二叉检索树

二叉检索树

　　Copyright 2002 by Zhang Ming, PKUCS
　　1. 定义及性质
　　n二叉检索树或者是一颗空树;或者是具
　　有下列性质的二叉树:对于任何一个结
　　点,设其值为K,则该结点的左子树(若
　　不空)的任意一个结点的值都小于K;该
　　结点的右子树(若不空)的任意一个结点
　　的值都大于或等于K;而且它的左右子树
　　也分别为二叉检索树.
　　n二叉检索树的性质: 按照中序周游将各结
　　点打印出来,将得到按照由小到大的排
　　列.
　　Copyright 2002 by Zhang Ming, PKUCS
　　BST图示
　　Copyright 2002 by Zhang Ming, PKUCS
　　检索
　　n二叉检索树的效率就在于只需检索二个子树
　　之一.
　　-从根结点开始,在二叉检索树中检索值K.如果
　　根结点储存的值为K,则检索结束.
　　-如果K小于根结点的值,则只需检索左子树
　　-如果K大于根结点的值,就只检索右子树
　　n这个过程一直持续到K被找到或者我们遇上
　　了一个树叶.
　　n如果遇上树叶仍没有发现K,那么K就不在该
　　二叉检索树中.
　　Copyright 2002 by Zhang Ming, PKUCS
　　2. 二叉检索树类定义
　　// BSTimplementation for the Dictionary ADT
　　template
　　class BST : public Dictionary {
　　private:
　　BinNode* root; // Root of the BST
　　intnodecount; // Number of nodes in the BST
　　// Private "helper" functions
　　void clearhelp(BinNode*);
　　BinNode* inserthelp(BinNode*, const Elem&);
　　BinNode* deletemin(BinNode*,
　　BinNode*&);
　　BinNode* removehelp(BinNode*, const Key&,
　　BinNode*&);
　　boolfindhelp(BinNode*, const Key&, Elem&) const;
　　void printhelp(BinNode*, int) const;
　　Copyright 2002 by Zhang Ming, PKUCS
　　public:
　　BST() { root = NULL; nodecount= 0; } // Constructor
　　~BST() { clearhelp(root); } // Destructor
　　void clear()
　　{ clearhelp(root); root = NULL; nodecount= 0; }
　　boolinsert(constElem& e) {
　　root = inserthelp(root, e);
　　nodecount++; return true;
　　}
　　boolremove(constKey& K, Elem& e) {
　　BinNode* t = NULL;
　　root = removehelp(root, K, t);
　　if (t == NULL) return false; // Nothing found
　　e = t->val(); nodecount--;
　　delete t;
　　return true;
　　}
　　Copyright 2002 by Zhang Ming, PKUCS
　　boolremoveAny(Elem& e) { // Delete min value
　　if (root == NULL) return false; // Empty tree
　　BinNode* t;
　　root = deletemin(root, t);
　　e = t->val();
　　delete t;
　　nodecount--;
　　return true;
　　}
　　boolfind(constKey& K, Elem& e) const
　　{ return findhelp(root, K, e); }
　　intsize() { return nodecount; }
　　void print() const {
　　if (root == NULL) cout<< "The BST is empty.\n";
　　else printhelp(root, 0);
　　}
　　};
　　Copyright 2002 by Zhang Ming, PKUCS
　　3. 二叉检索树的实现
　　n插入中包含检索(可以重码)
　　boolinsert(constElem& e) {
　　root = inserthelp(root, e);
　　nodecount++; return true;
　　}
　　nInserthelp的实现
　　template
　　BinNode* BST::
　　inserthelp(BinNode* subroot, const Elem& val) {
　　if (subroot== NULL) // Empty tree: create node
　　return (new BinNodePtr(val, NULL, NULL));
　　if (EEComp::lt(val, subroot->val())) // Insert on left
　　subroot->setLeft(inserthelp(subroot->left(), val));
　　else subroot->setRight(inserthelp(subroot->right(), val));
　　return subroot; // Return subtreewith node inserted
　　}
　　Copyright 2002 by Zhang Ming, PKUCS
　　BST插入图示
　　Copyright 2002 by Zhang Ming, PKUCS
　　检索
　　template
　　boolBST:: findhelp(
　　BinNode* subroot, const Key& K, Elem&
　　e) const {
　　if (subroot== NULL) return false; // Empty tree
　　else if (KEComp::lt(K, subroot->val())) // Check left
　　return findhelp(subroot->left(), K, e);
　　else if (KEComp::gt(K, subroot->val())) //Check right
　　return findhelp(subroot->right(), K, e);
　　else { e = subroot->val(); return true; } // Found it
　　}
　　Copyright 2002 by Zhang Ming, PKUCS
　　打印
　　template
　　void BST::
　　printhelp(BinNode* subroot, intlevel) const {
　　if (subroot== NULL) return; // Empty tree
　　printhelp(subroot->left(), level+1); //Do left subtree
　　for (inti=0; icout<< " ";
　　cout}
　　Copyright 2002 by Zhang Ming, PKUCS
　　4. 二叉检索树结点的删除
　　n对于二叉检索树,删除一个结点,相当
　　于删除有序序列中的一个记录,要求删
　　除后能保持二叉检索树的排序特性,并
　　且树高变化较小.
　　(1)找到值为val的结点rt
　　(2)rt为叶,可以直接删除
　　(3)rt左空或右空,可以让它的右子树或
　　左子树直接代替原rt
　　(4)rt左右都不空,可以让右子树中的最
　　小值代替原rt
　　Copyright 2002 by Zhang Ming, PKUCS
　　删除子树中最小值图示
　　Copyright 2002 by Zhang Ming, PKUCS
　　删除右子树中最小值结点
　　Copyright 2002 by Zhang Ming, PKUCS
　　删除rt子树中最小结点
　　template
　　BinNode* BST::
　　deletemin(BinNode* subroot,
　　BinNode*& min) {
　　if (subroot->left() == NULL) { // Found min
　　min = subroot;
　　return subroot->right();
　　}
　　else { // Continue left
　　subroot->setLeft(deletemin(subroot->left(), min));
　　return subroot;
　　}
　　}
　　Copyright 2002 by Zhang Ming, PKUCS
　　删除值为val的结点
　　template
　　BinNode* BST::
　　removehelp(BinNode* subroot, const Key& K,
　　BinNode*& t) {
　　if (subroot== NULL) return NULL; // Val is not in tree
　　else if (KEComp::lt(K, subroot->val())) // Check left
　　subroot->setLeft(removehelp(subroot->left(), K, t));
　　else if (KEComp::gt(K, subroot->val())) // Check right
　　subroot->setRight(removehelp(subroot->right(), K, t));
　　else { // Found it: remove it
　　BinNode* temp;
　　t = subroot;
　　Copyright 2002 by Zhang Ming, PKUCS
　　if (subroot->left() == NULL) // Only a right child
　　subroot= subroot->right(); // so point to right
　　else if (subroot->right() == NULL) // Only a left child
　　subroot= subroot->left(); // so point to left
　　else { // Both children are non-empty
　　subroot->setRight(deletemin(subroot->right(), temp));
　　Elemte= subroot->val();
　　subroot->setVal(temp->val());
　　temp->setVal(te);
　　t = temp;
　　}
　　}
　　return subroot;
　　}
　　Copyright 2002 by Zhang Ming, PKUCS
　　删除值为val的结点(续)
　　else { // Found it: remove it
　　BinNode* temp = rt;
　　if (rt->left == NULL)
　　rt= rt->right;
　　else if (rt->right == NULL)
　　rt= rt->left;
　　else {
　　temp = deletemin(rt->right);
　　rt->setValue(temp->value()); }
　　delete temp;
　　} }
　　Copyright 2002 by Zhang Ming, PKUCS
　　讨论
　　n所有操作都围绕BST的性质,并一定要保
　　持这个性质
　　n用非递归算法实现插入,检索,删除
　　Copyright 2002 by Zhang Ming, PKUCS
　　讨论(续)
　　n允许有重复关键码
　　时(右子树)
　　-重复关键码应该有
　　规律地出现
　　-插入,检索,删除
　　都考虑这个特点.
　　尤其是删除,必须
　　删右子树中最小(
　　如果有重复,将是
　　值与被删根结点相
　　同的结点,因此能
　　保持性质)