bintree.h

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

				memcpy(mArray,src.mArray,sizeof(Node*)*(mSize+1)/2);
			}
			else
				mArray = 0;
		}

		// Destructor
		~ByLevelIterator() 
		{ 
			if (mArray!=0)
			{
				delete [] mArray;
				mArray = 0;
			}
		}

		//------------------------------
		// Public Commands
		//------------------------------
		void Reset() 
		{ 
			if (mSize>0)
			{
				// Only allocate the first time Reset is called
				if (mArray==0)
				{
					// mArray must be able to hold the maximum "width" of the tree which
					// at most can be (NumberOfNodesInTree + 1 ) / 2
					mArray = new Node*[(mSize+1)/2];
				}
				// Initialize the array with 1 element, the mRoot.
				mArray[0] = mRoot;
				mEndPos = 1;
			}
			else 
				mEndPos=0;
		} // Reset

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

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

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

		// Assignment Operator
		ByLevelIterator& operator=(const ByLevelIterator& src) 
		{ 
			mRoot = src.mRoot; 
			mSize = src.mSize;
			if (src.mArray!=0)
			{
				mArray = new Node*[(mSize+1)/2];
				memcpy(mArray,src.mArray,sizeof(Node*)*(mSize+1)/2);
			}
			else
				mArray = 0;

			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 Commands
		//------------------------------

		void Inc()
		{
			if (mEndPos == 0)
				return;

			// Current node is mArray[0]
			Node* pNode = mArray[0];

			// Move the array down one notch, ie we have a new current node 
			// (the one than just was mArray[1])
			for (unsigned int i=0;i<mEndPos;i++)
			{
				mArray[i] = mArray[i+1];
			}
			mEndPos--;

			Node* pChild=pNode->GetLeftChild();
			if (pChild) // Append the left child of the former current node
			{ 
				mArray[mEndPos] = pChild;
				mEndPos++;
			}

			pChild = pNode->GetRightChild();
			if (pChild) // Append the right child of the former current node
			{ 
				mArray[mEndPos] = pChild;
				mEndPos++;
			}

		}

		//------------------------------
		// Private Members
		//------------------------------
		Node** mArray;
		Node* mRoot;
		unsigned int mSize;
		unsigned int mEndPos;
	}; // ByLevelIterator

	// AccessClass is a temparoary class used with the [] operator.
	// It makes it possible to have different behavior in situations like:
	// myTree["Foo"] = 32; 
	//   If "Foo" already exist, just update its value else insert a new 
	//   element.
	// int i = myTree["Foo"]
	// If "Foo" exists return its value, else throw an exception.
	// 
	class AccessClass
	{
		// Let BinTree be the only one who can instantiate this class.
		friend class BinTree<KeyType, ValueType>;
	public:

		// Assignment operator. Handles the myTree["Foo"] = 32; situation
		operator=(const ValueType& value)
		{
			// Just use the Set method, it handles already exist/not exist situation
			mTree.Set(mKey,value);
		}

		// ValueType operator
		operator ValueType()
		{
			Node* node = mTree.Find(mKey);

			// Not found
			if (node==0)
			{
				throw "Item not found";
			}

			return node->GetValue();
		}


	private:
		//------------------------------
		// Private Construction
		//------------------------------
		AccessClass(BinTree& tree, const KeyType& key):mTree(tree),mKey(key){}
		//------------------------------
		// Disabled Methods
		//------------------------------
		// Default constructor
		AccessClass();

		//------------------------------
		// Private Members
		//------------------------------
		BinTree& mTree;
		const KeyType& mKey;
	}; // AccessClass

	// ==== Enough of that, lets get back to the BinTree class itself ====

	//------------------------------
	// Public Construction
	//------------------------------
	// Constructor.
	BinTree():mRoot(0),mSize(0){}

	// Destructor
	~BinTree(){ DeleteAll(); }

	//------------------------------
	// Public Commands
	//------------------------------

	bool Insert(const KeyType& keyNew, const ValueType& v)
