bintree.h

来自「经典的红黑树算法」· C头文件 代码 · 共 1,118 行 · 第 1/2 页

/*=====================================================================
	BinTree.h - Binary tree template class

	Author: Per Nilsson

	Freeware and no copyright on my behalf. However, if you use the 
	code in some manner	I'd appreciate a notification about it
	[e-mail]

	The Red-Black insertion algorithm is to some extent based upon
	the example in 
	http://www.oopweb.com/Algorithms/Documents/PLDS210/Volume/red_black.html

	Classes:

		// The node class.
		template <class KeyType, class ValueType> class BinTreeNode

		// The tree class
		template <class KeyType, class ValueType> class BinTree
		{
		public:
			// Regular low->high (++) and high->low (--) iterator
		    class Iterator

			// Top to bottom iterator
			class ParentFirstIterator

			// Bottom to top iterator
			class ParentLastIterator

			// Top to bottom, level by level iterator
			class ByLevelIterator
		}

	Requirements:
		The KeyType class must support:
			1. < and == operations.
			2. Copy construction.

		The ValueType must support:
			1. Copy construction.
			2. Assignment operation (=) if BinTreeNode::SetValue is used

    Dependencies:
		No external dependencies

    #define NO_REDBLACK to deactivate the red-black functionality. 
	Tree will still work, but nothing is done in regards of balancing.

=====================================================================*/
#ifndef _BINTREE_H_
#define _BINTREE_H_

//------------------------------------------------------------
// class BinTreeNode is the element type of the BinTree tree. 
//------------------------------------------------------------
template <class KeyType, class ValueType> 
class BinTreeNode
{
public:
	//------------------------------
	// Public Construction
	//------------------------------

	// Constructor(Key, Value)
	BinTreeNode(const KeyType& k, const ValueType& v)
		:mKey(k),mValue(v),mLeftChild(0),mRightChild(0),mParent(0)
#ifndef NO_REDBLACK
		,mIsRed(true)
#endif
	{}

	// Destructor
	virtual ~BinTreeNode(){}

	//------------------------------
	// Public Commands
	//------------------------------
	// Set methods.
	// Set*Child also updates the the child's parent attribute.
	void SetLeftChild(BinTreeNode* p)  { mLeftChild=p; if (p) p->SetParent(this);}
	void SetRightChild(BinTreeNode* p) { mRightChild=p;if (p) p->SetParent(this);}
	void SetParent(BinTreeNode* p)	   { mParent=p; }

	void SetValue(const ValueType& v)  { mValue = v; }
	// Note: Deliberately no SetKey, that could easily screw up the tree.
	// If a key shall be changed, delete node from tree and insert a new one instead.

#ifndef NO_REDBLACK
	void SetRed()        { mIsRed = true; }
	void SetBlack()      { mIsRed = false; }
#endif
	//------------------------------
	// Public Queries
	//------------------------------

	// Get methods
	BinTreeNode* GetLeftChild() const  { return mLeftChild; }
	BinTreeNode* GetRightChild() const { return mRightChild; }
	BinTreeNode* GetParent() const     { return mParent; }

	ValueType GetValue() const         { return mValue; }
	KeyType GetKey() const             { return mKey; }

	// Some more or less useful queries
	bool IsRoot() const           { return mParent==0; }
	bool IsLeftChild() const      { return mParent!=0 && mParent->GetLeftChild()==this; }
	bool IsRightChild() const     { return mParent!=0 && mParent->GetRightChild()==this; }
	bool IsLeaf() const           { return mLeftChild==0 && mRightChild==0; }
	unsigned int GetLevel() const { if (IsRoot()) return 1; else return GetParent()->GetLevel() + 1; }

#ifndef NO_REDBLACK
	bool IsRed() const   { return mIsRed; };
	bool IsBlack() const { return !mIsRed; };
#endif

private:
	//------------------------------
	// Disabled Methods
	//------------------------------

	// Default constructor - deliberately not implemented
	BinTreeNode();

	//------------------------------
	// Private Members
	//------------------------------
	BinTreeNode*	mLeftChild;
	BinTreeNode*	mRightChild;

	BinTreeNode*	mParent;

	KeyType			mKey;
	ValueType		mValue;

#ifndef NO_REDBLACK
	bool mIsRed;
#endif

};

//------------------------------------------------------------
// class BinTree. Holder of the tree structure. 
//------------------------------------------------------------
template <class KeyType, class ValueType> 
class BinTree
{
public:
	//------------------------------
	// Public Definitions
	//------------------------------
	typedef BinTreeNode<KeyType,ValueType> Node;

	//------------------------------
	// Public Classes
	//------------------------------

	//--------------------------------------------------------
	// class BinTree::Iterator.
	// Regular low->high (++) and high->low (--) iterator
	//--------------------------------------------------------
	class Iterator
	{
	public:
		//------------------------------
		// Public Construction
		//------------------------------
		// Default Constructor
		Iterator():mRoot(0),mCur(0){}

