1 二分探索木、AVL木

データ構造とは、特定の性質を定義し、その性質を維持することです。

BS 木👉AVL 木

コース内容#

二叉排序树#

[またの名を二叉検索木、二叉探索木]

基礎知識#

性質：任意の三元組に対して、左部分木 < 根ノード < 右部分木
用途：検索、ランキングに関連する検索ニーズを解決する
【なぜ木構造の検索エントリは必ず根ノードになるのか？】
- 点と辺の意味を理解する：集合と関係
- 根ノードは全集を表す
構造操作：追加、削除、検索
- 追加
  - 子木の根ノードと比較し続け、再帰的に、子木に子ノードがなくなるまで
  - ⭐新しいノードは必ず葉ノードになる
- 削除 [ノード]
  - 度が 0：直接削除
  - 度が 1：子木 [孤児子木] をその親ノードに直接接続
  - 度が 2：[少し面倒]
    - 前駆または後続で元のノードを置き換える
      - 前駆ノード：その左部分木の最大値に対応するノード [このノードには右部分木がなく、度は最大で 1]
      - 後続ノード：その右部分木の最小値に対応するノード [このノードには左部分木がなく、度は最大で 1]
      - 【度が 2 のノードにのみ適用される。そうでなければ親ノードを探し、どの程度見つかるかを考慮する必要がある】
    - ⭐したがって、度が 0 または 1 のノード [前駆または後続] の削除問題に変換される
    - [一次元配列の削除操作としても理解できる]
- 検索：性質に基づいて再帰的に検索すればよい
挿入順序は木構造に影響を与え、異なる平均検索効率に対応する
- 同じシーケンスでも、異なる挿入順序
- 平均検索効率：ノード検索回数の期待値。すなわち、平均検索回数：検索総回数 / ノード数
  - 各ノードが等確率で検索されると仮定する
中間順序遍歴→小さいものから大きいものへの順序付きシーケンス
参考：『基礎データ構造』——3 木と二叉木 —— 二叉検索木

拡張内容#

[具体的なコードはコードデモを参照 —— 二叉排序树]

削除操作の最適化 [コードデモ —— 二叉排序树]
- 度が 0 と度が 1 のノードの削除操作は、【度が 1】の削除操作コードを共用できる
- 度が 0 のコード
- 度が 1 のコード
- 度が 0 のとき、temp は NULL を指し、同様に root を破棄し、NULL を返す
<ランキング問題>—— ランキング第k 位の要素を探す
- ⭐size フィールドを追加し、各子木のノード数を記録する [根ノードを含む]
  - データ構造の本質、特定の問題に対して【構造定義を変更する】
  - 挿入、削除時に size を更新する必要がある
- 検索条件
  - ① k = LS + 1、根ノードが我々が探している値
  - ② k < LS + 1、ランキング第 k 位の要素は左部分木にあり、左部分木で探し続ける
  - ③ k > LS + 1、ランキング第 k 位の要素は右部分木にあり、右部分木でランキング第 k - LS - 1 位の要素を探す
  - [PS] LS は左部分木のノード数
  - 境界条件で [-1 または key] を出力
<Top-k 問題>—— ランキング前k 位の要素を探す [ランキング <=k のすべての要素]
- 【ランキング問題に基づく】
- 検索条件
  - ① k = LS + 1、左部分木の値をすべて出力
  - ② k < LS + 1、前 k 位の要素はすべて左部分木にある
  - ③ k > LS + 1、根ノードと左部分木の要素は、すべて前 k 位の要素に属する
  - 木のサイズを縮小し続け、最初の状況に変わる
  - 解法は実際に多く、[例えばヒープ]、標準的な答えはない
二叉排序树とクイックソートの関係
- 【二叉排序树はクイックソートの思考構造レベルで使用されるデータ構造】
- クイックソートの Partition 操作
  - 基準値を二叉排序树の根ノードと見なす
  - 各 Partition 操作の後、基準値と左、右の関係は実際には👇
  - 根ノードと左、右部分木の関係
- ⭐以下の 2 つの考えを理解すれば、両者の関係が理解できる
  - 考え 1：クイックソートの時間計算量と二叉排序树の構築時間計算量の関係
    - 実際には同じことで、構築プロセスは複数の Partition プロセスに似ている
  - 考え 2：クイックセレクトアルゴリズムと二叉排序树の関係
    - 両者の本質も同じで、前者はアルゴリズムとして、後者はデータ構造として表現される
  - [個人的理解]
    - クイックソートは一堆の数が最初に一度 Partition し、半分に分けて続ける
    - 構築プロセスは一つの数を一つずつPartition し、毎回この数の位置を決めてから次に進む

