平衡二叉树中删除结点
求算法：平衡二叉树中删除结点（c\c＋＋）
[解决办法]
template <class E, class K>
AVLtree <E,K> & AVLtree <E,K> ::Delete(const K& k, E& e)
{// Delete element with key k and put it in e.
// Throw BadInput exception if there is no element
// with key k.
// define a stack to hold path taken from root
// to physically deleted node
// we will not run out of stack space unless
// the number of elements is much more than 2^60
Stack <AVLNode <E,K> *> S(100);
// set p to point to node with key k
AVLNode <E,K> *p = root; // search pointer
while (p && p-> data != k){// move to a child of p
S.Add(p);
if (k < p-> data) p = p-> LeftChild;
else p = p-> RightChild;
}
if (!p) throw BadInput(); // no element with key k
e = p-> data; // save element to delete
// restructure tree
// handle case when p has two children
if (p-> LeftChild && p-> RightChild) {// two children
// convert to zero or one child case
// find largest element in left subtree of p
S.Add(p);
AVLNode <E,K> *s = p-> LeftChild;
while (s-> RightChild) {// move to larger element
S.Add(s);
s = s-> RightChild;}
// move largest from s to p
p-> data = s-> data;
p = s;}
// p has at most one child
// save child pointer in c
AVLNode <E,K> *c;
if (p-> LeftChild) c = p-> LeftChild;
else c = p-> RightChild;
// delete p
if (p == root) root = c;
else {// is p a left or right child?
if (p == S.Top()-> LeftChild)
S.Top()-> LeftChild = c;
else S.Top()-> RightChild = c;}
E f = p-> data; // f may not equal e
delete p;
// rebalance tree and correct balance factors
// use stack to retrace path to root
// set q to parent of deleted node
AVLNode <E,K> *q;
try {S.Delete(q);}
catch (OutOfBounds)
{return *this;} // root was deleted
while (q)
if (f <= q-> data) {
// deleted from left subtree of q
// height of left subtree reduced by 1
q-> bf--;
if (q-> bf == -1) // height of q is unchanged
// nothing more to do
return *this;
if (q-> bf == -2) {// q is unbalanced
// classify imbalance and rotate
AVLNode <E,K> *B = q-> RightChild,
*PA; // q is A node
// PA is parent of A
try {S.Delete(PA);}
catch (OutOfBounds)
{PA = 0;} // A is root
switch (B-> bf) {
case 0: // L0 imbalance
RRrotate(PA,q,B);
B-> bf = 1;
q-> bf = -1; // q is A node
return *this;
case 1: // L1 imbalance
RLrotate(PA,q,B);
break; // must continue on path to root
case -1: // L-1 imbalance
RRrotate(PA,q,B);
}
q = PA;
}
else {// q-> bf is 0
try {S.Delete(q);}
catch (OutOfBounds)
{return *this;}
}
}
else {// f > q-> data
// deleted from right subtree of q
// height of right subtree reduced by 1
q-> bf++;
if (q-> bf == 1) // height of q is unchanged
// nothing more to do
return *this;
if (q-> bf == 2) {// q is unbalanced
// classify imbalance and rotate
AVLNode <E,K> *B = q-> LeftChild,
*PA; // q is A node
// PA is parent of A
try {S.Delete(PA);}
catch (OutOfBounds)
{PA = 0;} // A is root
switch (B-> bf) {
case 0: // R0 imbalance
LLrotate(PA,q,B);
B-> bf = -1;
q-> bf = 1; // q is A node
return *this;
case 1: // R1 imbalance
LLrotate(PA,q,B);
break; // must continue on path to root
case -1: // R-1 imbalance
LRrotate(PA,q,B);
}
q = PA;
}
else {// q-> bf is 0
try {S.Delete(q);}
catch (OutOfBounds)
{return *this;}
}
}
return *this;
}
AVL树的删除结点程序
[解决办法]
数据结构上应该有比较详细的描述，在一般《数据结构-c++描述》里面有现成的例子。
