BN089-BS开发框架MVC4版/source20131023/Zephyr.Net/Zephyr.Utils/Document/Excel/ExcelLibrary/CodeLib/BinaryTree/RedBlackTree/RedBlackTree.cs

这里只显示每个文件的开头 60 行。登录后可以解锁完整代码。

微信扫码关注公众号，代码整理好后第一时间通知你。

using System;
using System.Collections.Generic;
using System.Text;

namespace QiHe.CodeLib
{
    ///<summary>
    ///A red-black tree must satisfy these properties:
    ///1. The root is black. 
    ///2. All leaves are black. 
    ///3. Red nodes can only have black children. 
    ///4. All paths from a node to its leaves contain the same number of black nodes.
    ///</summary>
    public class RedBlackTree<TItem> : BinarySearchTreeBase<TItem, RedBlackTreeNode<TItem>>
        where TItem : IComparable<TItem>
    {
        public override RedBlackTreeNode<TItem> Nil
        {
            get { return RedBlackTreeNode<TItem>.Nil; }
        }

        public override void Insert(RedBlackTreeNode<TItem> node)
        {
            base.Insert(node);
            node.Color = NodeColor.Red;
            FixupAfterInsert(node);
        }

        /// <summary>
        /// restores the red-black properties to the search tree
        /// </summary>
        /// <param name="node"></param>
        private void FixupAfterInsert(RedBlackTreeNode<TItem> node)
        {
            while (node.Parent.Color == NodeColor.Red)
            {
                if (node.Parent.IsLeftChild)
                {
                    RedBlackTreeNode<TItem> uncle = node.Parent.Parent.Right;
                    // case 1
                    if (uncle.Color == NodeColor.Red)
                    {
                        uncle.Color = NodeColor.Black;
                        node.Parent.Color = NodeColor.Black;
                        node.Parent.Parent.Color = NodeColor.Red;
                        node = node.Parent.Parent;
                    }
                    else
                    {
                        // case 2
                        if (node.IsRightChild)
                        {
                            node = node.Parent;
                            RotateLeft(node);
                        }
                        // case 3
                        node.Parent.Color = NodeColor.Black;
                        node.Parent.Parent.Color = NodeColor.Red;
                        RotateRight(node.Parent.Parent);
                    }