「アルゴリズムとデータ構造」資料 9.

(1)

9.

二分木

奈良女子大学生活環境学部鴨浩靖

2009年12月8日初版 2011年11月21日第二版

2013年1月7日第三版 2020年12月14日第四版

1 / 36

(2)

たとえば、式を文字列で表現するよりも木で表現したほうが、構造を素直に反映できる。

文字列による表現 x+y×z (x+y)×z 木による表現 +

x ×

y z

×

+ z

x y

2 / 36

(3)

特に、子が高々二個である木を二分木という。

3 / 36

(4)

C

·

· ·

·

· ·

4 / 36

(5)

int

struct node {

struct node *left, *right;

int data;

};

struct bintree {

struct node *root;

};

5 / 36

(6)

すべての節点について、

▶ その節点のラベルの値は、その左部分木のどの節点のラベルの値よりもそれ以上であり、

▶ その節点のラベルの値は、その右部分木のどの節点のラベルの値よりもそれ以下である

二分木を、順序づけられた二分木という。

6 / 36

(7)

10

5 15

0 8 12 20

7 9 13 17

7 / 36

(8)

順序づけられた二分木から、特定の値をラベルに持つ節点をみつけるのは、次のアルゴリズムでできる。

1. pを根を指すポインタで初期化する。

2. 以下をくりかえす。

2.1 pがヌルポインタならば、みつからなかったと報告して終了。

2.2 pの指す節点のラベルがみつけたい値に等しければ、その節点を返して終了。

2.3 pの指す節点のラベルがみつけたい値よりも大きければ、pをその節点の左子節点へのポインタに変更。

2.4 pの指す節点のラベルがみつけたい値よりも小さければ、pをその節点の左子節点へのポインタに変更。

8 / 36

(9)

10^{目標より小さい}

5 15

0 8 12 20

7 9 13 17

9 / 36

(10)

10

5 15^{目標より大きい}

0 8 12 20

7 9 13 17

10 / 36

(11)

10

5 15

0 8 12^{みつかった！} 20

7 9 13 17

11 / 36

(12)

5 15

0 8 12 20

7 9 13 17

12 / 36

(13)

10

0 8 12 20

7 9 13 17

13 / 36

(14)

10

5 15

0 8 12^{目標より大きい} 20

7 9 13 17

14 / 36

(15)

10

5 15

0 8 12 20

7 9 13 17

なかった！

15 / 36

(16)

挿入は、探索でみつからなかったときの処理を、最後の候補の左右適当な側に子を挿入するだけで可能。

16 / 36

(17)

5 15

0 8 12 20

7 9 13 17

17 / 36

(18)

10

0 8 12 20

7 9 13 17

18 / 36

(19)

10

5 15

0 8 12^{みつかった！} 20

7 9 13 17

19 / 36

(20)

10

5 15

0 8 12 20

7 9 13 17

何もしない

20 / 36

(21)

5 15

0 8 12 20

7 9 13 17

21 / 36

(22)

10

0 8 12 20

7 9 13 17

22 / 36

(23)

10

5 15

0 8 12^{目標より大きい} 20

7 9 13 17

23 / 36

(24)

10

5 15

0 8 12 20

7 9 ^挿入(11) 13 17

24 / 36

(25)

削除は、ちょっと手間がかかる。

▶ 削除する節が葉の場合そのまま削除する。

▶ 削除する節が左右のうち片方の子のみを持つ場合子節を、部分木ごと、削除する節の位置に移動する。

▶ 削除する節が左右の両方の子を持つ場合

右部分木の最小なラベルを持つ節を探す。見つかった節を再帰的に木から削除して、削除する節の位置に移動する。

25 / 36

(26)

10

5 15

0 8 12 20

7 9^{削除したい} 13 17

26 / 36

(27)

10

5 15

0 8 12 20

7 ^{除去するだけ} 13 17

27 / 36

(28)

10

5 15

0 8 12^{削除したい} 20

7 9 13 17

28 / 36

(29)

10

5 15

0 8 13^子を移動 20

7 9 17

29 / 36

(30)

10

5 15^{削除したい}

0 8 12 20

7 9 13 17

30 / 36

(31)

10

0 8 12 20

7 9 13 17^{右部分木の最小値}

31 / 36

(32)

10

0 8 12 20

7 9 13 17^{再帰的に削除}

32 / 36

(33)

10

5 17^移動

0 8 12 20

7 9 13

33 / 36

(34)

あまり削除が頻繁でない時は、ラベルに「使用中」フラグを追加して、削除のかわりに「使用中」フラグをオフにする手もある。

その場合、「使用中」フラグを取り扱うために探索・挿入も対応して変更を加える必要がある。

34 / 36

(35)

二分木の左右が都合よく釣りあっていれば、探索・挿入・削除は

O(logn)の時間で実行できる。しかし、偏っていると、最悪で

O(n)^{の時間がかかる。}

35 / 36

(36)

7

3 13

2 5 11 17

最悪の場合の例

2 3

5 7

11 13

17

36 / 36