#ifndef NO_REDBLACK
	// RED / BLACK insertion
	{
		// First insert node the "usual" way (no fancy balance logic yet)
		Node* newNode = new Node(keyNew,v);
		if (!Insert(newNode))
		{
			delete newNode;
			return false;
		}

		// Then attend a balancing party
		while  (!newNode->IsRoot() && (newNode->GetParent()->IsRed()))
		{
			if ( newNode->GetParent()->IsLeftChild()) 
			{
				// If newNode is a left child, get its right 'uncle'
				Node* newNodesUncle = newNode->GetParent()->GetParent()->GetRightChild();
				if ( newNodesUncle!=0 && newNodesUncle->IsRed())
				{
					// case 1 - change the colours
					newNode->GetParent()->SetBlack();
					newNodesUncle->SetBlack();
					newNode->GetParent()->GetParent()->SetRed();
					// Move newNode up the tree
					newNode = newNode->GetParent()->GetParent();
				}
				else 
				{
					// newNodesUncle is a black node
					if ( newNode->IsRightChild()) 
					{
					// and newNode is to the right
					// case 2 - move newNode up and rotate
					newNode = newNode->GetParent();
					RotateLeft(newNode);
					}
					// case 3
					newNode->GetParent()->SetBlack();
					newNode->GetParent()->GetParent()->SetRed();
					RotateRight(newNode->GetParent()->GetParent());
				}
			}
			else 
			{
				// If newNode is a right child, get its left 'uncle'
				Node* newNodesUncle = newNode->GetParent()->GetParent()->GetLeftChild();
				if ( newNodesUncle!=0 && newNodesUncle->IsRed())
				{
					// case 1 - change the colours
					newNode->GetParent()->SetBlack();
					newNodesUncle->SetBlack();
					newNode->GetParent()->GetParent()->SetRed();
					// Move newNode up the tree
					newNode = newNode->GetParent()->GetParent();
				}
				else 
				{
					// newNodesUncle is a black node
					if ( newNode->IsLeftChild()) 
					{
						// and newNode is to the left
						// case 2 - move newNode up and rotate
						newNode = newNode->GetParent();
						RotateRight(newNode);
					}
					// case 3
					newNode->GetParent()->SetBlack();
					newNode->GetParent()->GetParent()->SetRed();
					RotateLeft(newNode->GetParent()->GetParent());
				}

			}
		}
		// Color the root black
		mRoot->SetBlack();
		return true;
	}
#else
	// No balance logic insertion
	{
		Node* newNode = new Node(keyNew,v);
		if (!Insert(newNode))
		{
			delete newNode;
			return false;
		}
		return true;
	}
#endif // NO_REDBLACK

	// Set. If the key already exist just replace the value
	// else insert a new element.
	void Set(const KeyType& k, const ValueType& v)
	{
		Node* p = Find(k);
		if (p)
		{
			p->SetValue(v);
		}
		else
			Insert(k,v);
	}

	// Remove a node.Return true if the node could
	// be found (and was removed) in the tree.
	bool Delete(const KeyType& k)
	{
		Node* p = Find(k);
		if (p == 0) return false;

		// Rotate p down to the left until it has no right child, will get there
		// sooner or later.
		while(p->GetRightChild())
		{
			// "Pull up my right child and let it knock me down to the left"
			RotateLeft(p);
		}
		// p now has no right child but might have a left child
		Node* left = p->GetLeftChild(); 

		// Let p's parent point to p's child instead of point to p
		if (p->IsLeftChild())
		{
			p->GetParent()->SetLeftChild(left);
		}
		else if (p->IsRightChild())
		{
			p->GetParent()->SetRightChild(left);
		}
		else
		{
			// p has no parent => p is the root. 
			// Let the left child be the new root.
			SetRoot(left);
		}

		// p is now gone from the tree in the sense that 
		// no one is pointing at it. Let's get rid of it.
		delete p;
			
		mSize--;
		return true;
	}

	// Wipe out the entire tree.
	void DeleteAll()
	{
		ParentLastIterator i(GetParentLastIterator());

		while(!i.atEnd())
		{
			Node* p = i.GetNode();
			i++; // Increment it before it is deleted
			     // else iterator will get quite confused.
			delete p;
		}
		mRoot = 0;
		mSize= 0;
	}

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

	// Is the tree empty?
	bool IsEmpty() const { return mRoot == 0; }

	// Search for the node.
	// Returns 0 if node couldn't be found.
	Node* Find(const KeyType& keyToFind) const
	{
		Node* pNode = mRoot;

		while(pNode!=0)
		{
			KeyType key(pNode->GetKey());

			if (keyToFind == key)
			{
				// Found it! Return it! Wheee!
				return pNode;
			}			
			else if (keyToFind < key)
			{
				pNode = pNode->GetLeftChild();
			}
			else //keyToFind > key
			{
				pNode = pNode->GetRightChild();
			}
		}

		return 0;
	}
	
	// Get the root element. 0 if tree is empty.
	Node* GetRoot() const { return mRoot; }

	// Number of nodes in the tree.
	unsigned int Size() const { return mSize; }

	//------------------------------
	// Public Iterators
	//------------------------------
	Iterator GetIterator()			 
	{ 
		Iterator it(GetRoot());
		return it; 
	}
	ParentFirstIterator GetParentFirstIterator() 
	{
		ParentFirstIterator it(GetRoot());
		return it; 
	}
	ParentLastIterator GetParentLastIterator()
	{   
		ParentLastIterator it(GetRoot());
		return it;	
	}
	ByLevelIterator GetByLevelIterator()	 
	{ 
		ByLevelIterator it(GetRoot(),Size());
		return it;	
	}
	
	//------------------------------
	// Public Operators
	//------------------------------

	// operator [] for accesss to elements
	AccessClass operator[](const KeyType& k) 
	{
		return AccessClass(*this, k);
	}
