redblack.cs

C#写的类似于STL的集合类,首先是C#编写,可以用于.net变程.

                if (root != null)
                    root.IsRed = false;

                item = default(T);
                return false;
            }

            // Return the item from the node we're deleting.
            item = keyNode.item;

            // At a leaf or a node with one child which is a leaf. Remove the node.
            if (keyNode != node) {
                // The node we want to delete is interior. Move the item from the
                // node we're actually deleting to the key node.
                keyNode.item = node.item;
            }

            // If we have one child, replace the current with the child, otherwise,
            // replace the current node with null.
            Node replacement;
            if (node.left != null) {
                replacement = node.left;
                Debug.Assert(!node.IsRed && replacement.IsRed);
                replacement.IsRed = false;
            }
            else if (node.right != null) {
                replacement = node.right;
                Debug.Assert(!node.IsRed && replacement.IsRed);
                replacement.IsRed = false;
            }
            else
                replacement = null;

            if (parent == null) {
                Debug.Assert(root == node);
                root = replacement;
            }
            else if (parent.left == node)
                parent.left = replacement;
            else {
                Debug.Assert(parent.right == node);
                parent.right = replacement;
            }

            // Color the root black, in case it was colored red above.
            if (root != null)
                root.IsRed = false;

            // Update item count.
            count -= 1;

            // And we're done.
            return true;
        }

        /// <summary>
        /// Delete all the items in a range, identified by a RangeTester delegate.
        /// </summary>
        /// <param name="rangeTester">The delegate that defines the range to delete.</param>
        /// <returns>The number of items deleted.</returns>
        public int DeleteRange(RangeTester rangeTester)
        {
            bool deleted;
            int count = 0;
            T dummy;

            do {
                deleted = DeleteItemFromRange(rangeTester, true, out dummy);
                if (deleted)
                    ++count;
            } while (deleted);

            return count;
        }

        /// <summary>
        /// Count the items in a custom range in the tree. The range is determined by 
        /// a RangeTester delegate.
        /// </summary>
        /// <param name="rangeTester">The delegate that defines the range.</param>
        /// <returns>The number of items in the range.</returns>
        public int CountRange(RangeTester rangeTester)
        {
            return CountRangeUnderNode(rangeTester, root, false, false);
        }

        /// <summary>
        /// Count all the items in a custom range, under and including node.
        /// </summary>
        /// <param name="rangeTester">The delegate that defines the range.</param>
        /// <param name="node">Node to begin enumeration. May be null.</param>
        /// <param name="belowRangeTop">This node and all under it are either in the range or below it.</param>
        /// <param name="aboveRangeBottom">This node and all under it are either in the range or above it.</param>
        /// <returns>The number of items in the range, under and include node.</returns>
        private int CountRangeUnderNode(RangeTester rangeTester, Node node, bool belowRangeTop, bool aboveRangeBottom)
        {
            if (node != null) {
                if (belowRangeTop && aboveRangeBottom) {
                    // This node and all below it must be in the range. Use the predefined count.
                    return node.Count;
                }

                int compare = rangeTester(node.item);
                int count;

                if (compare == 0) {
                    count = 1;  // the node itself
                    count += CountRangeUnderNode(rangeTester, node.left, true, aboveRangeBottom);
                    count += CountRangeUnderNode(rangeTester, node.right, belowRangeTop, true);
                }
                else if (compare < 0) {
                    count = CountRangeUnderNode(rangeTester, node.right, belowRangeTop, aboveRangeBottom);
                }
                else { // compare > 0
                    count = CountRangeUnderNode(rangeTester, node.left, belowRangeTop, aboveRangeBottom);
                }

                return count;
            }
            else {
                return 0;
            }
        }

        /// <summary>
        /// Find the first item in a custom range in the tree, and it's index. The range is determined
        /// by a RangeTester delegate.
        /// </summary>
        /// <param name="rangeTester">The delegate that defines the range.</param>
        /// <param name="item">Returns the item found, if true was returned.</param>
        /// <returns>Index of first item in range if range is non-empty, -1 otherwise.</returns>
        public int FirstItemInRange(RangeTester rangeTester, out T item)
        {
            Node node = root, found = null;
            int curCount = 0, foundIndex = -1;

            while (node != null) {
                int compare = rangeTester(node.item);

                if (compare == 0) {
                    found = node;
                    if (node.left != null)
                        foundIndex = curCount + node.left.Count;
                    else
                        foundIndex = curCount;
                }

                if (compare >= 0)
                    node = node.left;
                else {
                    if (node.left != null)
                        curCount += node.left.Count + 1;
                    else
                        curCount += 1;
                    node = node.right;
                }
            }

            if (found != null) {
                item = found.item;
                return foundIndex;
            }
            else {
                item = default(T);
                return -1;
            }
        }

        /// <summary>
        /// Find the last item in a custom range in the tree, and it's index. The range is determined
        /// by a RangeTester delegate.
        /// </summary>
        /// <param name="rangeTester">The delegate that defines the range.</param>
        /// <param name="item">Returns the item found, if true was returned.</param>
        /// <returns>Index of the item if range is non-empty, -1 otherwise.</returns>
        public int LastItemInRange(RangeTester rangeTester, out T item)
        {
            Node node = root, found = null;
            int curCount = 0, foundIndex = -1;

            while (node != null) {
                int compare = rangeTester(node.item);

                if (compare == 0) {
                    found = node;
                    if (node.left != null)
                        foundIndex = curCount + node.left.Count;
                    else
                        foundIndex = curCount;
                }

                if (compare <= 0) {
                    if (node.left != null)
                        curCount += node.left.Count + 1;
                    else
                        curCount += 1;
                    node = node.right;
                }
                else
                    node = node.left;
            }

            if (found != null) {
                item = found.item;
                return foundIndex;
            }
            else {
                item = default(T);
                return foundIndex;
            }
        }

        #endregion Ranges

