數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(25) 二分查找樹

1、11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 1Binary Search Trees P444nP445 DEFINITION: A binary search tree (二分查找樹二分查找樹) is a binary tree that is either empty or in which the data entry of every node has a key and satisfies the conditions:n1. The key of the left child of a node (if it exists) is less than the key of its pa

2、rent node.n2. The key of the right child of a node (if it exists) is greater than the key of its parent node.n3. The left and right subtrees of the root are again binary search trees.11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 2Binary Search TreesnNo two entries in a binary search tree may have equal keys.nWe may regard bi

3、nary search trees as a specialization of binary trees.n同時二分查找樹主要用于構(gòu)建ordered List。方便對關(guān)鍵碼的查找。P44611/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 3Binary Search Trees數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)ntemplate nclass Search_tree: public Binary_tree npublic:nError_code insert(const Record &new_data);nError_code remove(const Record &target);nError_c

4、ode tree_search(Record &target) const;nprivate: / Add auxiliary function prototypes here.n;11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 4Implement of Binary Search Trees10.2.2 Tree search 查找操作查找操作nError_code tree_search(Record &target) const;n方法：方法：n將將target與樹根節(jié)點比較，如果相等則找到，程序結(jié)束。與樹根節(jié)點比較，如果相等則找到，程序結(jié)束。n如果比根節(jié)點大，則進(jìn)入右子樹繼續(xù)

5、查找。如果比根節(jié)點大，則進(jìn)入右子樹繼續(xù)查找。n如果比根節(jié)點小，則進(jìn)入左子樹繼續(xù)查找。如果比根節(jié)點小，則進(jìn)入左子樹繼續(xù)查找。11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 5Implement of Binary Search Trees10.2.2 Tree search 查找操作查找操作 P447Example：查找：查找Kim的過程的過程11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 6Implement of Binary Search TreesTree search 查找操作查找操作 實現(xiàn)實現(xiàn)n#include Binary_tree.cppntemplate nclass Search_tree:

6、 public Binary_tree npublic:nError_code insert(const Record &new_data);nError_code remove(const Record &target);nError_code tree_search(Record &target /* out */) const;n /查找成功，查找成功，target的內(nèi)容為查找樹種節(jié)點的信息。返回的內(nèi)容為查找樹種節(jié)點的信息。返回success。n /查找失敗，返回查找失敗，返回notPresentnprivate: / Add auxiliary function

7、 prototypes here. Binary_node * search_for_node(Binary_node* sub_root, const Record &target) const; P448;11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 7Tree search 查找操作查找操作 實現(xiàn)實現(xiàn)Binary_node * search_for_node(Binary_node* sub_root, const Record &target) const; P448nsearch_for_node是一個查找子函數(shù)。是一個查找子函數(shù)。nSub_root: 為空或者指向一棵子樹

8、。為空或者指向一棵子樹。nPostcondition: 當(dāng)當(dāng)target不在子樹不在子樹sub_root中存在時，返回中存在時，返回NULL，當(dāng)找到當(dāng)找到target時返回指向時返回指向target的指針。的指針。11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 8Implement of Binary Search Trees查找操作查找操作 實現(xiàn)實現(xiàn)template Error_code Search_tree : tree_search(Record &target) constError_code result = success;Binary_node *found = search_

