avlbaum.h

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

////////////////////////////////////////////////////////////////
// Note:                                                      //
// there must be a function T::Compare(T&)                    //
// or the function Compare of teh Template-Klasse             //
// CAVLNode<T> has to be overridden.                          //
////////////////////////////////////////////////////////////////

// Forward-Deklarationen
template <class T>
class CAVLNode;

template <class T>
class CAVLTree;

template <class T>
class CAVLTreeIterator;

/* siehe unter
template <class T>
class CAVLTreeDialog;
*/

////////////////////////////////////////////////////////////////
// AVL-treenode (=subtree) (Template-Version)                 //
////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////
// AVL-Baumknoten (=Teilbaum) (Template-Variante)             //
////////////////////////////////////////////////////////////////

template <class T>
class CAVLNode
{
public:
	// standard constructor, constructors, destructor
	// Standard-Konstruktor, Konstruktor(en) und Destruktor
	CAVLNode(T* data, int balance = 0, CAVLNode<T>* parent = NULL, CAVLNode<T>* left = NULL, CAVLNode<T>* right = NULL);
	virtual ~CAVLNode();

	// searching
	// Suchen
	CAVLNode<T>* Search(const T* data);

	// comparing
	// Vergleich
	static int Compare(const T& t1, const T& t2);

	// information about the position in the tree
	// Informationen 黚er die Position im Baum
	bool IsRoot() const;
	bool IsLeftSibling() const;
	bool IsRightSibling() const;
	bool HasLeftSibling() const;
	bool HasRightSibling() const;

	// further information
	// Weitere Informationen
	int GetDepth() const;
	int GetLevel() const;
	int NodesInTree() const;

	// navigation in the tree
	// Navigation im Baum
	CAVLNode<T>* GetRoot();

	CAVLNode<T>* GetLeftSibling();
	CAVLNode<T>* GetRightSibling();

	CAVLNode<T>* GetFirstNodeInOrder();
	CAVLNode<T>* GetLastNodeInOrder();

	CAVLNode<T>* GetPrevNodeInOrder();
	CAVLNode<T>* GetNextNodeInOrder();

	// restructuration
	// Restrukturierungs-Ma遪ahmen
	bool LeftRotation();
	bool RightRotation();
	bool DoubleRotationLeft();
	bool DoubleRotationRight();


	// Diagnostics
	bool CheckBalances(LPTSTR buffer = NULL, UINT buflen = 0) const;

	// drawing into a device context, not fully implemented
	// Visualisierung in einem Ger鋞ekontext
#ifdef _MSC_VER
	void Draw(CDC* dc, CRect& rect);
#endif

	// item-data
	// Datenelement
	T* Data;

	// informationen about the height of the subtrees
	// -1: left subtree is by 1 higher than the right one
	//  0: both subtrees have the same height
	//  1: right subtree is by 1 higher than the left one

	// Informationen 黚er die Tiefe der Teilb鋟me
	// -1: linker Baum ist um 1 tiefer als rechter
	//  0: beide Teilb鋟me haben die gleiche Tiefe
	//  1: rechter Baum ist um 1 tiefer als linker
	
	int Balance;

	// parent node
	// 躡ergeordneter Knoten
	CAVLNode<T>* Parent;

	// left and right subtree
	// Linker und rechter Teilbaum
	CAVLNode<T>* Left;
	CAVLNode<T>* Right;
private:
	CAVLNode<T>* GetInsertPosition(const T* data);
	bool RestructureInsert();
	bool RestructureDelete();

	CAVLNode(const CAVLNode<T>& /*tree*/) {};
	CAVLNode& operator= (const CAVLNode<T>& /*tree*/) {return *this;};

	friend class CAVLTree<T>;
};

template <class T>
CAVLNode<T>::CAVLNode(T* data, int balance, CAVLNode<T>* parent, CAVLNode<T>* left, CAVLNode<T>* right)
	: Data(data),
	  Balance(balance),
	  Parent(parent),
	  Left(left),
	  Right(right)
{
};

template <class T>
CAVLNode<T>::~CAVLNode()
{
	delete Left;
	delete Right;
	delete Data;
};

template <class T>
bool CAVLNode<T>::RestructureInsert()
{
	CAVLNode<T>* item = this;
	while (!item->IsRoot())
	{
		// rule 1
		// Regel 1
		if (item->IsLeftSibling() && item->Parent->Balance == 0)
		{
			item->Parent->Balance = -1;
			item = item->Parent;
			continue;
		}
		if (item->IsRightSibling() && item->Parent->Balance == 0)
		{
			item->Parent->Balance = 1;
			item = item->Parent;
			continue;
		}
		// rule 2
		// Regel 2
		if (item->IsLeftSibling() && item->Parent->Balance == 1)
		{
			item->Parent->Balance = 0;
			break;
		}
		if (item->IsRightSibling() && item->Parent->Balance == -1)
		{
			item->Parent->Balance = 0;
			break;
		}
		// rule 3
		// Regel 3
		if (item->IsLeftSibling() && item->Parent->Balance == -1)
		{
			if (item->Balance == 1)
				item->Parent->DoubleRotationLeft();
			else
				item->Parent->RightRotation();
			break;
		}
		if (item->IsRightSibling() && item->Parent->Balance == 1)
		{
			if (item->Balance == -1)
				item->Parent->DoubleRotationRight();
			else
				item->Parent->LeftRotation();
			break;
		}
	}
	return true;
};

