LLRBツリー(Left-Leaning Red-Black Tree)

平衡二分木の世界では近年では赤黒木(Red-Black Tree, RB-tree)が標準的である。追加、検索、削除がそれぞれ最悪O(log N)というすぐれものだが、場合分けが多く実装はけっこう面倒だ。 赤黒木というの …

Continue reading ‘LLRBツリー(Left-Leaning Red-Black Tree)’ »