redblack.cs

game implemented java

			if (speedArray[key] == double.MaxValue)
				return;
			//MessageBox.Show("REMOVE: "+objName + " " +this.Size());
		
			// find node
			RedBlackNode node;

			// see if node to be deleted was the last one found
			if(key == lastNodeFound.Data.id)
				node = lastNodeFound;
			else
			{	// not found, must search		
				node = rbTree;
				while(!isSentinelNode(node))
				{
					if(key == node.Data.id)
						break;
					if(key < node.Data.id)
						node = node.Left;
					else
						node = node.Right;
				}

				if(isSentinelNode(node))
					throw(new RedBlackException("speedArray thought node existed"));// key not found
			}

			Delete(node);

			setMinTags(rbTree);
			
			intCount = intCount - 1;
			speedArray[key] = double.MaxValue;
		}
		///<summary>
		/// Delete
		/// Delete a node from the tree and restore red black properties
		///<summary>
		private void Delete(RedBlackNode z)
		{
			// A node to be deleted will: 
			//		1. be a leaf with no children
			//		2. have one child
			//		3. have two children
			// If the deleted node is red, the red black properties still hold.
			// If the deleted node is black, the tree needs rebalancing

			RedBlackNode x = new RedBlackNode();	// work node to contain the replacement node
			RedBlackNode y;							// work node 

			// find the replacement node (the successor to x) - the node one with 
			// at *most* one child. 
			if(isSentinelNode(z.Left) || isSentinelNode(z.Right)) 
				y = z;						// node has sentinel as a child
			else 
			{
				// z has two children, find replacement node which will 
				// be the leftmost node greater than z
				y = z.Right;				        // traverse right subtree	
				while(!isSentinelNode(y.Left))		// to find next node in sequence
					y = y.Left;
			}

			// at this point, y contains the replacement node. it's content will be copied 
			// to the valules in the node to be deleted

			// x (y's only child) is the node that will be linked to y's old parent. 
			if(!isSentinelNode(y.Left))
				x = y.Left;					
			else
				x = y.Right;					

			// replace x's parent with y's parent and
			// link x to proper subtree in parent
			// this removes y from the chain
			x.Parent = y.Parent;
			if(y.Parent != null)
				if(y.Data.id == y.Parent.Left.Data.id)
					y.Parent.Left = x;
				else
					y.Parent.Right = x;
			else
			{
				rbTree = x;			// make x the root node
				setMinTags(rbTree);
			}
			RedBlackNode temp = y;
			while (temp.Data.id != z.Data.id)	//Update tags (important in case 3)
			{
				setMinTags(temp);
				temp = temp.Parent;
			}
			temp = null;

			// copy the values from y (the replacement node) to the node being deleted.
			// note: this effectively deletes the node. 
			if(y.Data.id != z.Data.id) 
			{
				z.Data	= y.Data;
				setMinTags(z);
			}
			temp = z.Parent;
			while (temp != null)
			{
				setMinTags(temp);
				temp = temp.Parent;
			}

			if(y.Color == RedBlackNode.BLACK)
				RestoreAfterDelete(x);

			lastNodeFound = sentinelNode;
		}

		///<summary>
		/// RestoreAfterDelete
		/// Deletions from red-black trees may destroy the red-black 
		/// properties. Examine the tree and restore. Rotations are normally 
		/// required to restore it
		///</summary>
		private void RestoreAfterDelete(RedBlackNode x)
		{
			// maintain Red-Black tree balance after deleting node 			

			RedBlackNode y;

			while(x.Data.id != rbTree.Data.id && x.Color == RedBlackNode.BLACK) 
			{
				if(x.Data.id == x.Parent.Left.Data.id)			// determine sub tree from parent
				{
					y = x.Parent.Right;			// y is x's sibling 
					if(y.Color == RedBlackNode.RED) 
					{	// x is black, y is red - make both black and rotate
						y.Color			= RedBlackNode.BLACK;
						x.Parent.Color	= RedBlackNode.RED;
						RotateLeft(x.Parent);
						setMinTags(x);
						setMinTags(y);
						setMinTags(x.Parent);
						y = x.Parent.Right;
					}
					if(y.Left.Color == RedBlackNode.BLACK && 
						y.Right.Color == RedBlackNode.BLACK) 
					{	// children are both black
						y.Color = RedBlackNode.RED;		// change parent to red
						setMinTags(x);
						x = x.Parent;					// move up the tree
					} 
					else 
					{
						if(y.Right.Color == RedBlackNode.BLACK) 
						{
							y.Left.Color	= RedBlackNode.BLACK;
							y.Color			= RedBlackNode.RED;
							RotateRight(y);
							y				= x.Parent.Right;
						}
						y.Color			= x.Parent.Color;
						x.Parent.Color	= RedBlackNode.BLACK;
						y.Right.Color	= RedBlackNode.BLACK;
						RotateLeft(x.Parent);
						x = rbTree;
						setMinTags(x.Left);
						setMinTags(x.Right);
						setMinTags(x);
					}
				} 
				else 
				{	// right subtree - same as code above with right and left swapped
					y = x.Parent.Left;
					if(y.Color == RedBlackNode.RED) 
					{
						y.Color			= RedBlackNode.BLACK;
						x.Parent.Color	= RedBlackNode.RED;
						RotateRight (x.Parent);
						setMinTags(x);
						setMinTags(y);
						setMinTags(x.Parent);
						y = x.Parent.Left;
					}
					if(y.Right.Color == RedBlackNode.BLACK && 
						y.Left.Color == RedBlackNode.BLACK) 
					{
						y.Color = RedBlackNode.RED;
						setMinTags(x);
						x		= x.Parent;
					} 
					else 
					{
						if(y.Left.Color == RedBlackNode.BLACK) 
						{
							y.Right.Color	= RedBlackNode.BLACK;
							y.Color			= RedBlackNode.RED;
							RotateLeft(y);
							y				= x.Parent.Left;
						}
						y.Color			= x.Parent.Color;
						x.Parent.Color	= RedBlackNode.BLACK;
						y.Left.Color	= RedBlackNode.BLACK;
						RotateRight(x.Parent);
						x = rbTree;
						setMinTags(x.Left);
						setMinTags(x.Right);
						setMinTags(x);
					}
				}
			}
			x.Color = RedBlackNode.BLACK;
		}
		
		///<summary>
		/// Clear
		/// Empties or clears the tree
		///<summary>
		public void Clear ()
		{
			rbTree      = sentinelNode;
			intCount    = 0;
			for (int i=0;i<speedArray.Length;i++)
				speedArray[i] = 0;
		}
		///<summary>
		/// Size
		/// returns the size (number of nodes) in the tree
		///<summary>
		public int Size()
		{
			// number of keys
			return intCount;
		}
		///<summary>
		/// Equals
		///<summary>
		public override bool Equals(object obj)
		{
			if(obj == null)
				return false;
			
			if(!(obj is RedBlackNode ))
				return false;
			
			if(this == obj)
				return true;
			
			return (ToString().Equals(((RedBlackNode)(obj)).ToString()));
			
		}
		///<summary>
		/// HashCode
		///<summary>
		public override int GetHashCode()
		{
			return intHashCode;
		}
		///<summary>
		/// ToString
		///<summary>
		public override string ToString()
		{
			return strIdentifier.ToString();
		}
		public double GetValueAtID (int id)
		{
			return speedArray[id];
		}
		public AStarNode GetMin()
		{
			RedBlackNode curr = rbTree;
			while (!isSentinelNode(curr))
			{
				if (curr.Left_Min < curr.Right_Min)
				{
					if (curr.Data.FofN <= curr.Left_Min)
						return curr.Data;
					else
						curr = curr.Left;
				}
				else
				{
					if (curr.Data.FofN <= curr.Right_Min)
						return curr.Data;
					else
						curr = curr.Right;
				}
			}
			throw (new RedBlackException("Somehow failed to find a maximum value "+this.Size()));
		}	
		private bool isSentinelNode (RedBlackNode n)
		{
			return (n.Data.id == -1 && n.Left == null && n.Right == null);
		}
		private void setMinTags (RedBlackNode n)
		{
			if (n == null || isSentinelNode(n))
				return;

			n.Left_Min = Math.Min(Math.Min(n.Left.Data.FofN,n.Left.Left_Min),n.Left.Right_Min);
			n.Right_Min = Math.Min(Math.Min(n.Right.Data.FofN,n.Right.Left_Min),n.Right.Right_Min);
			//return n;
		}
	}
}