avlbaum.h

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

template <class T>
CAVLNode<T>* CAVLNode<T>::GetLeftSibling()
{
	if (IsRoot() || IsLeftSibling()) return NULL;
	return Parent->Left;
};

template <class T>
CAVLNode<T>* CAVLNode<T>::GetRightSibling()
{
	if (IsRoot() || IsRightSibling()) return NULL;
	return Parent->Right;
};

template <class T>
CAVLNode<T>* CAVLNode<T>::GetFirstNodeInOrder()
{
	CAVLNode<T>* item = this;
	while (item->Left != NULL)
	{
		item = item->Left;
	}
	return item;
};

template <class T>
CAVLNode<T>* CAVLNode<T>::GetLastNodeInOrder()
{
	CAVLNode<T>* item = this;
	while (item->Right != NULL)
	{
		item = item->Right;
	}
	return item;
};

template <class T>
CAVLNode<T>* CAVLNode<T>::GetPrevNodeInOrder()
{
	if (Left != NULL)
	{
		return Left->GetLastNodeInOrder();
	}
	if (IsRightSibling()) return Parent;
	CAVLNode<T>* item = this;
	while (!item->IsRoot())
	{
		if (item->IsLeftSibling()) 
			item = item->Parent;
		else
			return item->Parent;
	}
	return NULL;
};

template <class T>
CAVLNode<T>* CAVLNode<T>::GetNextNodeInOrder()
{
	if (Right != NULL)
	{
		return Right->GetFirstNodeInOrder();
	}
	if (IsLeftSibling()) return Parent;
	CAVLNode<T>* item = this;
	while (!item->IsRoot())
	{
		if (item->IsRightSibling()) 
			item = item->Parent;
		else
			return item->Parent;
	}
	return NULL;
};

template <class T>
CAVLNode<T>* CAVLNode<T>::GetInsertPosition(const T* data)
{
	switch (Compare(*Data, *data))
	{
	case -1:
		if (!Right) return this;
		return Right->GetInsertPosition(data);
	case  0:
		return NULL; // Fehler, Objekt schon im Baum
		// error, object already in the tree (only inserted once!)
	case  1:
		if (!Left) return this;
		return Left->GetInsertPosition(data);
	}
	return NULL; // tritt nie auf
	// never happens
};

template <class T>
bool CAVLNode<T>::LeftRotation()
{
	ASSERT(Right != NULL);
	
	if (Right == NULL) return false;

	CAVLNode<T>* b = Right;
	// Falls nicht die Wurzel: Knoten b wird Kind
	if (!IsRoot())
	{
		if (IsLeftSibling())
			Parent->Left = b;
		else
			Parent->Right = b;
		b->Parent = Parent;
	}
	else
	{
		b->Parent = NULL;
	}
	
	// Zeiger korrekt umsetzen
	Right = b->Left;
	b->Left = this;

	// Elternzeiger setzen
	Parent = b;
	if (Right != NULL) Right->Parent = this;
	
	// Balancen setzen
	if (b->Balance == 0)
	{
		Balance = 1;
		b->Balance = -1;
	}
	else
	{
		Balance = 0;
		b->Balance = 0;
	}

	return true;
};

template <class T>
bool CAVLNode<T>::RightRotation()
{
	ASSERT(Left != NULL);
	
	if (Left == NULL) return false;

	CAVLNode<T>* b = Left;
	// Falls nicht die Wurzel: Knoten b wird Kind
	if (!IsRoot())
	{
		if (IsLeftSibling())
			Parent->Left = b;
		else
			Parent->Right = b;
		b->Parent = Parent;
	}
	else
	{
		b->Parent = NULL;
	}
	
	// Zeiger korrekt umsetzen
	Left = b->Right;
	b->Right = this;

	// Elternzeiger setzen
	Parent = b;
	if (Left != NULL) Left->Parent = this;

	// Balancen setzen
	if (b->Balance == 0)
	{
		Balance = -1;
		b->Balance = 1;
	}
	else
	{
		Balance = 0;
		b->Balance = 0;
	}

	return true;
};

template <class T>
bool CAVLNode<T>::DoubleRotationLeft()
{
	ASSERT(Left != NULL && Left->Right != NULL);

	if (Left == NULL || Left->Right == NULL) return false;

	CAVLNode<T>* b = Left;
	CAVLNode<T>* c = Left->Right;

	// Falls nicht die Wurzel: Knoten c wird Kind
	if (!IsRoot())
	{
		if (IsLeftSibling())
			Parent->Left = c;
		else
			Parent->Right = c;
	}

	// Zeiger korrekt umsetzen
	b->Right = c->Left;
	Left = c->Right;
	c->Left = b;
	c->Right = this;

	// Elternzeiger setzen
	c->Parent = Parent;
	Parent = c;
	b->Parent = c;
	if (b->Right != NULL) b->Right->Parent = b;
	if (Left != NULL) Left->Parent = this;

	// Balancen setzen
	switch (c->Balance)
	{
	case -1:
		Balance = 1;
		b->Balance = 0;
		break;
	case 0:
		Balance = 0;
		b->Balance = 0;
		break;
	case 1:
		Balance = 0;
		b->Balance = -1;
		break;
	}
	c->Balance = 0;
	
	return true;
};