		// Constructor(Node*)
		Iterator(Node* root):mRoot(root){ Reset();}

		// Copy constructor
		Iterator(const Iterator& src):mRoot(src.mRoot),mCur(src.mCur){}


		//------------------------------
		// Public Commands
		//------------------------------
		// Reset the iterator
		// atLowest : true  - Reset at lowest key value (and then ++ your way through)
		//            false - Reset at highest key value (and then -- your way through)
		void Reset(bool atLowest=true) 
		{ 
			if (atLowest) 
				mCur = Min(mRoot); 
			else 
				mCur = Max(mRoot);
		}

		//------------------------------
		// Public Queries
		//------------------------------

		// Has the iterator reached the end?
		bool atEnd() const { return mCur==0; }
		Node* GetNode() { return mCur;	}

		//------------------------------
		// Public Operators
		//------------------------------

		// Assignment operator
		Iterator& operator=(const Iterator& src) 
		{ 
			mRoot = src.mRoot; 
			mCur = src.mCur; 
			return (*this);
		}

		// Increment operator
		void operator++(int) { Inc(); }

		// Decrement operator
		void operator--(int)
		{
			Dec();
		}

		// Access operators
		Node* operator -> () { return GetNode();	}
		Node& operator*   () 
		{ 
			if (atEnd())
			{
				throw "Iterator at end";			
			}
			return *mCur; 
		}

	private:
		//------------------------------
		// Private Helper Methods
		//------------------------------

		// Min: Returns node with lowest key from n and down.
		//      Ie the node all down to the left
		Node* Min(Node* n)
		{
			while(n && n->GetLeftChild())
				n = n->GetLeftChild();
			return n;
		}
		// Min: Returns node with highest key from n and down.
		//      Ie the node all down to the right
		Node* Max(Node* n)
		{
			while(n && n->GetRightChild())
				n = n->GetRightChild();
			return n;
		}

		//------------------------------
		// Private Commands
		//------------------------------
		// ++
		void Inc()
		{
			// Already at end?
			if (mCur==0)
				return;

			if (mCur->GetRightChild())
			{
				// If current node has a right child, the next higher node is the 
				// node with lowest key beneath the right child.
				mCur =  Min(mCur->GetRightChild());
			}
			else if (mCur->IsLeftChild())
			{
				// No right child? Well if current node is a left child then
				// the next higher node is the parent
				mCur = mCur->GetParent();
			}
			else
			{
				// Current node neither is left child nor has a right child.
				// Ie it is either right child or root
				// The next higher node is the parent of the first non-right
				// child (ie either a left child or the root) up in the
				// hierarchy. Root's parent is 0.
				while(mCur->IsRightChild())
					mCur = mCur->GetParent();
				mCur =  mCur->GetParent();
			}
		}

		// --
		void Dec()
		{
			// Already at end?
			if (mCur==0)
				return;

			if (mCur->GetLeftChild())
			{
				// If current node has a left child, the next lower node is the 
				// node with highest key beneath the left child.
				mCur =  Max(mCur->GetLeftChild());
			}
			else if (mCur->IsRightChild())
			{
				// No left child? Well if current node is a right child then
				// the next lower node is the parent
				mCur =  mCur->GetParent();
			}
			else
			{
				// Current node neither is right child nor has a left child.
				// Ie it is either left child or root
				// The next higher node is the parent of the first non-left
				// child (ie either a right child or the root) up in the
				// hierarchy. Root's parent is 0.

				while(mCur->IsLeftChild())
					mCur = mCur->GetParent();
				mCur =  mCur->GetParent();
			}
		}

		//------------------------------
		// Private Members
		//------------------------------
		Node* mRoot;
		Node* mCur;
	}; // Iterator

	//--------------------------------------------------------
	// class BinTree::ParentFirstIterator. 
	// Traverses the tree from top to bottom. Typical usage is 
	// when storing the tree structure, because when reading it 
	// later (and inserting elements) the tree structure will
	// be the same.
	//--------------------------------------------------------
	class ParentFirstIterator
	{
	public:

		//------------------------------
		// Public Construction
		//------------------------------
		// Default constructor
		ParentFirstIterator():mRoot(0),mCur(0){}

		// Constructor(Node*)
		explicit ParentFirstIterator(Node* root):mRoot(root),mCur(0){ Reset(); }

		//------------------------------
		// Public Commands
		//------------------------------
		void Reset() { mCur = mRoot; };

		//------------------------------
		// Public Queries
		//------------------------------

		// Has the iterator reached the end?
		bool atEnd() const { return mCur==0; }
		Node* GetNode() { return mCur;	}

		//------------------------------
		// Public Operators
		//------------------------------

		// Assignment operator
		ParentFirstIterator& operator=(const ParentFirstIterator& src) 
		{ 
			mRoot = src.mRoot; mCur = src.mCur; return (*this);
		}

