アルゴリズムとデータ構造 補足資料13-4 「2分探索木の追加・削除（ダイジェスト）」 横浜国立大学 理工学部 数物・電子情報系学科 富井尚志
探索木のオペレータ（ダイジェスト） 探索木を探索する 探索木に節点を追加（挿入）する 探索木から節点を削除する 端点（葉：leaf）の削除 一つの子孫しか持たない節点の削除 二つの子孫を持つ接点の削除
探索木の成長 root {7, 2, 9, 1, 6, 8, 10, 4, 3, 5}
探索木の成長 root {7, 2, 9, 1, 6, 8, 10, 4, 3, 5} 7 NULL NULL
探索木の成長 root {7, 2, 9, 1, 6, 8, 10, 4, 3, 5} 7 NULL 2 NULL NULL
探索木の成長 root {7, 2, 9, 1, 6, 8, 10, 4, 3, 5} 7 2 9 NULL NULL NULL NULL
探索木の成長 {7, 2, 9, 1, 6, 8, 10, 4, 3, 5} 7 2 9 1 root NULL NULL NULL
探索木の成長 {7, 2, 9, 1, 6, 8, 10, 4, 3, 5} 7 2 9 1 6 root NULL NULL NULL
探索木の成長 {7, 2, 9, 1, 6, 8, 10, 4, 3, 5} 7 2 9 1 6 8 root NULL NULL NULL
探索木の成長 {7, 2, 9, 1, 6, 8, 10, 4, 3, 5} 7 2 9 1 6 8 10 root NULL NULL
探索木の成長 {7, 2, 9, 1, 6, 8, 10, 4, 3, 5} 7 2 9 1 6 8 10 4 root NULL NULL
探索木の成長 root {7, 2, 9, 1, 6, 8, 10, 4, 3, 5} 7 2 9 1 6 8 10 NULL NULL NULL NULL NULL NULL NULL 4 NULL 3 NULL NULL
探索木の成長 root {7, 2, 9, 1, 6, 8, 10, 4, 3, 5} 7 2 9 1 6 8 10 NULL NULL NULL NULL NULL NULL NULL 4 3 5 NULL NULL NULL NULL
探索木の枝刈り delete( 8, root ) 端点、または、 一つの子孫しか持たない接点の削除 7 2 9 1 6 8 10 4 3 NULL 1 6 8 10 NULL NULL NULL NULL NULL NULL NULL 4 3 5 NULL NULL NULL NULL
探索木の枝刈り delete( 7, root ) 二つの子孫を持つ接点の削除 左部分木の 最右要素で 置き換え 7 2 9 1 6 10 NULL 1 6 10 NULL NULL NULL NULL NULL 4 3 5 NULL NULL NULL NULL
探索木の枝刈り delete( 7, root ) 二つの子孫を持つ接点の削除 左部分木の 最右要素で 置き換え 6 2 9 1 6 10 値をコピー 2 9 NULL 1 6 10 NULL NULL NULL NULL NULL 左部分木の 最右要素 4 3 5 NULL NULL NULL NULL
探索木の枝刈り delete( 7, root ) 二つの子孫を持つ接点の削除 左部分木の 最右要素で 置き換え 6 2 9 1 6 10 NULL 1 6 10 NULL NULL NULL NULL NULL 左部分木の 最右要素→削除 4 3 5 NULL NULL NULL NULL
探索木の枝刈り 6 2 9 1 10 4 3 5 root NULL NULL NULL NULL NULL NULL NULL NULL
探索木の成長 7 を追加 6 2 9 1 10 4 3 5 root NULL NULL NULL NULL NULL NULL NULL
探索木の成長 7 を追加 6 動的データ構造： 追加や削除が生じても、 構造を変えながらデータを 保持できる 2 9 1 7 10 4 3 root 7 を追加 6 動的データ構造： 追加や削除が生じても、 構造を変えながらデータを 保持できる 2 9 1 7 10 NULL NULL NULL NULL NULL NULL 4 3 5 NULL NULL NULL NULL