C#数据结构-红黑树实现

参考网址： https://zhuanlan.zhihu.com/p/353948322

二叉查找树，他对于大多数情况下的查找和插入在效率上来说是没有问题的，但是他在最差的情况下效率比较低。

红黑树保证在最坏的情况下插入和查找效率都能保证在对数的时间复杂度内完成。

红黑树的性质：

性质1.节点是红色或黑色
性质2.根是黑色
性质3.所有叶子都是黑色（叶子是NIL节点）
性质4.如果一个节点是红的，则它的两个子节点都是黑的(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5.从任一节点到其叶子的所有路径都包含相同数目的黑色节点。

注：清晰理解红黑树的性质，对红黑树算法的实现有非常重要的作用。

最近发现一个旧金山大学计算机系的一个网站，可以根据你输入的插入、删除和查找的的值，提供非常直观的插入、删除和查找动画展示，删除选取的左子树的最大节点作为删除节点的替换节点。超链接地址

简述一下，红黑树的查找和删除的实现原理：

红黑树的查找：

将要查找的value和节点的value比较，如果小于，那么就在Left Node节点查找；如果大于，则在Right Node节点查找，如果相等，更新Value。

红黑树的删除：

1.如果删除节点没有子节点，直接返回null

2.如果只有一个子节点，返回其子节点代替删除节点即可

3.当左右子节点都不为空时，找到其右子树中的最小节点，替换删除节点的位置

在实现原理上，红黑树的查找和删除，跟二叉查找树是一致的。不过，为了保证树在插入、删除完成之后，保持红黑树的平衡状态，需要实现更多更复杂的逻辑。

using System;
using System.Collections.Generic;

namespace StructScript
{
    /// 红黑树定义：
    /// 性质1.节点是红色或黑色
    /// 性质2.根是黑色
    /// 性质3.所有叶子都是黑色（叶子是NIL节点）
    /// 性质4.如果一个节点是红的，则它的两个子节点都是黑的(从每个叶子到根的所有路径上不能有两个连续的红色节点)
    /// 性质5.从任一节点到其叶子的所有路径都包含相同数目的黑色节点。
    public class RedBlackTree<T>
    {
        //根节点
        private RedBlackTreeNode<T> mRoot;
        //比较器
        private Comparer<T> mComparer;
        private const bool RED = true;
        private const bool BLACK = false;

        public RedBlackTree()
        {
            mRoot = null;
            mComparer = Comparer<T>.Default;
        }

        public bool Contains(T value)
        {
            RedBlackTreeNode<T> node;
            return Contain(value, out node);
        }

        public bool Contain(T value, out RedBlackTreeNode<T> newNode)
        {
            if (value == null)
            {
                throw new ArgumentNullException();
            }
            newNode = null;
            RedBlackTreeNode<T> node = mRoot;
            while (node != null)
            {
                int comparer = mComparer.Compare(value, node.Data);
                if (comparer > 0)
                {
                    node = node.RightChild;
                }
                else if (comparer < 0)
                {
                    node = node.LeftChild;
                }
                else
                {
                    newNode = node;
                    return true;
                }
            }
            return false;
        }

        public void Add(T value)
        {
            if (mRoot == null)
            {
                // 根节点是黑色的
                mRoot = new RedBlackTreeNode<T>(value, BLACK);
            }
            else
            {
                // 新插入节点是红色的
                Insert1(new RedBlackTreeNode<T>(