AVL Tree by Java -- これで分かったAVL木
AVL木(AVL Tree)は、 マップ(連想配列)と呼ばれるデータ構造の実装に使われる平衡木の１つです。 平衡木では木のバランスが適度にとれており、 キーの検索・要素の挿入・削除などの処理が、いかなる場合でも \(O(\log n)\) の計算量で行えます(\(n\) は要素数)。 AVL木の他にも 赤黒木 という平衡木がありますが、 AVL木は赤黒木に比べてより厳密に平衡性を維持しようとします。つまり、 よりバランスがとれているということです。 そのため赤黒木より検索の性能が良いとされています。 ただし、挿入や削除ではより手間がかかります。 本ページは、AVL木の実装に関して詳しく解説しています。 他のサイトでは省略されてしまっているような回転の場合分けについてもやさしく解説してあります。 その他にも、何故そうするの？という疑問に対して、 なるたけ答えるように書いたつもりですので、是非
Red-Black Tree by Java -- これで分かった赤黒木
このページは、マップと呼ばれるデータ構造の実装の１つである赤黒木 (２色木、red-black tree)について解説するページです。赤黒木は、要素の 挿入・削除・検索などの操作が \(O(\log n)\) の計算量で実行出来る平衡木 です(\(n\) は要素数)。赤黒木はやっていることは単純なのですが、とにかく 場合分けがたくさんあって、習得しようとしながらもくじけてしまった人も 多いのではないでしょうか？ しかし、ご安心ください。このページは場合分けを出来るだけ減らし、 挿入操作で４パターン、削除操作で８パターンさえ理解すれば赤黒木が分かる ように書かれています。削除操作に関しては、左右対称のパターンを省けば ４パターン理解すればおおむね OK です。これから赤黒木を勉強しようという人 はもちろん、一度は勉強したが挫折してしまったという人も是非とも読んでみて ください。 【準備】 ま
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
