二叉木の概念#
満たされた二分木#
二分木には、次の条件があります：度（子ノードの数）が 0 のノードと度が 2 のノードのみが存在し、かつ度が 0 のノードは同じレベルにあります。
- 合計 $2^{k}-1$ 個のノードがあります（k は木の深さです）
- 各レベルには $2^{n-1}$ 個のノードがあります（n は現在のレベルです）
完全二分木#
最後のレベル以外は満たされている必要があり、最後の行は左から右に並べ替えられ、間隔がない必要があります。
- 最下層には 1〜$2^{k-1}$ 個のノードが存在し、間隔はありません。
二分探索木#
二分探索木は順序付き木であり、二分整列木、二分探索木とも呼ばれます。
- 左部分木が空でない場合、左部分木のすべてのノードの値はその根ノードの値よりも小さいです。
- 右部分木が空でない場合、右部分木のすべてのノードの値はその根ノードの値よりも大きいです。
- 左右の部分木はそれぞれ二分整列木です。
- 同じキー値のノードは存在しません。
二分探索木の根ノードは変更されず、データの挿入や削除が行われると、二分木が単方向リストに向かうことになり、データの検索効率が低下するため、平衡二分木があります。
平衡二分木#
AVL 木（Adelson-Velsky and Landis Tree）
平衡二分木は二分木を最適化したものです。
- 空の木であることができます。
- 任意のノードの左部分木と右部分木は両方とも平衡木であり、高さの差の絶対値が 1 を超えない。
平衡の方法
バランスファクター：あるノードの左部分木と右部分木の高さ（深さ）の差は、ノードのバランスファクターであり、平衡二分木にはバランスファクターが 1 より大きいノードは存在しません（-1、0、1 のみ）。
平衡二分探索木#
平衡二分探索木は空の木であるか、左右の部分木がともに平衡二分木である（高さの差が 1 を超えない）ことがあります。