4-1. 二分探索木
2
二分木とは
レコードを次の３つで構成
•要素を格納するセル
•左部分木を指すポインタを格納するセル
•右部分木を指すポインタを格納するセル
3
左部分木
根(root)
右部分木
二分探索木とは
•二分探索木では，小さい要素を左部分木に，大き
い要素を右部分木に格納する
•二分探索木を，中間順 (in-order) で走査すると，
要素は整列（ソート）された順になる
4
左部分木
根(root)
右部分木
要素の削除
•要素の削除は，場合分けで行う
•削除する要素に子がない場合
•削除する要素に子が１つある場合
•削除する要素に子が２つある場合
5
削除する要素に子がない場合
単純に要素を削除する
４を削除
７
５９
３
１４
７
５９
３
１
6
１，９の削除のときも，
単純に要素を削除する
削除する要素に子が１つある場合
要素を削除する．直下の子要素が置き換わる
５を削除
７
５９
３
１４
７
９
３
１
7
削除する要素に子が２つある場合
要素を削除する．左部分木の中にある「最大の要
素」を削除の上で，それが置き換わる
７を削除
７
５９
３
１４
8
５
９
３
１４
4-2. 「二分探索木」を実習で
きる
オンラインサイトの紹介
9
10
「二分探索木」を実習できる
オンラインサイトの紹介
パソコン演習
④説明が出る．ESC キーを押して，説明を消す
⑤左下のメニューで「検索」を選び，
「行く」を選ぶ．表示を確認する．
12
パソコン演習
⑥今度は，左下のメニューで「入れる」を選び，
「行く」をクリックする．表示を確認する．
⑦データが増えるので，確認する
13