平衡二叉查找树 —AVL 树#

二叉検索木の退化問題を解決する

基礎知識#

背景
- 発明者：AV、L、AV の貢献が大きい
- 年代：1962 年
- [神経ネットワークもこの年代に誕生した]
性質
- 本質的には二叉排序树でもあり、二叉排序树のすべての性質を持つ
- 追加の性質：左、右部分木の高さの差は 1 を超えない [左、右部分木はほぼ同じ大きさ]
⭐平衡条件、平衡調整

[さらに] 考える#

高さ H の BS、AVL 木が含むノード数はどの範囲にあるか？

[二叉木の一般的上限：2 ^ H - 1]
<BS> H ~ 2 ^ H - 1
<AVL> low(H - 2) + low(H - 1) + 1 ~ 2 ^ H - 1
- すなわち 1.5 ^ H ~ 2 ^ H - 1、low (H) は高さ H の AVL 木の最小ノード数を表す
- 左境界はフィボナッチ数列
  - その増加速度は 1.618 ^ n ≈ 1.5 ^ n 【予測に使用できる】
- 👉ノード数と高さの関係は対数関係であるため、検索効率は O (logN) レベル
❓ [さらに] 通常の二叉排序树の検索効率は必ず AVL 木より劣るのか？
- 必ずしもそうではなく、挿入シーケンスの順序によるが、AVL 木の下限は高い
- 【引き延ばし】
  - 木の高さ = 生命の長さ、ノード数 = 生命の富、異なるアルゴリズムで結果は異なる
  - 教育は底線を高めるものであり、上限ではなく、上限は能力と運に依存する
    - 上限は大きく、選択できない挿入シーケンスに大きく依存し、運に任せる

調整⭐#

挿入 / 削除 + 調整：挿入操作は二叉排序树と一致し、重要なのは調整 [⭐どのノードを回すかをつかむ]

回転#

[不均衡なときに使用される基本操作]

左回転
- 根ノードをつかみ、中心点を左に回転させる
  - K3 が根ノードになる
  - K1 が K3 の左部分木になる
  - K3 の元の左部分木 A が K1 の右部分木になる [K3> A > K1 のため]
- "葉ノード" の深さの変化：A は変わらず、B - 1、K2 + 1
  - 👉子木の高さの変化：左部分木 + 1、右部分木 - 1
右回転
- 根ノードをつかみ、中心点を右に回転させる
  - K2 が根ノードになる
  - K1 が K2 の右部分木になる
  - K2 の元の右部分木 B が K1 の左部分木になる [K2 < B < K1 のため]
- "葉ノード" の深さの変化：A - 1、B は変わらず、K3 + 1
  - 👉子木の高さの変化：左部分木 - 1、右部分木 + 1
左回転と右回転は対称操作であり、本質的には子木の高さに影響を与える

不均衡タイプ && 調整戦略#

判断シーン：バックトラックの過程で、最初に不均衡を発見したとき、不均衡であれば調整する
状況は対称：LL ——RR ，LR——RL

① LL

⭐重要なポイント⭐：h1、h2、h3、h4 の関係を分析する [等式を書く]
- 分析
  - 一つずつ挿入し、新しく挿入されたノードは必ず A 子木に到達し、LL 型の不均衡を引き起こす [削除も一つずつ行う]
  - 挿入前は必ず平衡である
  - 挿入後、K1 の左部分木は右部分木より 2 高い
    - すなわち h (K2) = h (K3) + 2 であり、
      - h(K2) = h1 + 1
      - h(K3) = max(h3, h4) + 1
- 等式関係 =>
  - h1 = max(h3, h4) + 2 = h2 + 1
  - [PS] |h3 - h4| <= 1
**<調整戦略>** 大右回転。結果は上図を参照、平衡分析は以下：
- ① K1：左部分木の高さh2= 右部分木の高さmax(h3, h4) + 1=h1 -1
- ② K2：左部分木の高さh1= 右部分木の高さh2 + 1
- 平衡が取れており、非常にバランスが取れていると言える

② LR

