首页 > 代码库 > 算法导论-----------二叉搜索树
算法导论-----------二叉搜索树
先上二叉树查找树的删除的代码,因为删除是二叉查找树最复杂的操作:
int BinarySearchTree<T>::tree_remove(const T& elem) { BinarySearchTreeNode<T> *z = tree_search(elem);//根据元素查找到要删除的节点 BinarySearchTreeNode<T> *x, *y; if (z != NULL) { //用y来表示实际要删除的节点 if (z->left == NULL || z->right == NULL)//最多只有一个儿子节,要么没有儿子节点 y = z; else y = tree_search(tree_successor(elem));//有两个儿子的时候实际删除的是后继节点 //因为有上面的if语句,所以y要么只有一个儿子,要么没有儿子。后继节点只有右儿子或者没有儿子 //所以x要么是儿子节点,要么是空节点 if (y->left != NULL) x = y->left; else x = y->right; if (x != NULL)//判断y节点有没有儿子节点,有的花就把y节点的父节点变成x的父节点。 x->parent = y->parent; //y是根节点或者不是根节点的情况 if (y->parent == NULL) root = x; else if (y == y->parent->left)//如果y节点不是根节点的情况该怎么处理呢? y->parent->left = x; else y->parent->right = x; //处理后继节点的情况,因为y表示后继的时候y!=z; if (y != z) z->elem = y->elem; delete y; } return -1; }
二叉查找树的概念及操作。主要内容包括二叉查找树的性质,如何在二叉查找树中查找最大值、最小值和给定的值,如何找出某一个元素的前驱和后继,如何在二叉查找树中进行插入和删除操作。在二叉查找树上执行这些基本操作的时间与树的高度成正比,一棵随机构造的二叉查找树的期望高度为O(lgn),从而基本动态集合的操作平均时间为θ(lgn)。
1、二叉查找树
二叉查找树是按照二叉树结构来组织的,因此可以用二叉链表结构表示。二叉查找树中的关键字的存储方式满足的特征是:设x为二叉查找树中的一个结点。如果y是x的左子树中的一个结点,则key[y]≤key[x]。如果y是x的右子树中的一个结点,则key[x]≤key[y]。根据二叉查找树的特征可知,采用中根遍历一棵二叉查找树,可以得到树中关键字有小到大的序列。
一棵二叉树查找及其中根遍历结果如下图所示:
书中给出了一个定理:如果x是一棵包含n个结点的子树的根,则其中根遍历运行时间为θ(n)。
问题:二叉查找树性质与最小堆之间有什么区别?能否利用最小堆的性质在O(n)时间内,按序输出含有n个结点的树中的所有关键字?
2、查询二叉查找树
二叉查找树中最常见的操作是查找树中的某个关键字,除了基本的查询,还支持最大值、最小值、前驱和后继查询操作,书中就每种查询进行了详细的讲解。
(1)查找SEARCH
在二叉查找树中查找一个给定的关键字k的过程与二分查找很类似,根据二叉查找树在的关键字存放的特征,很容易得出查找过程:首先是关键字k与树根的关键字进行比较,如果k大比根的关键字大,则在根的右子树中查找,否则在根的左子树中查找,重复此过程,直到找到与遇到空结点为止。例如下图所示的查找关键字13的过程:(查找过程每次在左右子树中做出选择,减少一半的工作量)
书中给出了查找过程的递归和非递归形式的伪代码:
TREE_SEARCH(x,k) if x=NULL or k=key[x] then return x if(k<key[x]) then return TREE_SEARCH(left[x],k) else then return TREE_SEARCH(right[x],k)
ITERATIVE_TREE_SEARCH(x,k) while x!=NULL and k!=key[x] do if k<key[x] then x=left[x] else then x=right[x] return x
(2)查找最大关键字和最小关键字
根据二叉查找树的特征,很容易查找出最大和最小关键字。查找二叉树中的最小关键字:从根结点开始,沿着各个节点的left指针查找下去,直到遇到NULL时结束。如果一个结点x无左子树,则以x为根的子树中,最小关键字就是key[x]。查找二叉树中的最大关键字:从根结点开始,沿着各个结点的right指针查找下去,直到遇到NULL时结束。书中给出了查找最大最小关键字的伪代码:
TREE_MINMUM(x) while left[x] != NULL do x=left[x] return x
TREE_MAXMUM(x) while right[x] != NULL do x= right[x] return x
(3)前驱和后继
给定一个二叉查找树中的结点,找出在中序遍历顺序下某个节点的前驱和后继。如果树中所有关键字都不相同,则某一结点x的前驱就是小于key[x]的所有关键字中最大的那个结点,后继即是大于key[x]中的所有关键字中最小的那个结点。根据二叉查找树的结构和性质,不用对关键字做任何比较,就可以找到某个结点的前驱和后继。
查找前驱步骤:先判断x是否有左子树,如果有则在left[x]中查找关键字最大的结点,即是x的前驱。如果没有左子树,则从x继续向上执行此操作,直到遇到某个结点是其父节点的右孩子结点。例如下图查找结点7的前驱结点6过程:
查找后继步骤:先判断x是否有右子树,如果有则在right[x]中查找关键字最小的结点,即使x的后继。如果没有右子树,则从x的父节点开始向上查找,直到遇到某个结点是其父结点的左儿子的结点时为止。例如下图查找结点13的后继结点15的过程:
书中给出了求x结点后继结点的伪代码:
TREE_PROCESSOR(x) if right[x] != NULL then return TREE_MINMUM(right(x)) y=parent[x] while y!= NULL and x ==right[y] do x = y y=parent[y] return y
定理:对一棵高度为h的二叉查找,动态集合操作SEARCH、MINMUM、MAXMUM、SUCCESSOR、PROCESSOR等的运行时间均为O(h)。
3、插入和删除
插入和删除会引起二叉查找表示的动态集合的变化,难点在在插入和删除的过程中要保持二叉查找树的性质。插入过程相当来说要简单一些,删除结点比较复杂。
(1)插入
插入结点的位置对应着查找过程中查找不成功时候的结点位置,因此需要从根结点开始查找带插入结点位置,找到位置后插入即可。下图所示插入结点过程:
书中给出了插入过程的伪代码:
TREE_INSERT(T,z) y = NULL; x =root[T] while x != NULL do y =x if key[z] < key[x] then x=left[x] else x=right[x] parent[z] =y if y=NULL then root[T] =z else if key[z]>key[y] then keft[y] = z else right[y] =z
插入过程运行时间为O(h),h为树的高度。
(2)删除
从二叉查找树中删除给定的结点z,分三种情况讨论:
<1>结点z没有左右子树,则修改其父节点p[z],使其为NULL。删除过程如下图所示:
<2>如果结点z只有一个子树(左子树或者右子树),通过在其子结点与父节点建立一条链来删除z。删除过程如下图所示:
<3>如果z有两个子女,则先删除z的后继y(y没有左孩子),在用y的内容来替代z的内容。
书中给出了删除过程的伪代码:
TREE_DELETE(T,z) if left[z] ==NULL or right[z] == NULL then y=z else y=TREE_SUCCESSOR(z) if left[y] != NULL then x=left[y] else x=right[y] if x!= NULL then parent[x] = parent[y] if p[y] ==NULL then root[T] =x else if y = left[[prarnt[y]] then left[parent[y]] = x else right[parent[y]] =x if y!=z then key[z] = key[y] copy y's data into z return y
定理:对高度为h的二叉查找树,动态集合操作INSERT和DELETE的运行时间为O(h)。
4、实现测试
采用C++语言实现一个简单的二叉查找树,支持动态集合的基本操作:search、minmum、maxmum、predecessor、successor、insert和delete。设计的二叉查找树结构如下所示:
template<class T> class BinarySearchTreeNode { public: T elem; BinarySearchTreeNode<T> *parent; BinarySearchTreeNode<T> *left; BinarySearchTreeNode<T> *right; }; template<class T> class BinarySearchTree { public: BinarySearchTree(); void tree_insert(const T& elem); int tree_remove(const T& elem); BinarySearchTreeNode<T> *tree_search(const T& elem) const; T tree_minmum(BinarySearchTreeNode<T>* root) const; T tree_maxmum(BinarySearchTreeNode<T>* root) const; T tree_successor(const T& elem) const; T tree_predecessor(const T& elem) const; int empty() const; void inorder_tree_walk() const; BinarySearchTreeNode<T>* get_root() { return root; } private: BinarySearchTreeNode<T>* root; };
完整程序如下所示:
#include<iostream> #include<stack> using namespace std; /*-----------------------------------------------------------------------------------------------*/ /*采用C++语言实现一个简单的二叉查找树,支持动态集合的基本操作: */ /*search、minmum、maxmum、predecessor、successor、insert和delete。设计的二叉查找树结构如下所示: */ /*------------------------------------------------------------------------------------------------*/ template<class T> class BinarySearchTreeNode { public: T elem; BinarySearchTreeNode<T> *parent; BinarySearchTreeNode<T> *left; BinarySearchTreeNode<T> *right; }; template<class T> class BinarySearchTree { public: BinarySearchTree(); void tree_insert(const T& elem); int tree_remove(const T& elem); BinarySearchTreeNode<T> *tree_search(const T& elem) const; T tree_minmum(BinarySearchTreeNode<T>* root) const; T tree_maxmum(BinarySearchTreeNode<T>* root) const; T tree_successor(const T& elem) const; T tree_predecessor(const T& elem) const; int empty() const; void inorder_tree_walk() const; BinarySearchTreeNode<T>* get_root() { return root; } private: BinarySearchTreeNode<T>* root; }; //构造函数,初始化二叉查找树。 template <class T> BinarySearchTree<T>::BinarySearchTree() { root = NULL; } template <class T> void BinarySearchTree<T>::tree_insert(const T& elem) { if (!empty()) { BinarySearchTreeNode<T> *p_node = root; BinarySearchTreeNode<T> *q_node = NULL; BinarySearchTreeNode<T> *new_node = new BinarySearchTreeNode<T>; new_node->elem = elem; new_node->left = NULL; new_node->right = NULL; new_node->parent = NULL; while (p_node) { q_node = p_node; if (p_node->elem > elem) p_node = p_node->left; else p_node = p_node->right; }//当p_node为空的时候,q_node正好是正确的插入位置的父节点,且q_node是叶节点. if (q_node->elem > elem) q_node->left = new_node; else q_node->right = new_node; new_node->parent = q_node; } else { root = new BinarySearchTreeNode<T>; root->elem = elem; root->parent = NULL; root->left = NULL; root->right = NULL; } } //二叉查找树节点的删除 template <class T> int BinarySearchTree<T>::tree_remove(const T& elem) { BinarySearchTreeNode<T> *z = tree_search(elem); BinarySearchTreeNode<T> *x, *y; if (z != NULL) { //用y来表示实际要删除的节点 if (z->left == NULL || z->right == NULL)//最多只有一个儿子节,要么没有儿子节点 y = z; else y = tree_search(tree_successor(elem));//有两个儿子的时候实际删除的是后继节点 //因为有上面的if语句,所以y要么只有一个儿子,要么没有儿子。后继节点只有右儿子或者没有儿子 //所以x要么是儿子节点,要么是空节点 if (y->left != NULL) x = y->left; else x = y->right; if (x != NULL) x->parent = y->parent; if (y->parent == NULL) root = x; else if (y == y->parent->left) y->parent->left = x; else y->parent->right = x; //处理后继节点的情况,因为y表示后继的时候y!=z; if (y != z) z->elem = y->elem; delete y; } return -1; } // BinarySearchTreeNode<T>* 返回类型,返回查找元素elem的节点 template <class T> BinarySearchTreeNode<T>* BinarySearchTree<T>::tree_search(const T& elem) const { BinarySearchTreeNode<T> *pnode = root; while (pnode) { if (pnode->elem == elem) break; else if (pnode->elem > elem) pnode = pnode->left; else pnode = pnode->right; } return pnode; } //返回最小关键字的元素,可以参考书上用递归方法的写 template <class T> T BinarySearchTree<T>::tree_minmum(BinarySearchTreeNode<T>* root) const { BinarySearchTreeNode<T> *pnode = root; while (pnode->left) pnode = pnode->left; return pnode->elem; } //返回最大关键字的元素,可以改用递归,不过效率降低 template <class T> T BinarySearchTree<T>::tree_maxmum(BinarySearchTreeNode<T>* root) const { BinarySearchTreeNode<T> *pnode = root; while (pnode->right != NULL) pnode = pnode->right; return pnode->elem; } //后继节点 template <class T> T BinarySearchTree<T>::tree_successor(const T& elem) const { BinarySearchTreeNode<T>* pnode = tree_search(elem); BinarySearchTreeNode<T>* parentnode; if (pnode != NULL) { if (pnode->right) return tree_minmum(pnode->right); parentnode = pnode->parent; while (parentnode && pnode == parentnode->right) { pnode = parentnode; parentnode = parentnode->parent; } if (parentnode) return parentnode->elem; else return T(); } return T(); } //前继节点 template <class T> T BinarySearchTree<T>::tree_predecessor(const T& elem)const { BinarySearchTreeNode<T>* pnode = tree_search(elem); BinarySearchTreeNode<T>* parentnode; if (pnode != NULL) { if (pnode->right) return tree_maxmum(pnode->right); parentnode = pnode->parent; while (parentnode && pnode == parentnode->left) { pnode = parentnode; parentnode = pnode->parent; } if (parentnode) return parentnode->elem; else return T(); } return T(); } template <class T> int BinarySearchTree<T>::empty() const { return (NULL == root); } //按照大小顺序输出二叉查找树,即中根遍历的方法输出二叉查找树.使用stack功能的实现。 template <class T> void BinarySearchTree<T>::inorder_tree_walk() const { if (NULL != root) { stack<BinarySearchTreeNode<T>*> s; BinarySearchTreeNode<T> *P_temp; P_temp = root; while (NULL != P_temp || !s.empty()) { if (NULL != P_temp) { s.push(P_temp); P_temp = P_temp->left; } else { P_temp = s.top(); s.pop(); cout << P_temp->elem << " "; P_temp = P_temp->right; } } } } int main() { BinarySearchTree<int> bstree; BinarySearchTreeNode<int>* ptnode, *proot; bstree.tree_insert(32); bstree.tree_insert(21); bstree.tree_insert(46); bstree.tree_insert(54); bstree.tree_insert(16); bstree.tree_insert(38); bstree.tree_insert(70); cout << "inorder tree walk is: "; bstree.inorder_tree_walk(); proot = bstree.get_root(); cout << "\nmax value is: " << bstree.tree_maxmum(proot) << endl; cout << "min value is: " << bstree.tree_minmum(proot) << endl; ptnode = bstree.tree_search(38); if (ptnode) cout << "the element 38 is exist in the binary tree.\n"; else cout << "the element 38 is not exist in the binary tree.\n"; cout << "the successor of 38 is: " << bstree.tree_successor(38) << endl; cout << "the predecessor of 38 is:" << bstree.tree_predecessor(38) << endl; if (bstree.tree_remove(46) == 0) cout << "delete 46 successfully" << endl; else cout << "delete 46 failed" << endl; cout << "inorder tree walk is: "; bstree.inorder_tree_walk(); exit(0); }
程序测试结果如下所示:
二叉查找上各种基本操作的运行时间都是O(h),h为树的高度。但是在元素插入和删除过程中,树的高度会发生改变。如果n个元素按照严格增长的顺序插入,那个构造出的二叉查找树的高度为n-1。例如按照先后顺序插入7、15、18、20、34、46、59元素构造二叉查找树,二叉查找树结构如下所示:
算法导论-----------二叉搜索树