二分探索木のアニメーション/可視化(データ構造@情報学) - 動き/アニメーションを目で見て理解する学問

で見て理解するアルゴリズム

Main

Info

項目を検索中...

タイトルを検索中...

BinarySearchTree(二分探索木)のイメージ

BinarySearchTree(二分探索木)でのイメージを持てるような例を紹介します.

これだけ知っとく! : BinarySearchTree(二分探索木)概要

Points!

必ず子ノード左側の値 < 親ノードの値 < 子ノード右側の値の関係になる木構造
値を追加する時、親要素より小さい値は左側の木へ、大きい値は右側の木に追加される
値を探索する時、親要素より小さい値は左側の木へ、大きい値は右側の木に探しにいく.\(O(log_2N)\)
値を削除する時、子要素が1つのみなら、対象を削除してその下の子要素を上に移動させる
値を削除する時、子要素が2つなら、小さい値を持つ左側から最大値を取り出し、削除ノードの値を入れる.もともと最大ノードだったところはそのノードの左側を上に移動させる.(最大のためその最大値を持つノードの左側に木はない)

前置き! : 操作方法

下記の「追加する数字」に数字を入力して、Addを押すと、二分探索技に新しい数字が追加されます.
またSearchで指定された値があるかどうかを探し, Deleteで指定ノードを削除します.
全体のデータ数を指定してResetを押すとその数にしてグラフの作成をやり直します.
WithAnimationをOFFにすれば、アニメーションなしで見ることができます.

可視化! : BinarySearchTree(二分探索木)の可視化

BinarySearchTreeの木表現

With Animation