⭐重要なポイント⭐：h1、h2、h3、h4 の関係を分析する [等式を書く]
- 分析
  - 一つずつ挿入し、新しく挿入されたノードは必ず B / C 子木に到達し、LR 型の不均衡を引き起こす
  - 挿入前は必ず平衡である
  - 挿入後、K1 の左部分木は右部分木より 2 高い
    - すなわち h (K2) = h (D) + 2 であり、
      - h(K2) = max(h2, h3) + 2
      - h(D) = h4
- 等式関係 =>
  - max(h2, h3) = h4 = h1
  - [PS] |h2 - h3| <= 1

❗ 再度注意！判断は常にバックトラックの過程で最初の不均衡時に発生するため、それ以前のすべての子木は平衡である

**<調整戦略>** 小左回転 + 大右回転。結果は以下の図を参照：
- まず小左回転で LL 型に変換し、その後大右回転 [LL 調整戦略]
- 平衡分析
  - 明らかに、左右部分木の高さは h1、h2、h3、h4 に依存する
  - それらの間の高さの差は 1 を超えない [h2 または h3 のいずれかが小さい可能性がある]

調整戦略の小結#

バックトラック段階での最初の不均衡ノードで発生する
調整の重要なポイント：4 つの状況での ABCD4 つの子木の高さの関係
4 つの状況
- LL、LR：最終的に大右回転が必要
  - LL、大右回転
  - LR、まず小左回転、その後大右回転
- RL、RR：最終的に大左回転が必要
  - RL、まず小右回転、その後大左回転
  - RR、大左回転

[平衡二叉查找树 —SBTree]#

AVL は木の高さで平衡を取るが、SBTree はノード数で平衡を取る
AVL の学習順序を参考に：平衡条件 + 平衡調整 [挿入、削除]

随堂练习#

2 番目のシーケンスから構成された二叉検索木は一つのリストに退化し、挿入順序が構造に影響を与える
不均衡を判断する際、挿入ノードから一歩ずつバックトラックし、不均衡があればすぐに調整する

コードデモ#

二叉排序树#

5 つの基本操作：初期化、破棄、検索、挿入、削除
ソート問題の追加 [サイズフィールドの追加]、Top-k 問題の解答 [ソート問題に基づく]
[PS]
- 前駆を探す際にバグが存在：度が 1 または 0 のノードの前駆は必ずしも子木に存在するわけではないが、このシーンは気にしなくてよい
- 再帰は境界条件を考慮する必要がある
- マクロを使ってコードをより美しくすることを学ぶ
- 二叉木の基本的な分析は通常 3 つの状況を考慮する：左、根、右
一部の結果

【附】ランダム生成入力操作のコード

等比例でない操作タイプを生成

AVL 树#

挿入と削除後、木の高さを再計算することに注意【常に構造定義を維持することを忘れない】
- 挿入 / 削除ノード時 + 左回転 / 右回転調整時
⭐NIL ノードを導入し、NULL🆒を代替する [赤黒木でも必要]
- NULL はアクセスできない
- NIL は実際のノードであり、アクセス可能
- 【コード実装を便利にする】
LL、LR および RL、RR の最後の操作はそれぞれ大右回転および大左回転である

附加知識点#

二叉木の状況を分析する際、基本的には 3 つの状況に分ける：左、根、右

思考点#

通常の二叉排序树の検索効率は必ず AVL 木より劣るのか？
- 必ずしもそうではなく、挿入シーケンスの順序によるが、AVL 木の下限は高い
- 【引き延ばし】
  - 木の高さ = 生命の長さ、ノード数 = 生命の富、異なるアルゴリズムで結果は異なる
  - 教育は底線を高めるものであり、上限ではなく、上限は能力と運に依存する
    - 上限は大きく、選択できない挿入シーケンスに大きく依存し、運に任せる

Tips#

C++ を学ぶ前提：システムプログラミング、ネットワーク知識、アルゴリズム構造、C 言語
アルゴリズム設計および分析能力とは：分類討論 [いくつかの状況に分ける] および帰納的要約 [複数の状況を一つにまとめる] の能力
- プログラム = アルゴリズム + データ構造
- 問題を解くことでこの能力を向上させる人は天賦の才能を持つ選手である
おすすめの極客コラム ——誰でも学べるプログラミング入門講座—— 伝統的な学習方法への挑戦