iavl.h

常用算法与数据结构原代码

		else 
			p = p->RightChild;
	}
	if (!p) 
	{
		Reset(1, k);
		throw BadInput();
	} // not found
	
	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);
		IAVLNode<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->LeftSize--;
		p = s;
	}
	
	// p has at most one child
	// save child pointer in c
	IAVLNode<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
	IAVLNode<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
				IAVLNode<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
				IAVLNode<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;
}


template<class E, class K>
IndexedAVLtree<E,K>& IndexedAVLtree<E,K>::IndexedDelete(int k, E& e)
{// Delete k'th and put it in e.
	// Throw BadInput exception if there is no k'th element.
	
	// 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<IAVLNode<E,K>*> S(100);
	
	// set p to point to node with k'th element
	IAVLNode<E,K> *p = root; // search pointer
	while (p && p->LeftSize != k) 
	{
		S.Add(p);
		if (k < p->LeftSize) 
		{
			p->LeftSize--;
			p = p->LeftChild;
		}
		else
		{
			k -= p->LeftSize;
			p = p->RightChild;
		}
	}
	if (!p) 
	{// no element to delete, reset LeftSize
		p = root;
		while (p)
		{
			if (k < p->LeftSize) 
			{
				p->LeftSize--;
				p = p->LeftChild;}
			else 
			{
				k -= p->LeftSize;
				p = p->RightChild;
			}
		}
		throw BadInput();
	}
	
	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);
		IAVLNode<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->LeftSize--;
		p = s;
	}
	
	// p has at most one child
	// save child pointer in c
	IAVLNode<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
	IAVLNode<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
				IAVLNode<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
				IAVLNode<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;
}

template<class E, class K>
void IndexedAVLtree<E,K>::
InOutput(IAVLNode<E,K> *t)
{// Output in ascending order.
	// Use an inorder traversal.
	if (t) 
	{
		InOutput(t->LeftChild);
		cout << t->data << " ";
		InOutput(t->RightChild);
	}
}

template<class E, class K>
void IndexedAVLtree<E,K>::
PostOutput(IAVLNode<E,K> *t)
{// Output in postorder.
	if (t) 
	{
		PostOutput(t->LeftChild);
		PostOutput(t->RightChild);
		cout << t->data << " ";
	}
}

#endif;