二叉检索树
二叉检索树
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.
";
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允许有重复关键码
时(右子树)
-重复关键码应该有
规律地出现
-插入,检索,删除
都考虑这个特点.
尤其是删除,必须
删右子树中最小(
如果有重复,将是
值与被删根结点相
同的结点,因此能
保持性质)
132