template <class T>
bool CAVLNode<T>::DoubleRotationRight()
{
	ASSERT(Right != NULL && Right->Left != NULL);
	
	if (Right == NULL || Right->Left == NULL) return false;

	CAVLNode<T>* b = Right;
	CAVLNode<T>* c = Right->Left;

	// Falls nicht die Wurzel: Knoten c wird Kind
	if (!IsRoot())
	{
		if (IsLeftSibling())
			Parent->Left = c;
		else
			Parent->Right = c;
	}

	// Zeiger korrekt umsetzen
	Right = c->Left;
	b->Left = c->Right;
	c->Left = this;
	c->Right = b;

	// Elternzeiger setzen
	c->Parent = Parent;
	Parent = c;
	b->Parent = c;
	if (Right != NULL) Right->Parent = this;
	if (b->Left != NULL) b->Left->Parent = b;

	// Balancen setzen
	switch (c->Balance)
	{
	case -1:
		Balance = 0;
		b->Balance = 1;
		break;
	case 0:
		Balance = 0;
		b->Balance = 0;
		break;
	case 1:
		Balance = -1;
		b->Balance = 0;
		break;
	}
	c->Balance = 0;

	return true;
};

#ifdef _MSC_VER
template <class T>
void CAVLNode<T>::Draw(CDC* dc, CRect& rect)
{
	int depth = GetDepth();
	CSize Size = dc->GetTextExtent(*Data);
	dc->TextOut((rect.left+rect.right)/2-Size.cx/2, rect.top, *Data);

	if (Left != NULL)
	{
		CRect rect1 = rect;
		rect1.top += 2*Size.cy;
		rect1.right = (rect.right+rect.left)/2;
		dc->MoveTo((rect.left+rect.right)/2, rect.top+Size.cy);
		dc->LineTo((rect1.left+rect1.right)/2, rect1.top);
		Left->Draw(dc, rect1);
	}
	if (Right != NULL)
	{
		CRect rect2 = rect;
		rect2.top += 2*Size.cy;
		rect2.left = (rect.right+rect.left)/2;
		dc->MoveTo((rect.left+rect.right)/2, rect.top+Size.cy);
		dc->LineTo((rect2.left+rect2.right)/2, rect2.top);
		Right->Draw(dc, rect2);
	}
};
#endif

////////////////////////////////////////////////////////////////
// AVL-Tree (Template-Version)                                //
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
// AVL-Baum (Template-Variante)                               //
////////////////////////////////////////////////////////////////

// Requirements for the class T:
// Objects of class T must be comparable.
// A function
// int T::Compare(const T& t) const 
// must be implemented.
// Return values:
//    -1, if *this <  t
//     0, if *this == t
//     1, if *this >  t

// Anforderungen an die Klasse T:
// Objekte der Klasse T m黶sen vergleichbar sein.
// Der Vergleich erfolgt 黚er eine Funktion
// int T::Compare(const T& t) const 
// R點kgabewerte:
//    -1, falls *this <  t
//     0, falls *this == t
//     1, falls *this >  t

template <class T>
class CAVLTree
{
public:
	// construction and destruction
	// Standard-Konstruktor, Konstruktor und Destruktor
	CAVLTree();
	virtual ~CAVLTree();

	// information
	// Informationen
	bool IsEmpty() const;
	int GetDepth() const;
	long NodesInTree() const;

	// access to the root of the tree
	// Zugriff auf die Wurzel
	CAVLNode<T>* GetRoot();

	// insert and delete
	// Insert und Delete
	CAVLNode<T>* Insert(T* data, bool autodelete = true);
	bool Delete(T* data);

	bool DeleteAll();

	virtual CAVLNode<T>* Search(const T* data);
	virtual CAVLNode<T>* Search(T& data);

#ifdef _MSC_VER
	void Draw(CDC* dc, CRect& rect);
#endif

private:
	CAVLNode<T>* Tree;
	
	friend class CAVLTreeIterator<T>;
	/* siehe unten
	friend class CAVLTreeDialog<T>;
	*/
};

template <class T>
CAVLTree<T>::CAVLTree() : Tree(NULL)
{
};

template <class T>
CAVLTree<T>::~CAVLTree()
{
	delete Tree;
};

template <class T>
bool CAVLTree<T>::IsEmpty() const
{
	return Tree == NULL;
};

template <class T>
int CAVLTree<T>::GetDepth() const
{
	if (Tree == NULL) return 0;
	return Tree->GetDepth();
};

template <class T>
CAVLNode<T>* CAVLTree<T>::Insert(T* data, bool autodelete)
{
	// if the tree is empty, the root is used to store the entry

	// Wenn der Baum noch leer ist, kann (und mu