2分探索木 | YottaGin

[Python] 2分探索木が同一か判定

2つの2分探索木が同一かどうか判定します。同じ場所のノードに同じデータを持つ場合を同一と判断します。 2分探索木は、以下の実装を使います。同じかどうかの判定を左の子と右の子に再帰的に行うことで判断できます。判定するノードが葉ノードの子で...

2分探索木を Python で実装します。以前、ほぼ全く同じ内容で記事を書いています。ノード 2分探索木では、ノードは自身のデータと、0個、1個、2個のいずれかの子ノードを持っており、左側の子ノードは親の値より小さい値、右...

二分探索木二分探索木（にぶんたんさくぎ、英:binary search tree）は、コンピュータプログラムにおいて、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。出典: フリ...

B木やB⁺木がなぜ必要なのか良く分かっていなかったのが、下記のビデオで分かったので、まとめます。 B木（びーき）は、コンピュータサイエンスにおけるデータ構造、特に木構造の一つ。ブロック単位のランダムアクセスが可能な補助記憶装置（ハードディスクドラ...

以下の続きです。ノードの挿入 Red Black Tree でノードの挿入は、以下の3つのステップで行われます。普通の2分探索木の挿入を行うまずは、普通の2分探索木と同じように、ノードを挿入します。挿入するノードの色を赤にする ...

以下の動画がとても分かりやすいです。 Red Black Treeと同じ平衡2分探索木にAVL木があります。 AVL木では、「左右部分木の高さの差は１以下」というルールを設けて、木の高さの調節を行いました。 Red Black ...

以下を参照しています。 AVL Tree | Set 1 (Insertion) AVL Tree | Set 2 (Deletion) また、ざっくりとした説明は、以下の動画が一番分かりやすかったです。インドの人は説明が上手です。 ...