1、Chapter 10 BINARY TREES,1. General Binary Trees,2. Binary Search Trees,3. Building a Binary Search Tree,4. Height Balance: AVL Trees,5. Splay Trees,6. Pointers and Pitfalls,10.1 Binary Trees,DEFINITION A binary tree is either empty, or it consists of a node called the root together with two binary t

2、rees called the left subtree and the right subtree of the root.,1. Definitions,2. Traversal of Binary Trees,At a given node there are three tasks to do in some order: Visit the node itself (V); traverse its left subtree (L); traverse its right subtree (R). There are six ways to arrange these tasks:,

3、VLR LVR LRV VRL RVL RLV,By standard convention, these are reduced to three by considering only the ways in which the left subtree is traversed before the right.,preorder,preorder,inorder,inorder,postorder,postorder,These three names are chosen according to the step at which the given node is visited

4、.,With preorder traversal we first visit a node, then traverse its left subtree, and then traverse its right subtree. With inorder traversal we first traverse the left subtree, then visit the node, and then traverse its right subtree. With postorder traversal we first traverse the left subtree, then

5、 traverse the right subtree, and nally visit the node.,See pg.432-434,Expression tree,x = (-b+(b2-4ac)0.5) / (2a),3. Linked implementation of Binary Trees,Node structure of Binary Trees,example,Linked Binary Trees Specifications,template class Binary_tree public: / Add methods here. protected: / Add

