(8.3.1)--ch8-03-二叉排序树的基本概念与查找.pdf

《(8.3.1)--ch8-03-二叉排序树的基本概念与查找.pdf》由会员分享，可在线阅读，更多相关《(8.3.1)--ch8-03-二叉排序树的基本概念与查找.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 Sequential SearchData Structures and Algorithms Basic Concepts and Search of Binary Search Trees Data Structures and AlgorithmsData Structures and AlgorithmsChapter 8 Searchstatic search tablestatic search tableSearchSearch performance,best to achieve performance,best to achieve O(logn)O(logn),the

2、table is the table is orderedorderedInsert and delete Insert and delete performance,best performance,best to achieve to achieve O(1)O(1),chainchain storage storageData Structures and AlgorithmsData Structures and AlgorithmsChapter 8 Search8.2 Tree-based searchThe definition of the The definition of

3、the binary sort tree binary sort tree is:is:the the binary sort tree binary sort tree is either an is either an emptyempty tree;or tree;ora binary tree with the following characteristics:a binary tree with the following characteristics:First,if its left subtree is not empty,then First,if its left su

4、btree is not empty,then all all the node values on the left subtree should be less the node values on the left subtree should be less than the value of the rootthan the value of the root;Third,its Third,its left and right subtrees are also a left and right subtrees are also a binary sort treebinary

5、sort tree.Second,if its right subtree is not Second,if its right subtree is not empty,thenempty,then all all node values on the right subtree should be greater node values on the right subtree should be greater than the value of the root nodethan the value of the root node;binary sort treebinary sor

6、t treeData Structures and AlgorithmsData Structures and Algorithmseg.eg.4 4503080209010854035252388a binary sort treea binary sort tree66NotChapter 8 Search8.2 Tree-based search binary sort treebinary sort treeData Structures and AlgorithmsData Structures and Algorithms550308020908540358832eg.binary

7、 sort treebinary sort treefind the keywordfind the keyword=50,35,90,953080209085403588325050304035508090failChapter 8 Search8.2 Tree-based searchData Structures and AlgorithmsData Structures and AlgorithmsBinary Sort TreeBinary Sort Treesearch processsearch process6First,if the given value is First,

8、if the given value is equal to the key of the equal to the key of the root noderoot node,the,the search is successful search is successful；Second,if the given value is Second,if the given value is less than the key of the less than the key of the root noderoot node,continue to search on the,continue

9、 to search on the leftleft subtree;subtree;Third,if the given value is Third,if the given value is greater than the key of greater than the key of the root nodethe root node,continue to search on the,continue to search on the right right subtree.subtree.otherwise otherwise，If the binary sort tree is

10、 If the binary sort tree is emptyempty,the,the search is search is unsuccessfulunsuccessful；Search in the binary sort tree,similar to Search in the binary sort tree,similar to binary searchbinary searchThe meaning The meaning of sortingof sortingChapter 8 Search8.2 Tree-based searchData Structures a

11、nd AlgorithmsData Structures and AlgorithmsThe search process generates a search pathThe search process generates a search path：Starting from the root node,follow the left branch Starting from the root node,follow the left branch or the right branch down until the node with the or the right branch d

12、own until the node with the key equal to the given valuekey equal to the given valueStarting from the root node,follow theleft branch Starting from the root node,follow theleft branch or the right branch down until the pointer points or the right branch down until the pointer points to the empty tre

13、eto the empty tree Find successfulFind successful Find unsuccessfulFind unsuccessfulBinary Sort TreeBinary Sort Treesearch processsearch processChapter 8 Search8.2 Tree-based searchData Structures and AlgorithmsData Structures and AlgorithmsBinary Sort TreeBinary Sort Tree search search algorithmalg

14、orithm RecursionRecursionBSTree SearchBST(BSTree bst,KeyType key)if(!bst)return NULL;else if(bst-key=key)return bst；else if(key key)return SearchBST(bst-lchild,key);else return SearchBST(bst-rchild,key);Non-recursiveNon-recursive？Chapter 8 Search8.2 Tree-based searchData Structures and AlgorithmsData Structures and AlgorithmsData Structures and AlgorithmsData Structures and Algorithms Thanks!XIAN UNIVERSITY OF POSTS&TELECOMMUNICATIONS Chunmei Wang