dackdive's blog

新米webエンジニアによる技術ブログ。JavaScript(React), Salesforce, Python など

「みんなのデータ構造」学習メモ:6.2 BinarySearchTree 二分探索木

みんなのデータ構造(紙書籍+電子書籍) – 技術書出版と販売のラムダノート

amazon

みんなのデータ構造

みんなのデータ構造

  • 作者:Pat Morin
  • 発売日: 2018/07/20
  • メディア: 単行本(ソフトカバー)

これまでのメモ

二分木の続き。 TypeScript によるソースコード
https://github.com/zaki-yama/open-data-structures-typescript/blob/master/src/BinarySearchTree.ts

用語

f:id:dackdive:20200429001406p:plain:w360

  • 二分探索木の性質:あるノード u に対し、
    • u.left 以下の部分木はすべて u.x より小さい
    • u.right 以下の部分技はすべて u.x より大きい

参考:探索木 - Wikipedia

その木構造が探索木として機能するために、あるノードのキーは、そのノードの左の子ノードのキーよりは常に大きく、逆に右の子ノードのキーよりは常に小さい性質が必要である

本書では言及されてなかったけど、二分木と関係なく探索木という用語があって、両方の性質を満たすものを二分探索木と呼ぶ、という理解。

先にまとめ

二分探索木は SSet (順序づけられた Set)インターフェースの実装。
add(x), remove(x), find(x) の実行時間は  O(n) である。

二分探索木は木の形状に関して制約がないため、アンバランス(たとえば、ほとんどのノードが子を1つだけ持つ鎖のような形)かもしれないという問題がある。

二分探索木の探索・追加・削除

6.2.1 探索(find)

r からノードを順にたどって x を探す。ノード u を訪問しているとき、以下の3つの場合がありうる。

  1. x < u.x なら u.left に進む
  2. x > u.x なら u.right に進む
  3. x = u.x なら値が x であるノード u を見つけた

3 つめのケースになるか、u = null になった(= 見つからなかった)ら探索は終了。

6.2.2 追加(add)

f:id:dackdive:20200429001428p:plain:w360

x を追加するには、まず x を検索する。このとき、最後に訪問したノード p を保持しておき、x が見つからなかった場合はノード p の子である葉として、x を保存する。

6.2.3 削除(remove)

f:id:dackdive:20200429001633p:plain:w480

削除するノードの子が

  • 0個のとき:葉なので、そのままノードを削除すればいい
  • 1個のとき:削除するノードの親と子をつなぎ合わせる
  • 2個のとき:u.right を根とする部分木の中で最小の値を持つノード w を見つけ、 u があった場所に挿入する

2個のときがちょっと複雑。ロジックとしては、 u.right にアクセスしてその後ひたすら左の子が存在しなくなるまでたどっていけばいい(一番左が最小なので)。