赤黒木

目次

赤黒木

赤黒木は平衡二分木の1種であり、いくつかのノードは「赤」と指定されていて、残りは「黒」と指定されています。 他の平衡二分木と同じように、赤黒木に対する演算は木の大きさに対して対数時間で完了すると信頼できます。

Scalaは不変な集合やマップの実装として内部で赤黒木を利用するものを提供します。 TreeSetおよびTreeMapという名前で利用してください。

scala> scala.collection.immutable.TreeSet.empty[Int]

res11: scala.collection.immutable.TreeSet[Int] = TreeSet()

scala> res11 + 1 + 3 + 3

res12: scala.collection.immutable.TreeSet[Int] = TreeSet(1, 3)

赤黒木は全ての要素を整列した順に返す効率の良いイテレータを与えるため、SortedSetのScalaでの標準的な実装です。

続いては: 不変ビットセット

赤黒木

目次