Binary Search Trees (BST) Chapter 10 Binary Search Trees (BST)

Chap.10 Contents 10.1 Binary Search Trees 10.1.1 The BinarySearchTree 10.1.2 Implementation of the BinarySearchTree Class 10.2 Balanced Binary Search Trees 10.2.1 AVL Trees 10.2.2 The Height of an AVL Tree 10.2.3 The AVLTree Class

10.1 Binary Search Trees (BST)

The BinarySearchTree Implementation 10.1.1 The BinarySearchTree Implementation of the Set Interface

10.1.2 Implementation of the BinarySearchTree Class

依國語注音符號順序來排序

public Iterator<E> iterator() { return new TreeIterator(); }

contains, add, 與remove methods 唯一可存取的 element 是 root. left sub-tree 的每個 element 皆 小於 root, 而且 right sub-tree 的每個 element 皆 大於 root.

80 40 90 60 50 75 contains (75)? true contains (73)? false

public boolean contains (Object obj) { Entry<E> temp = root; int comp; while (temp != null) { comp = ( (Comparable)obj).compareTo (temp.element); if (comp == 0) /*found it*/ return true; if (comp < 0) /*search left sub-tree*/ temp = temp.left; else/*comp> 0,search right sub-tree*/ temp = temp.right; } // while return false; /*tree does not contain obj */ } // end of contains

add (73); 80 40 90 60 50 75

80 40 90 60 50 75 73 Will the inserted element always be a leaf? ANS:Yes

public boolean add (E element) { if /*tree is empty*/(root == null) /* then add element as root*/ {root = new Entry (element, null); size++; return true;} else/*tree is not empty*/ { Entry<E> temp = root; int comp; while (true) { comp = ((Comparable)element).compareTo (temp.element); if /* the element is already there */ (comp == 0) return false; if /*insert the element in left subtree*/ (comp < 0) if (temp.left != null) temp = temp.left; else/* temp.left is null, insert it here*/ {temp.left = new Entry<E> (element, temp); size++; return true;} else /*insert the element in right subtree */ (comp >0) if (temp.right != null) temp = temp.right; else/*temp.right is null, insert it here*/ {temp.right = new Entry<E> (element, temp); size++; return true;} }/* while*/ }/*tree is not empty*/ } //end of add

public RBT. Entry BSTinsert (E anElement) { aRoot=this; RBT public RBT.Entry BSTinsert (E anElement) { aRoot=this; RBT.Entry aNode; if /*tree is empty*/(aRoot == null) /* insert anElement as root*/ {aNode = new Entry (anElement, null); size++; return aNode;} else/*tree is not empty*/ { Entry<E> temp = aRoot; int comp; while (true) { comp = ((Comparable) anElement).compareTo (temp.element); if /* the anElement is already there */ (comp == 0) {System.out.println(“duplicate element: “+ anElement); System.exit(1);} //強迫程式結束 if /*insert anElement in left subtree*/ (comp < 0) if (temp.left != null) temp = temp.left; else/* temp.left is null, insert it here*/ {aNode=temp.left = new Entry<E> (element, temp); size++; return aNode;} else /*insert anElement in right subtree */ (comp >0) if (temp.right != null) temp = temp.right; else/*temp.right is null, insert it here*/ {aNode=temp.right = new Entry<E> (element, temp); }/* while*/ }/*tree is not empty*/ } //end of BSTinsert()

For adding an element, what is the worst case? chain What is the worst height? n-1 The worstTime (n) is linear in n. What is the average height? log n The averageTime (n) is logarithmic in n.

remove (50); 80 40 90 60 50 75 73

remove (40); 80 40 90 60 75 73

After removing 40: 80 60 90 75 73

remove (80); 80 60 110 75 100 150 73 85 105 95

element 80 has two children, 所以無法直接將 80 抽離 tree (否則tree有個洞) tree中有兩個 elements 可取代 80 的位置 而不會破壞 binary search tree 左小右大的特性. Which two? Answer on next page

我們可以用 前一個 75 或 後一個 85 來換掉 80. 我們採用 後一個 85 因為稍後會講到 successor method. element的後一個為: right sub-tree 的最左邊的 element Thus, replace 80 with 85, and then remove 85.

After removing 80: 85 60 110 75 100 150 73 95 105

Can removing the successor get complicated? Ans: Yes Can the successor have two children? Ans: Yes, then, you have to do the same again to fill up the “hole”.

For “remove” method, What is worstTime(n)? Ans: O (N) What is averageTime(n)? Ans: O (log N)

// successor returns the successor Entry of e, if e has a successor. // returns null, otherwise. // The averageTime(n) is constant, and worstTime(n) is O(n). protected Entry<E> successor (Entry<E> e)

protected Entry<E> successor (Entry<E> e) { if (e == null) return null; else if /*e 有 right child, 像 50*/ // 右下走一步 再往左下方走到底 else /* e 沒有 right child, 像 36*/ // 往左上方走到底 再右上走一步 } // end of successor

protected Entry<E> successor (Entry<E> e) { if (e == null) return null; else if /*e has a right child, like 50 above*/ // successor is leftmost Entry in right subtree of e else /* e has no right child, like 36 above */ // go up the tree to the left as far as possible, // then go up to the right. } // successor

C Point 1 : A O N R G T U

G Point 2 : A O N R T 59 U

next G Point 3 : A O N R lastReturned T 60 60 U

G Point 4 : A O next null R lastReturned T 61 61 U

G Point 5: A O next lastReturned R T 62 62 62 U

10.2 Balanced Binary Search Trees

必也正名乎 Rotate 本是順時針 逆時針 兩種 何來左轉 右轉? 下面的象限圖為您正名 上圖把順時針rotate 視為右轉 視為左轉

(2) l.right=p (1) p.left=l.right

Rotation 的實作 觀察旋轉前後，找出需要改變的 references 三個重點: 只要改變兩個 references (見上頁Steps 1 & 2) references 是雙向的 parent -> child child -> parent 要考慮原本 p 的 parent 的 三種 cases P L L L.L P L.R L.L L.R

重點 1. 要改變的兩個 references For a right rotation around p: (1) p.left = l.right;   l.right = p; where p stands for parent, and l for the left child of p.

重點 2. 考慮 references 是雙向的 所以共要改變四個 references: (1) p.left = l.right; l.right.parent = p; (2) l.right = p; p.parent = l;

重點 3. p 的 parent 有三種 cases Case 1: p 為 root ，其 parent 為 null

Case 2: p 的 parent 的 right subtree 是這棵rotated tree p.parent.right 就是 p Rotated Tree P

Case 3: p 的 parent 的 left subtree 是這棵rotated tree p.parent.left 就是 p Rotated Tree P

軟體創作 要用 一疊白紙 , 一支削尖的鉛筆 , 橡皮擦, 一杯花草茶, 及 一顆沈靜的心 (心要慢) 一杯花草茶, 及 一顆沈靜的心 (心要慢) 讓心靈專注 渾然忘我 這時思路流暢 創意泉湧 與一位摯友彼此切磋 (pair programming) 不斷思 考各種 cases 每個case用一張紙畫草圖 反覆思考 debug (去除思考漏洞) 修改 再整理出演算法 這真的是很 enjoyable 的軟體創作過程! 軟體工程師 要快樂 有尊嚴 而平和 的生活著!

金城武 海報 世界越快 心則慢 中華電信 極速4G

軟體開發 上面 Right Rotation 清楚顯示 如何藉著 design sketch 等文件 幫助思考 想出演算法! (註: method name 要用動詞 故叫 rotateRight ( ) ) 如何藉著 design sketch 等文件 幫助思考 想出演算法! 這就叫 軟體開發!

RR 的旋轉 R Left Rotation

LL 的旋轉 L Right Rotation

LR 的旋轉 先對左邊子節點 left 旋轉，轉換成 LL 的形式， 再做一次 right 旋轉 即完成 Right Rotation L Left Rotation

RL 的旋轉 先對右邊子節點 right 旋轉，轉換成 RR 的形式， 再做一次 left 旋轉 即完成 Left Rotation R R Right Rotation

Rotation 的啟示 用 high-level data structure (此處是tree) 才能畫出草圖 有了草圖 才能發揮想像力 想出rotate這高階而精巧的動作 注意: 它實際上 低階地說 只是幾個 references 的變動

10.2.1 AVL Trees

10.2.2 The Height of an AVL Tree minh 為 建立高度為 h 的AVL tree 所需的最少 elements 數目

高度 h 的AVL tree t 要有最少 elements個數 它的 sub-trees 高度為 h-1 及 h-2. 其中一棵 subtree 必須高度為 h-1 有 minh-1 個 elements, 另一棵 subtree 必須 高度為 h-2 有 minh-2 個 elements. As shown next page: minh = minh-1+minh-2+1

h=2 minh= 4 h=3 minh=7 h=3-2=1 minh=2 50 90 50 100 39 80 39 80 129 60 h=3-1 min=4 60

200 h=4 minh =12 100 500 39 150 300 600 130 200 450 900 400

Fibn = Fibn-1 + Fibn-2 for n>=2 h 0 1 2 3 4 Fibh 0 1 1 2 3 5 8 13 Fibonacci (Fib) Numbers 0 1 1 2 3 5 8 13… Fib0 =0, Fib1 =1, Fib2 =1, Fib2=2, Fib2 =3, … Fibn = Fibn-1 + Fibn-2 for n>=2 h 0 1 2 3 4 Fibh 0 1 1 2 3 5 8 13 minh 1 2 4 7 12 Thus, minh = Fib(h+3) – 1 (proof by math. induction)

maxh AVL tree maxh 為 高度為 h 的AVL tree 且盡可能有最多的 elements.

maxh 即binary tree 最多elements的值 maxh = 2h+1-1 50 39 80 30 45 60 100

10.2.3 The AVLTree Class

1. L (left) 2. R (right) 3. = (balanced) are Balance Factors (平衡因子) 以 20 為例 right sub-tree height is 2 left sub-tree height is 1 向右傾斜 故標示 R (right)