5

私が学んでいる教科書 (Lafore) は、最初に Red-Black Trees を提示し、疑似コードは含まれていませんが、提示された関連アルゴリズムはかなり複雑で、多くのユニークなケースがあります。

次に、彼は 2-3-4 Trees を提示します。これは、私には理解するのがはるかに簡単で、実装するのが簡単だと思います。彼には、非常に明確な実際の Java コードがいくつか含まれています。彼は 2-3-4 の方が実装しやすいとほのめかしているようで、これまで見てきたことに基づいて同意します。

ただし、ウィキペディアは反対のことを言っています...おそらく間違っていると思います：

http://en.wikipedia.org/wiki/2-3-4_tree

2-3-4 木は赤黒木の等長図であり、同等のデータ構造であることを意味します。つまり、2-3-4 ツリーごとに、データ要素が同じ順序の赤黒ツリーが少なくとも 1 つ存在します。さらに、ノードの拡張、分割、およびマージを引き起こす 2-3-4 ツリーの挿入および削除操作は、赤黒ツリーの色反転および回転と同等です。赤黒木への導入では、概念的に単純であるため、通常、最初に 2-3-4 木を紹介します。ただし、2-3-4 ツリーは、ツリーの操作に多数の特殊なケースが含まれるため、ほとんどのプログラミング言語で実装するのが難しい場合があります。赤黒木は実装が簡単なので、代わりに使用される傾向があります。

具体的には「特例が多い」という部分がかなり後ろ向きに思えます（特例が多いのは2-3-4ではなくRBだと思います）。しかし、私はまだ学んでいます (そして、正直なところ、赤黒の木について完全に理解していません) ので、他の意見を聞きたいです。

補足として...私はLaforeの言うことのほとんどに同意しますが、ウィキペディアが一般的であると言っているのとは逆の順序で彼がそれらを提示したことは興味深いと思います（RBの前に2-3-4）。RBは概念化するのが非常に難しいため、最初に2-3-4がより理にかなっていると思います。おそらく、彼がその順序を選んだのは、RB が、彼が前の章で完成させたばかりの BST とより密接に関連していたからです。

4

1 に答える 1

4

「より多くの特別なケース」についての部分は、私にはかなり後ろ向きに思えます（2-3-4ではなく、多くの特別なケースがあるRBだと思います）

言語にパターン マッチングがある場合、RB ツリーは数十行で実装できます。

data Color = R | B
data Tree a = E | T Color (Tree a) a (Tree a)

balance :: Color -> Tree a -> a -> Tree a -> Tree a
balance B (T R (T R a x b) y c          ) z d                               = T R (T B a x b) y (T B c z d)
balance B (T R a           x (T R b y c)) z d                               = T R (T B a x b) y (T B c z d)
balance B a                               x (T R (T R b y c) z d          ) = T R (T B a x b) y (T B c z d)
balance B a                               x (T R b           y (T R c z d)) = T R (T B a x b) y (T B c z d)
balance col a x b = T col a x b

insert :: Ord a => a -> Tree a -> Tree a
insert x s = T B a y b where
  ins E          =  T R E x E
  ins s@(T col a y b) 
    | x < y      =  balance col (ins a) y b
    | x > y      =  balance col a y (ins b)
    | otherwise  =  s
  T _ a y b = ins s

岡崎の論文からのこの有名な定義

于 2012-04-06T17:23:13.867 に答える