template <class T>
bool CAVLNode<T>::RestructureDelete()
{
	// Regeln f黵 den Elternknoten des gerade gel鰏chten Blattes
	// anwenden, bevor mit dem eigentlichen Aufstieg begonnen
	// werden kann
	CAVLNode<T>* item = this;
	// Regel 1
	if (item->Balance == 0 && item->Left == NULL) 
	{
		item->Balance = 1;
		return true;
	}
	if (item->Balance == 0 && item->Right == NULL) 
	{
		item->Balance = -1;
		return true;
	}
	// Regel 2
	if (item->Balance == -1 && item->Left == NULL)
	{
		item->Balance = 0;
	}
	if (item->Balance == 1 && item->Right == NULL)
	{
		item->Balance = 0;
	}
	// Regel 3
	if (item->Balance == -1 && item->Right == NULL)
	{
		if (item->Left->Balance == 1)
		{
			item->DoubleRotationLeft();
			item = item->Parent; // Zeiger sind durch die Rotation etwas verrutscht
		}
		else
		{
			item->RightRotation();
			item = item->Parent; // Zeiger sind durch die Rotation etwas verrutscht
		}
		if (item->Balance == 1)
			return true;
	}
	if (item->Balance == 1 && item->Left == NULL)
	{
		if (item->Right->Balance == -1)
		{
			item->DoubleRotationRight();
			item = item->Parent; // Zeiger sind durch die Rotation etwas verrutscht
		}
		else
		{
			item->LeftRotation();
			item = item->Parent; // Zeiger sind durch die Rotation etwas verrutscht
		}
		if (item->Balance == -1)
			return true;
		//return true;
	}
	// Beginn des eigentlichen Aufstiegs
	while (!item->IsRoot())
	{
		// Regel 1
		if (item->IsLeftSibling() && item->Parent->Balance == 0)
		{
			item->Parent->Balance = 1;
			break;
		}
		if (item->IsRightSibling() && item->Parent->Balance == 0)
		{
			item->Parent->Balance = -1;
			break;
		}
		// Regel 2
		if (item->IsLeftSibling() && item->Parent->Balance == -1)
		{
			item->Parent->Balance = 0;
			item = item->Parent;
			continue;
		}
		if (item->IsRightSibling() && item->Parent->Balance == 1)
		{
			item->Parent->Balance = 0;
			item = item->Parent;
			continue;
		}
		// Regel 3
		if (item->IsRightSibling() && item->Parent->Balance == -1)
		{
			if (item->Parent->Left->Balance == 1)
			{
				item->Parent->DoubleRotationLeft();
				item = item->Parent->Parent; // Zeiger sind durch die Rotation etwas verrutscht
			}
			else
			{
				item->Parent->RightRotation();
				item = item->Parent->Parent; // Zeiger sind durch die Rotation etwas verrutscht
			}
			if (item->Balance == 1)
				return true;
			continue;
		}
		if (item->IsLeftSibling() && item->Parent->Balance == 1)
		{
			if (item->Parent->Right->Balance == -1)
			{
				item->Parent->DoubleRotationRight();
				item = item->Parent->Parent; // Zeiger sind durch die Rotation etwas verrutscht
			}
			else
			{
				item->Parent->LeftRotation();
				item = item->Parent->Parent; // Zeiger sind durch die Rotation etwas verrutscht
			}
			if (item->Balance == -1)
				return true;
			continue;
		}
		// Never appears...
		break;
	}
	return true;
};

template <class T>
CAVLNode<T>* CAVLNode<T>::Search(const T* data)
{
	switch (Compare(*Data, *data))
	{
	case -1: 
		if (!Right) return NULL;
		return Right->Search(data);
	case  0: return this;
	case  1:
		if (!Left) return NULL;
		return Left->Search(data);
	}
	return NULL;
};

template <class T>
int CAVLNode<T>::Compare(const T& t1, const T& t2)
{
	return t1.Compare(t2);
};

template <class T>
bool CAVLNode<T>::IsRoot() const
{
	return Parent == NULL;
};

template <class T>
bool CAVLNode<T>::IsLeftSibling() const
{
	return !IsRoot() && Parent->Left == this;
};

template <class T>
bool CAVLNode<T>::IsRightSibling() const
{
	return !IsRoot() && Parent->Right == this;
};

template <class T>
bool CAVLNode<T>::HasLeftSibling() const
{
	return !IsRoot() && IsRightSibling() && Parent->Left != NULL;
};
	
template <class T>
bool CAVLNode<T>::HasRightSibling() const
{
	return !IsRoot() && IsLeftSibling() && Parent->Right != NULL;
};

template <class T>
int CAVLNode<T>::GetDepth() const
{
	int i = 0;
	if (Left != NULL)
		i = Left->GetDepth();
	if (Right != NULL)
		i = max(i, Right->GetDepth());
	return i+1;
};

template <class T>
int CAVLNode<T>::GetLevel() const
{
	const CAVLNode<T>* item = this;
	int level = 0;
	while (item->Parent != NULL)
	{
		item = item->Parent;
		level++;
	}
	return level;
};

template <class T>
int CAVLNode<T>::NodesInTree() const
{
	int Nodes = 1;
	if (Left != NULL) 
		Nodes += Left->NodesInTree();
	if (Right != NULL)
		Nodes += Right->NodesInTree();
	return Nodes;
};

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