9、for_node(root, target);if (found = NULL)result = not_present;elsetarget = found-data;return result;11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 9Implement of Binary Search Trees查找操作查找操作 實現(xiàn)實現(xiàn)-遞歸遞歸template Binary_node *Search_tree : search_for_node(Binary_node* sub_root, const Record &target) constif (sub_root = NULL | su

10、b_root-data = target)return sub_root;else if (sub_root-data right, target);else return search_for_node(sub_root-left, target);11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 10Implement of Binary Search Trees查找操作查找操作 實現(xiàn)實現(xiàn) 非遞歸非遞歸/Nonrecursive version:template Binary_node *Search_tree : search_for_node(Binary_node* sub_root, con

11、st Record &target) constwhile (sub_root != NULL & sub_root-data != target)if (sub_root-data right;else sub_root = sub_root-left;return sub_root;11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 11查找操作查找操作 實現(xiàn)分析實現(xiàn)分析 P449頁頁 需要注意：同樣的關(guān)鍵碼，可能產(chǎn)生很多不同的查找樹需要注意：同樣的關(guān)鍵碼，可能產(chǎn)生很多不同的查找樹結(jié)構(gòu)。圖結(jié)構(gòu)。圖(a) (b) (c) (d) (e)為由七個字母構(gòu)成的二分為由七個字母構(gòu)成的二分查找樹的

12、結(jié)構(gòu)。查找樹的結(jié)構(gòu)。對于查找操作對于查找操作:整棵樹越濃密，則查找操作的效率越高。整棵樹越濃密，則查找操作的效率越高。 最好的結(jié)構(gòu)最好的結(jié)構(gòu)最常見的結(jié)構(gòu)最常見的結(jié)構(gòu)11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 12查找操作查找操作 實現(xiàn)分析實現(xiàn)分析 P449頁頁最壞的結(jié)構(gòu)最壞的結(jié)構(gòu)11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 1310.2.3 Insert into a Binary Search Tree 二分查找樹的插入操作n向二分查找樹中插入節(jié)點的過程分析：向二分查找樹中插入節(jié)點的過程分析：l如果二叉查找樹為空，則新結(jié)點作為根結(jié)點。如果二叉查找樹為空，則新結(jié)點作為根結(jié)點。l如果二叉查找樹非空，則將新

13、結(jié)點的關(guān)鍵碼與根結(jié)如果二叉查找樹非空，則將新結(jié)點的關(guān)鍵碼與根結(jié)點的關(guān)鍵碼比較：點的關(guān)鍵碼比較：l若相等表示該結(jié)點已在二叉排序樹中插入失??；若相等表示該結(jié)點已在二叉排序樹中插入失??；l若小于根結(jié)點的關(guān)鍵碼，則將新結(jié)點插入到根結(jié)點的左子若小于根結(jié)點的關(guān)鍵碼，則將新結(jié)點插入到根結(jié)點的左子樹中；樹中；l否則，插入到右子樹中。否則，插入到右子樹中。l 子樹中的插入過程和樹中的插入過程相同，如此進(jìn)子樹中的插入過程和樹中的插入過程相同，如此進(jìn)行下去，直到找到該結(jié)點，或者直到左或右子樹為行下去，直到找到該結(jié)點，或者直到左或右子樹為空二叉樹，新結(jié)點插入成為葉子結(jié)點為止?？斩鏄?，新結(jié)點插入成為葉子結(jié)點為止。11

14、/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 14P451 e,b,d,f,a,g,c逐一插入的過程逐一插入的過程11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 1510.2.3 Insert into a Binary Search Tree 插入操作分析n(1) 不同的插入序列可能會產(chǎn)生相同的二不同的插入序列可能會產(chǎn)生相同的二分查找樹的結(jié)構(gòu)。分查找樹的結(jié)構(gòu)。n如如 e,f,g,b,a,d,c and e,b,d,c,a,f,gn(2) 如果插入的序列已經(jīng)有序，那么生成如果插入的序列已經(jīng)有序，那么生成的查找樹的結(jié)構(gòu)是最壞的。的查找樹的結(jié)構(gòu)是最壞的。n如如a,b,c,d,e,f,g, 將生成圖將生成圖10.8(

15、e)的結(jié)構(gòu)的結(jié)構(gòu)11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 16Implement of Binary Search TreesTree search 插入操作插入操作 實現(xiàn)實現(xiàn)n#include Binary_tree.cppntemplate nclass Search_tree: public Binary_tree npublic:nError_code insert(const Record &new_data);nn Error_code remove(const Record &target);nError_code tree_search(Record &t

16、arget /* out */) const;n nprivate: / Add auxiliary function prototypes here. Error_code search_and_insert( Binary_node * &sub_root, const Record &new_data);11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 17Implement of Binary Search Trees插入操作插入操作 實現(xiàn)實現(xiàn)template Error_code Search_tree : insert( const Record &new_data)

17、/插入成功返回插入成功返回 success /插入失敗返回插入失敗返回 duplicate_errorError_code result=search_and_insert(root, new_data);if(result=success)count+;return result;11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 18Implement of Binary Search Trees插入操作插入操作 實現(xiàn)實現(xiàn)template Error_code Search_tree : search_and_insert( Binary_node * &sub_root /*inout*/,

18、 const Record &new_data /*in*/)if (sub_root = NULL) sub_root = new Binary_node(new_data);return success;else if (new_data data)return search_and_insert(sub_root-left, new_data);else if (new_data sub_root-data)return search_and_insert(sub_root-right, new_data);else return duplicate_error;11/23/20