		// Increment operator
		void operator++(int) { Inc(); }

		// Access operators
		Node* operator -> () { return GetNode();	}
		Node& operator*   () 
		{ 
			if (atEnd())
				throw "ParentFirstIterator at end";			
			return *GetNode(); 
		}
	private:

		//------------------------------
		// Private Commands
		//------------------------------

		void Inc()
		{
			// Already at end?
			if (mCur==0)
				return;

			// First we try down to the left
			if (mCur->GetLeftChild())
			{
				mCur =  mCur->GetLeftChild();
			}
			else if (mCur->GetRightChild())
			{
				// No left child? The we go down to the right.
				mCur = mCur->GetRightChild();
			}
			else
			{
				// No children? Move up in the hierarcy until
				// we either reach 0 (and are finished) or
				// find a right uncle.
				while (mCur!=0)
				{
					// But if parent is left child and has a right "uncle" the parent
					// has already been processed but the uncle hasn't. Move to 
					// the uncle.
					if (mCur->IsLeftChild() && mCur->GetParent()->GetRightChild())
					{
						mCur = mCur->GetParent()->GetRightChild();
						return;
					}
					mCur = mCur->GetParent();
				}
			}
		}

		//------------------------------
		// Private Members
		//------------------------------
		Node* mRoot;
		Node* mCur;

	}; // ParentFirstIterator

	//--------------------------------------------------------
	// class BinTree::ParentLastIterator. 
	// Traverse the tree from bottom to top.
	// Typical usage is when deleting all elements in the tree
	// because you must delete the children before you delete
	// their parent.
	//--------------------------------------------------------
	class ParentLastIterator
	{
	public:

		//------------------------------
		// Public Construction
		//------------------------------
		// Default constructor
		ParentLastIterator():mRoot(0),mCur(0){}

		// Constructor(Node*)
		explicit ParentLastIterator(Node* root):mRoot(root),mCur(0){ Reset();}

		//------------------------------
		// Public Commands
		//------------------------------
		void Reset() { mCur = Min(mRoot); }

		//------------------------------
		// Public Queries
		//------------------------------

		// Has the iterator reached the end?
		bool atEnd() const { return mCur==0; }
		Node* GetNode() { return mCur;	}

		//------------------------------
		// Public Operators
		//------------------------------

		// Assignment operator
		ParentLastIterator& operator=(const ParentLastIterator& src) { mRoot = src.mRoot; mCur = src.mCur; return (*this);}

		// Increment operator
		void operator++(int) { Inc(); }

		// Access operators
		Node* operator -> () { return GetNode();	}
		Node& operator*   () 
		{ 
			if (atEnd())
				throw "ParentLastIterator at end";			
			return *GetNode(); 
		}
	private:
		//------------------------------
		// Private Helper Methods
		//------------------------------

		// Min: Returns the node as far down to the left as possible.
		Node* Min(Node* n)
		{
			while(n!=0 && (n->GetLeftChild()!=0 || n->GetRightChild()!=0))
			{
				if (n->GetLeftChild())
					n = n->GetLeftChild();
				else
					n = n->GetRightChild();
			}
			return n;
		}

		//------------------------------
		// Private Commands
		//------------------------------
		void Inc()
		{
			// Already at end?
			if (mCur==0)
				return;

			// Note: Starting point is the node as far down to the left as possible.

			// If current node has an uncle to the right, go to the
			// node as far down to the left from the uncle as possible
			// else just go up a level to the parent.
			if (mCur->IsLeftChild() && mCur->GetParent()->GetRightChild())
			{
				mCur = Min(mCur->GetParent()->GetRightChild());
			}
			else
				mCur = mCur->GetParent();
		}

		//------------------------------
		// Private Members
		//------------------------------
		Node* mRoot;
		Node* mCur;
	}; // ParentLastIterator

	// ByLevelIterator. Traverse tree top to bottom, level by level left to right.
	// Typical usage : I don't know. Perhaps if the tree should be displayed               
	// in some fancy way.
	// It is the most memory consuming of all iterators as it will allocate an 
	// array of (Size()+1)/2 Node*s.
	// Impl. desc:
	//   mArray[0] is the current node we're looking at, initially set to mRoot.
	//   When ++:ing the children of mArray[0] (if any) are put last in the 
	//   array and the array is shifted down 1 step
	class ByLevelIterator
	{
	public:
		//------------------------------
		// Public Construction
		//------------------------------

		// Default constructor
		ByLevelIterator():mRoot(0),mArray(0),mSize(0){}

		// Constructor(treeRoot, elementsInTree)
		ByLevelIterator(Node* root, unsigned int size):mRoot(root),mSize(size),mArray(0){ Reset();}

		// Copy constructor
		ByLevelIterator(const ByLevelIterator& src):mRoot(src.mRoot),mSize(src.mSize),mEndPos(src.mEndPos)
		{
			if (src.mArray!=0)
			{
				mArray = new Node*[(mSize+1)/2];