private:

	//------------------------------
	// Disabled methods
	//------------------------------
	// Copy constructor and assignment operator deliberately 
	// defined but not implemented. The tree should never be 
	// copied, pass along references to it instead (or use auto_ptr to it).
	explicit BinTree(const BinTree& src); 
	BinTree& operator = (const BinTree& src);


	//------------------------------
	// Private Commands
	//------------------------------
	void SetRoot(Node* newRoot)
	{
		mRoot = newRoot;
		if (mRoot!=0)
			mRoot->SetParent(0);
	}

	// Insert a node into the tree without using any fancy balancing logic.
	// Returns false if that key already exist in the tree.
	bool Insert(Node* newNode)
	{
		bool result=true; // Assume success

		if (mRoot==0)
		{
			SetRoot(newNode);
			mSize = 1;
		}
		else
		{
			Node* pNode = mRoot;
			KeyType keyNew = newNode->GetKey();
			while (pNode)
			{
				KeyType key(pNode->GetKey());

				if (keyNew == key)
				{
					result = false;
					pNode = 0;
				} 
				else if (keyNew < key)
				{
					if (pNode->GetLeftChild()==0)
					{
						pNode->SetLeftChild(newNode);
						pNode = 0;
					}
					else
					{
						pNode = pNode->GetLeftChild();
					}
				} 
				else 
				{
					// keyNew > key
					if (pNode->GetRightChild()==0)
					{
						pNode->SetRightChild(newNode);
						pNode = 0;
					}
					else
					{
						pNode = pNode->GetRightChild();
					}
				}
			}

			if (result)
			{
				mSize++;
			}
		}
		
		return result;
	}

	// Rotate left.
	// Pull up node's right child and let it knock node down to the left
	void RotateLeft(Node* p)
	{		
		Node* right = p->GetRightChild();

		p->SetRightChild(right->GetLeftChild());
		
		if (p->IsLeftChild())
			p->GetParent()->SetLeftChild(right);
		else if (p->IsRightChild())
			p->GetParent()->SetRightChild(right);
		else
		{
			SetRoot(right);
		}
		right->SetLeftChild(p);
	}

	// Rotate right.
	// Pull up node's left child and let it knock node down to the right
	void RotateRight(Node* p)
	{		

		Node* left = p->GetLeftChild();

		p->SetLeftChild(left->GetRightChild());
		
		if (p->IsLeftChild())
			p->GetParent()->SetLeftChild(left);
		else if (p->IsRightChild())
			p->GetParent()->SetRightChild(left);
		else
		{
			SetRoot(left);
		}
		left->SetRightChild(p);
	}

	//------------------------------
	// Private Members
	//------------------------------
	Node* mRoot; // The top node. 0 if empty.	
	unsigned int mSize; // Number of nodes in the tree
};
#endif // _BINTREE_H_