19、21數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 1910.2.4 Tree sort n對于一棵二叉查找樹，中序遍歷的序列即為有對于一棵二叉查找樹，中序遍歷的序列即為有序序列。序序列。n因此，二叉查找樹的插入過程也可以看成是排因此，二叉查找樹的插入過程也可以看成是排序的過程。即序的過程。即n首先，將無序序列逐一插入二叉排序樹。首先，將無序序列逐一插入二叉排序樹。n然后，對二叉排序樹進(jìn)行中序遍歷。完成排序然后，對二叉排序樹進(jìn)行中序遍歷。完成排序nTree sort比較適合于無序的序列，對于基本有比較適合于無序的序列，對于基本有序的序列效率較低序的序列效率較低11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 2010.2.5 Re

20、moval from a Binary Search Tree 刪除操作討論n（1） 刪除的節(jié)點是葉子結(jié)點：replace the link to the removed node by NULL.11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 2110.2.5 Removal from a Binary Search Tree 刪除操作討論n（2） 刪除的節(jié)點只有一棵非空子樹：Adjust the link from the parent of the removed node to point to the root of the nonempty subtree.11/23/2021數(shù)據(jù)結(jié)構(gòu)與程

21、序設(shè)計 2210.2.5 Removal from a Binary Search Tree 刪除操作討論n（3） 刪除的節(jié)點左右子樹都非空：找到被刪除節(jié)點的中序遍歷的前驅(qū)（左子樹中最右邊的孩子），用前驅(qū)節(jié)點代替被刪除點.11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 23Implement of Binary Search TreesTree search 刪除操作刪除操作 實現(xiàn)實現(xiàn)#include Binary_tree.cpptemplate class Search_tree: public Binary_tree public:。 Error_code remove(const Record

22、 &target);private: / Add auxiliary function prototypes here. Error_code remove_root( Binary_node * &sub_root/*inout*/) Error_code search_and_destroy( Binary_node* &sub_root, const Record &target);11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 24Implement of Binary Search TreesTree search 刪除操作刪除操作 實現(xiàn)實現(xiàn) P456Erro

23、r_code remove_root( Binary_node * &sub_root/*inout*/)/remove_root直接將直接將sub_root指向的節(jié)點從查找樹中刪除。指向的節(jié)點從查找樹中刪除。E.g.If the node at left of x is to be removed, the call should be: remove_root(x-left);If the root of the tree is to be removed, the call should be: remove_root(root);11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 25Im

24、plement of Binary Search Trees刪除操作刪除操作 實現(xiàn)實現(xiàn) P458template Error_code Search_tree : remove(const Record &target)/* Post: If a Record with a key matching that of target belongs to the Search tree a code of success is returned and the corresponding node is removed from thetree. Otherwise, a code of

25、not present is returned.Uses: Function search_and_destroy */Error_code result=search_and_destroy(root, target);if(result=success)count-;return result;11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 26Implement of Binary Search Trees刪除操作刪除操作 實現(xiàn)實現(xiàn) P458template Error_code Search_tree : search_and_destroy( Binary_node* &sub_ro

26、ot, const Record &target)/*Post: If the key of target is not in the subtree, a code of not_present is returned. Otherwise, a code of success is returned and the subtree node containing target has been removed in such a way that the properties of a binary search tree have been preserved.Uses: Fun

27、ctions search and destroy recursively and remove root */if (sub_root = NULL | sub_root-data = target)return remove_root(sub_root);else if (target data)return search_and_destroy(sub_root-left, target);elsereturn search_and_destroy(sub_root-right, target);11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 27刪除操作刪除操作 實現(xiàn)實現(xiàn) P457templa

28、te Error_code Search_tree : remove_root(Binary_node * &sub_root)if (sub_root = NULL) return not_present;Binary_node *to_delete = sub_root; / Remember node to delete at end./處理只有一棵子樹或者沒有孩子節(jié)點的情況處理只有一棵子樹或者沒有孩子節(jié)點的情況 if (sub_root-right = NULL) sub_root = sub_root-left;else if (sub_root-left = NULL) s

29、ub_root = sub_root-right;else / Neither subtree is empty.to_delete = sub_root-left; / Move left to find predecessor. 記錄待刪除的節(jié)點記錄待刪除的節(jié)點Binary_node *parent = sub_root; / parent of to_deletewhile (to_delete-right != NULL) / to_delete is not the predecessor.parent = to_delete;to_delete = to_delete-right; sub_root-data = to_delete-data; / Move from to_delete to root.if (parent = sub_root) sub_root-left = to_delete-left;else parent-right = to_delete-left; delete to_delete; / Remove to_delete from tree.return success;11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序