#if DEBUG
		/// <summary>
		/// Prints out the tree.
		/// </summary>
		public void Print() {
			PrintSubTree(root, "", "");
			Console.WriteLine();
		}

		/// <summary>
		/// Prints a sub-tree.
		/// </summary>
		/// <param name="node">Node to print from</param>
		/// <param name="prefixNode">Prefix for the node</param>
		/// <param name="prefixChildren">Prefix for the node's children</param>
		private void PrintSubTree(Node node, string prefixNode, string prefixChildren) {
			if (node == null)
				return;

			// Red nodes marked as "@@", black nodes as "..".
            Console.WriteLine("{0}{1} {2,4} {3}", prefixNode, node.IsRed ? "@@" : "..", node.Count, node.item.ToString());

			PrintSubTree(node.left, prefixChildren + "|-L-", prefixChildren + "|  ");
			PrintSubTree(node.right, prefixChildren + "|-R-", prefixChildren + "   ");
		}

		/// <summary>
		/// Validates that the tree is correctly sorted, and meets the red-black tree 
		/// axioms.
		/// </summary>
		public void Validate() {
			Debug.Assert(comparer != null, "Comparer should not be null");

			if (root == null) {
				Debug.Assert(0 == count, "Count in empty tree should be 0.");
			
			}
			else {
				Debug.Assert(! root.IsRed, "Root is not black");
				int blackHeight;
				int nodeCount = ValidateSubTree(root, out blackHeight);
				Debug.Assert(nodeCount == this.count, "Node count of tree is not correct.");
			}
		}

		/// <summary>
		/// Validates a sub-tree and returns the count and black height.
		/// </summary>
		/// <param name="node">Sub-tree to validate. May be null.</param>
		/// <param name="blackHeight">Returns the black height of the tree.</param>
        /// <returns>Returns the number of nodes in the sub-tree. 0 if node is null.</returns>
		private int ValidateSubTree(Node node, out int blackHeight) {
			if (node == null) {
				blackHeight = 0;
				return 0;
			}

			// Check that this node is sorted with respect to any children.
			if (node.left != null)
                Debug.Assert(comparer.Compare(node.left.item, node.item) <= 0, "Left child is not less than or equal to node");
            if (node.right != null)
                Debug.Assert(comparer.Compare(node.right.item, node.item) >= 0, "Right child is not greater than or equal to node");

            // Check that the two-red rule is not violated.
			if (node.IsRed) {
				if (node.left != null)
					Debug.Assert(! node.left.IsRed, "Node and left child both red");
				if (node.right != null) 
					Debug.Assert(! node.right.IsRed, "Node and right child both red");
			}

			// Validate sub-trees and get their size and heights.
			int leftCount, leftBlackHeight;
			int rightCount, rightBlackHeight;
            int ourCount;

			leftCount = ValidateSubTree(node.left, out leftBlackHeight);
			rightCount = ValidateSubTree(node.right, out rightBlackHeight);
            ourCount = leftCount + rightCount + 1;

            Debug.Assert(ourCount == node.Count);

			// Validate the equal black-height rule.
			Debug.Assert(leftBlackHeight == rightBlackHeight, "Black heights are not equal");

			// Calculate our black height and return the count
			blackHeight = leftBlackHeight;
			if (! node.IsRed)
				blackHeight += 1;
            return ourCount;
		}
#endif //DEBUG

    }

}