6、 auxiliary function prototypes here. Binary_node *root; ;,Binary trees class,二叉樹根結(jié)點指針,template struct Binary_node Entry data; Binary_node *left; Binary_node *right; Binary_node( ); Binary_node(const Entry ,Binary node class,數(shù)據(jù)域,指向左孩子的指針,指向右孩子的指針,template void Binary_tree:inorder(void (*visit)(Entry

7、,Inorder traversal:,method,函數(shù)參數(shù) (訪問數(shù)據(jù)),調(diào)用遞歸中序 遍歷函數(shù),遞歸中序遍歷函數(shù) 多一個參數(shù),樹形結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)。樹能夠很好地描述結(jié)構(gòu)的分支關(guān)系和層次特性，它非常類似于自然界中的樹。樹結(jié)構(gòu)在客觀世界中是大量存在的，例如家譜以及行政組織機構(gòu)都可用樹形象地表示。樹在計算機領(lǐng)域中也有著廣泛的應用，如在編譯程序中，用樹來表示源程序語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，可以用樹來組織信息。本章重點討論二叉樹的存儲表示及其各種運算，要求大家要學會編寫實現(xiàn)二叉樹的各種運算的算法。 二叉樹是遞歸定義的，因此遞歸是它的固有特性，本小節(jié)的練習中就要求大家完成許多操作二叉樹的算

8、法，且是遞歸算法。 下面我們給出一個以先序方式創(chuàng)建任意二叉樹的算法，請 認真學習。,template void Binary_tree:CreatBinary_tree() CreatBinary_tree(root); template void Binary_tree: CreatBinary_tree(Binary_node* ,建立二叉鏈表 表示的二叉樹,遞歸建立以r為 根結(jié)點指針的二叉鏈表 表示的二叉樹,建立”空”二叉樹,建立根結(jié)點,建立根結(jié)點 的左子樹,建立根結(jié)點 的右子樹,Entry data member,Entry data member,表示空的 數(shù)據(jù),我們再給出一個應用例

9、。,在以二叉鏈表存儲的二叉樹中查找值為x的結(jié)點，請編寫一非遞歸算法：打印值為x的結(jié)點的所有的祖先結(jié)點的值。設值為x的結(jié)點不多于1個。,template printAncestors(Binary_tree tree, T ,在二叉樹tree中搜索 結(jié)點x，找到則打印 所有祖先結(jié)點及x 否則輸出x不存在,要求非遞歸 因此自行定義 棧結(jié)點類型,指針域(保留從根到 搜索結(jié)點路徑上 所以結(jié)點指針),標記域 (tag=0左子樹 否則是右子樹),置空棧,棧數(shù)組,棧結(jié)點類型名,取得二叉樹tree 的根結(jié)點指針 做為t的初始值,指針不空而且 其所指結(jié)點的 數(shù)據(jù)域不是x,棧不空,搜索左子樹 尋找值為x的結(jié)點,進

10、棧,二叉樹tree 的根結(jié)點是x,if (t ,找到值為x的結(jié)點 輸出所有祖先結(jié)點 (棧),跳出while循環(huán),如果棧頂是右指針 彈出,如果棧不空 棧頂是左指針 轉(zhuǎn)向右子樹 重新回到while,沒找到值為x的結(jié)點,在C+環(huán)境下演示創(chuàng)建二叉樹及在建立的二叉樹上完成各項操作的bt_main.cpp。,10.2 Binary Search Trees,Can we find an implementation for ordered lists in which we can search quickly (as with binary search on a contiguous list) an

11、d in which we can make insertions and deletions quickly (as with a linked list)?,A binary search tree is a binary trees that is either empty or in which the data entry of every node has a key and satisfies the conditions: 1. The key of the root (if it exists) is greater than the key in any node in t

12、he left subtree of the root. 2. The key of the root (if it exists) is less than the key in any node in the right subtree of the root. 3. The left and right subtrees of the root are again binary search trees.,binary search tree Definitions pg.445,binary searchtree not binary searchtree,DEFINITION A b

13、inary search tree is a binary tree that is either empty or in which the data entry of every node has a key and satises the conditions: 1. The key of the left child of a node (if it exists) is less than the key of its parent node. 2. The key of the right child of a node (if it exists) is greater than

14、 the key of its parent node. 3. The left and right subtrees of the root are again binary search trees.,error,error,We always require: No two entries in a binary search tree may have equal keys., We can regard binary search trees as a new ADT. We may regard binary search trees as a specialization of

15、binary trees. We may study binary search trees as a new implementation of the ADT ordered list. The binary search tree class will be derived from the binary tree class; hence all binary tree methods are inherited.,1. Ordered Lists and Implementations pg.446,The Binary Search Tree Class pg.446,templa

16、te class Search_tree:public Binary_tree public: Error_code insert(const Record ,The inherited methods include the constructors, the destructor,clear, empty, size, height, and the traversals preorder, inorder,and postorder.,A binary search tree also admits specialized methods called insert, remove, a

17、nd tree search.,The class Record has the behavior outlined in Chapter 7: Each Record is associated with a Key. The keys can be compared with the usual comparison operators. By casting records to their corresponding keys, the comparison operators apply to records as well as to keys.,2. Tree Search pg

18、.447,Error_code Search_tree: tree_search(Record Post: If there is an entry in the tree whose key matches that in target, the parameter target is replaced by the corresponding record from the tree and a code of success is returned. Otherwise a code of not_present is returned.,This method will often b

19、e called with a parameter target that contains only a key value. The method will fill target with the complete data belonging to any corresponding Record in the tree.,To search for the target, we first compare it with the entry at the root of the tree. If their keys match, then we are finished. Othe

20、rwise, we go to the left subtree or right subtree as appropriate and repeat the search in that subtree.,We program this process by calling an auxiliary recursive function.,The process terminates when it either finds the target or hits an empty subtree., The auxiliary search function returns a pointe

21、r to the node that contains the target back to the calling program. Since it is private in the class, this pointer manipulation will not compromise tree encapsulation.,Binary_node* Search_tree: search_for_node(Binary_node *sub_root, const Record tree_search usually performs almost as well as binary

22、search.,3.Insertion into a Binary Search Tree pg.451,Error_code Search tree: insert(const Record Post: If a Record with a key matching that of new data already belongs to the Search tree a code of duplicate_error is returned. Otherwise, the Record new data is inserted into the tree in such a way tha

23、t the properties of a binary search tree are preserved, and a code of success is returned.,Method for Insertion,template Error_code Search_tree:insert(const Record ,“空”BST 直接插入(根結(jié)點),尋找 插入位置,插入數(shù)據(jù)小于 當前(子樹根)結(jié)點數(shù)據(jù) 繼續(xù)在左子樹中 搜尋插入位置,在右子樹中 搜尋插入位置,直至到達一個空BST 子樹，脫離循環(huán)；這時 插入結(jié)點應是parent 的孩子,sub_root=new Binary_node

24、(new_data); if(new_datadata) parent-left=sub_root; else parent-right = sub_root; return success; ,根據(jù)插入結(jié)點值 確定應是parent 的左孩子還是右孩子？,The method insert can usually insert a new node into a random binary search tree with n nodes in O(n) steps. It is possible, but extremely unlikely, that a random tree may

25、degenerate so that insertions require as many as n steps. If the keys are inserted in sorted order into an empty tree, however, this degenerate case will occur.,See pg.453 Theorem 10.1 and Corollary 10.2,When a binary search tree is traversed in inorder, the keys will come out in sorted order. This

26、is the basis for a sorting method, called treesort: Take the entries to be sorted, use the method insert to build them into a binary search tree, and then use inorder traversal to put them out in order.,Theorem 10.1 Treesort makes exactly the same comparisons of keys as does quicksort when the pivot

27、 for each sublist is chosen to be the first key in the sublist.,4. Treesort pg.453,Corollary 10.2 In the average case, on a randomly ordered list of length n, treesort performs comparisons of keys.,First advantage of treesort over quicksort: The nodes need not all be available at the start of the pr

28、ocess, but are built into the tree one by one as they become available. Second advantage: The search tree remains available for later insertions and removals. Drawback: If the keys are already sorted, then treesort will be a disaster- the search tree it builds will reduce to a chain. Treesort should

29、 never be used if the keys are already sorted,or are nearly so.,5.Removal from a Binary Search Tree pg.455,從二叉查找(搜索/排序)樹中刪除一個結(jié)點，不能把以該結(jié)點為根的子樹都刪除，只能刪掉該結(jié)點，并且還應該保證刪除后得到的二叉樹仍然滿足二叉查找樹的性質(zhì)，即在二叉查找樹中刪除一個結(jié)點相當于刪去有序序列中的一個結(jié)點。那么，如何在二叉查找樹上刪去一個結(jié)點呢? 如上頁圖所示：當被刪結(jié)點是葉子或僅有一棵子樹時，情況較簡單，只是修改其雙親結(jié)點的指針就可以了；若被刪結(jié)點既有左子樹也有右子樹時，應當如何

30、處理呢？假設在二叉查找樹上被刪結(jié)點為P(指向結(jié)點的指針為p)，其雙親結(jié)點為F(結(jié)點指針為f)，且不失一般性，可設p是f的左指針，即被刪結(jié)點P是F的左孩子。一種處理方法如下頁圖所示：以被刪結(jié)點的左子樹中最大結(jié)點S(必然是葉子)的數(shù)據(jù)代替被刪結(jié)點P的數(shù)據(jù)，然后刪除葉子S。,Auxiliary Function to Remove One Node:,template Error_code Search_tree: remove_root(Binary_node* ,注意：sub_root 一定是引用參數(shù),sub_root只有左 子樹,以左孩子做為 刪除后子樹的新根,sub_root只有右 子樹,以

31、右孩子做為 刪除后子樹的新根,sub_root既有左 子樹,也有右子樹. 搜尋它的左子樹 中最大結(jié)點,令to_delete移動到 sub_root的左孩子,指針parent 保持跟蹤to_delete 是它的雙親結(jié)點,在sub_root所指 結(jié)點的左子樹中 搜尋最大結(jié)點 (此結(jié)點是它的前驅(qū)) 脫離循環(huán)to_delete 指向找到的結(jié)點,將to_delete所指結(jié)點 的數(shù)據(jù)域轉(zhuǎn)移到 sub_root所指結(jié)點,If sub_root is NULL a code of not_present is returned. Otherwise, the root of the subtree is re

32、moved in such a way that the properties of a binary search tree are preserved. The parameter sub_root is reset as the root of the modified subtree, and success is returned.,if(parent=sub_root) sub_root -left=to_delete-left; else parent-right=to_delete-left; / end else(2) delete to_delete; return suc

33、cess; ,to_delete是sub_root 的左孩子它沒有右子樹, 因此,將to_delete所指結(jié)點 的左子樹做為sub_root (parent)的左子樹,將to_delete所指結(jié)點 的左子樹做為parent的右子樹,Remove to_delete from tree,Removal Method:,template Error_code Search_tree:remove(const Record ,Recursive function: search_and_destroy,template Error_code Search_tree: search_and_destr

34、oy(Binary_node* ,按target值向左(右)子樹遞歸 調(diào)用搜尋被刪結(jié)點.sub_root的 左(右)孩子域做為遞歸調(diào)用參數(shù), 這樣當?shù)竭_邊界調(diào)用remove_root時 sub_root的地址就可以由引用參數(shù) 帶回到其雙親結(jié)點的左(右)孩子域,10.3 Building a Balanced Binary Search Tree,Problem: Start with an ordered list and build its entries into a binary search tree that is nearly balanced (bushy).,If the no

35、des of a complete binary tree are labeled in inorder sequence, starting with 1, then each node is exactly as many levels above the leaves as the highest power of 2 that divides its label.,由于課時不夠，本節(jié)刪略。 感興趣的同學可以自學。 See Pg 463-472,10.4 Height Balance: AVL Trees,1.Denition: An AVL tree is a binary searc

36、h tree in which the heights of the left and right subtrees of the root differ by at most 1 and in which the left and right subtrees are again AVL trees. With each node of an AVL tree is associated a balance factor that is left higher, equal, or right higher according, respectively, as the left subtr

37、ee has height greater than, equal to, or less than that of the right subtree.,平衡因子,中文教材中，平衡因子左子樹高度右子樹高度；因此AVL定義為BST中任一結(jié)點平衡因子的絕對值 1。,平衡,左高1,左高2,右高2,enum Balance_factor left_higher, equal_height, right_higher ;,本教材中，將平衡因子定義為“枚舉”類型。,AVL_node: pg.475,template struct AVL_node: public Binary_node Balance_

38、factor balance; AVL_node() balance = equal_height; left = right = NULL; AVL_node(const Record ,inherit,data member,constructor,constructor, In a Binary_node, left and right have type Binary_node*, so the inherited pointer members of an AVL node have this type too, not the more restricted AVL node *.

39、 In the insertion method,we must make sure to insert only genuine AVL nodes. The benefit of implementing AVL nodes with a derived structure is the reuse of all of our functions for processing nodes of binary trees and search trees., We often invoke these methods through pointers to nodes,such as lef

40、t-get_balance( ). But left could (for the compiler) point to any Binary_node, not just to an AVL_node, and these methods are declared only for AVL_node. A C+ compiler must reject a call such as left-get balance( ), since left might point to a Binary node that is not an AVL_node., To enable calls suc

41、h as left-get_balance( ), we include dummy versions of get_balance( ) and set_balance( ) in the underlying Binary_node structure. These do nothing:,template void Binary_node:set_balance(Balance_factor b) template Balance_factor Binary_node:get_balance(Balance_factor b) return equal_height; ,Class De

42、claration for AVL Trees,template class AVL_tree: public Search_tree public: Error_code insert(const Record ,Error_code remove_avl(Binary_node *,2.Insertions of a Node,See pg.478 Fig. 10.18 Simple insertions of nodes into an AVL tree,AVL insertions requiring rotations (pg.483 Fig.10.21),Public Insert

43、ion Method,template Error_code AVL_tree: insert(const Record ,Post: If the key of new_data is already in the AVL_tree, a code of duplicate_error is returned. Otherwise, a code of success is returned and the Record new_data is inserted into the tree in such a way that the properties of an AVL tree ar

44、e preserved. Uses: avl_insert.,Has the tree grown in height?,Recursive Function Specifications,template Error_code AVL_tree: avl_insert ( Binary_node * if (taller = true),Insert into empty subtree,duplicate_error,Insert in left subtree,Recursive call self,left subtree is taller,switch (sub_root-get_

45、balance() case left_higher: left_balance(sub_root); taller = false; break; case equal_height: sub_root-set_balance(left_higher); break; case right_higher: sub_root-set_balance(equal_height); taller = false; break; / end switch / end insert to left subtree (if block) else,Change balance factors,Left

46、subtree already Is taller,Re balancing always shortens the tree,Old left subtree Is equal height,left subtree Is taller,Insert in right subtree, result = avl_insert(sub_root-right, new_data, taller); if( taller = true ) switch(sub_root-get_balance() case left_higher: sub_root-set_balance(equal_heigh

47、t); taller = false; break; case equal_height: sub_root-set_balance(right_higher); break; case right_higher: right_balance(sub_root); taller = false; break; / end switch / end insert to right subtree (else block) return result; ,Old left subtree Is taller,ok!,Old left subtree Is equal height,right su

48、btree already Is taller,Rotations of an AVL Tree (pg.480 Fig.10.19),Rotations of an AVL Tree,template void AVL_tree: rotate_left(Binary_node * ,sub_root points to a subtree of the AVL_tree,This subtree has a non empty right subtree,impossible cases,impossible cases,The new balance factors for root a

49、nd right tree depend on the previous balance factor for sub tree:,Double Rotation,balance of an AVL Tree,template void AVL_tree: right_balance(Binary_node *,sub_root points to a subtree of an AVL_tree that is doubly unbalanced on the right,single rotation left,impossible cases,case left_higher: Bina

50、ry_node *sub_tree = right_tree-left; switch (sub_tree-get_balance() / switch(2) case equal_height: sub_root-set_balance(equal_height); right_tree-set_balance(equal_height); break; case left_higher: sub_root-set_balance(equal_height); right_tree-set_balance(right_higher); break; case right_higher: su

51、b_root-set_balance(left_higher); right_tree-set_balance(equal_height); break; / end switch(2),double rotation left,sub_tree-set_balance(equal_height); rotate_right(right_tree); rotate_left(sub_root); / end switch ,3.Removal of a Node,1. Reduce the problem to the case when the node x to be removed ha

52、s at most one child. 2. Delete x. We use a bool variable shorter to show if the height of a subtree has been shortened. 3. While shorter is true do the following steps for each node p on the path from the parent of x to the root of the tree. When shorter becomes false, the algorithm terminates.,4. C

53、ase 1: Node p has balance factor equal. The balance factor of p is changed according as its left or right subtree has been shortened, and shorter becomes false.,5. Case 2: The balance factor of p is not equal, and the taller subtree was shortened. Change the balance factor of p to equal, and leave s

54、horter as true.,6. Case 3: The balance factor of p is not equal, and the shorter subtree was shortened. Apply a rotation as follows to restore balance. Let q be the root of the taller subtree of p. 7. Case 3a: The balance factor of q is equal. A single rotation restores balance, and shorter becomes

55、false.,8. Case 3b: The balance factor of q is the same as that of p. Apply a single rotation, set the balance factors of p and q to equal, and leave shorter as true.,9. Case 3c: The balance factors of p and q are opposite. Apply a double rotation (rst around q , then around p), set the balance facto

56、r of the new root to equal and the other balance factors as appropriate, and leave shorter as true.,See pg.486 Fig. 10.22,See pg.487 Fig. 10.23,4. The height of an AVL Tree pg.485, The number of recursive calls to insert a new node can be as large as the height of the tree. At most one (single or do

57、uble) rotation will be done per insertion. A rotation improves the balance of the tree, so later insertions are less likely to require rotations. It is very difcult to nd the height of the average AVL tree,but the worst case is much easier. The worst-case behavior of AVL trees is essentially no wors

58、e than the behavior of random search trees. Empirical evidence suggests that the average behavior of AVL trees is much better than that of random trees, almost as good as that which could be obtained from a perfectly balanced tree.,Worst-Case AVL Trees, To find the maximum height of an AVL tree with

59、 n nodes, we instead find the minimum number of nodes that an AVL tree of height h can have. Let Fh be such a tree, with left and right subtrees Fl and Fr . Then one of Fl and Fr , say Fl , has height h - 1 and the minimum number of nodes in such a tree, and Fr has height h - 2 with the minimum number of nodes. These trees, as sparse