一个C#泛形红黑树实现

作者：劈腿年代shui还相信真爱 | 来源：互联网 | 2023-09-17 10:18

看了一下算法导论，纸上得来终觉浅，绝知此事要躬行，所以把感兴趣的算法就写了下。红黑树在插入，删除，查找过程中都

看了一下算法导论&＃xff0c;纸上得来终觉浅&＃xff0c;绝知此事要躬行&＃xff0c;所以把感兴趣的算法就写了下。

红黑树在插入&＃xff0c;删除&＃xff0c;查找过程中都可以保持较高的运行效率&＃xff0c;sharpdevelop 中自定义的代码编辑控件中的document模型就是运用了红黑树。

RedBlackTree.cs

using System;

namespace Cn.Linc.Algorithms.BasicStructure
{
    public enum NodeColor
    {
        Black,
        Red
    }

    ///

    /// A binary search tree is a red-black tree if it satisfies the following red-black properties:
    /// 1) Every node is either red or black.
    /// 2) The root is black.
    /// 3) Every leaf (NIL) is black.
    /// 4) If a node is red, then both its children are black.
    /// 5) For each node, all paths from the node to descendant leaves contain the same number of black nodes.
    ///
    /// Red-black trees are one of many search-tree schemes that are "balanced" in order to
    /// guarantee that basic dynamic-set operations take O(lg n) time in the worst case.
    ///
    /// Notice, a null leaf node or parent node is colored black.
    ///
    /// More details please find in chapter 13, Introduction to Algorithms, Second Edition
    /// by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein   ISBN:0262032937
    /// The MIT Press © 2001 (1180 pages)
    ///

    /// RedBlackTreeNode type
    /// IComparable type
    public class RedBlackTree<T,S>
        where T: RedBlackTreeNode<S>
        where S: IComparable
    {
        private RedBlackTreeNode<S> root;

        ///

        /// Insert a new node, at first initialize the new node as red to keep the black height
        /// rule of red black tree. Insert the new node to proper position accordding to its value,
        ///  the fix the tree according to the defination of red black tree.
        ///

        ///
        public void InsertNode(S nodeValue)
        {
            RedBlackTreeNode<S> newNode &＃61; new RedBlackTreeNode<S>(nodeValue);
            if (root &＃61;&＃61; null)
            {
                root &＃61; newNode;
            }
            else
            {
                RedBlackTreeNode<S> tempX &＃61; root;
                RedBlackTreeNode<S> tempY &＃61; null;
                while (tempX !&＃61; null)
                {
                    tempY &＃61; tempX;
                    tempX &＃61; nodeValue.CompareTo(tempX.Value) > 0 ? tempX.RightChild : tempX.LeftChild;
                }
                if (nodeValue.CompareTo(tempY.Value) >&＃61; 0)
                {
                    tempY.RightChild &＃61; newNode;
                }
                else
                {
                    tempY.LeftChild &＃61; newNode;
                }
            }
            InsertFixup(newNode);
        }

        ///

        /// Delete node.
        /// If the node only have one or no child, just delete it.
        /// If the node has both left and right children, find its successor, delete it and copy its
        /// value to the node to be deleted.
        /// After deleting, fix up the tree according to defination.
        ///

        ///
        public void DeleteNode(T node)
        {
            if (node &＃61;&＃61; null)
                return;

            if ((node &＃61;&＃61; root) && (root.RightChild &＃61;&＃61; null) && (root.LeftChild &＃61;&＃61; null))
            {
                root &＃61; null;
                return;
            }

            RedBlackTreeNode<S> tempX &＃61; null, tempY &＃61; null;
            if (node.LeftChild &＃61;&＃61; null || node.RightChild &＃61;&＃61; null)
            {
                tempY &＃61; node;
            }
            else
            {
                tempY &＃61; GetSuccessor(node);
            }

            tempX &＃61; (tempY.LeftChild !&＃61; null) ? tempY.LeftChild : tempY.RightChild;

            if (tempY.ParentNode &＃61;&＃61; null)
                root &＃61; tempX;
            else
            {
                if (tempY &＃61;&＃61; tempY.ParentNode.LeftChild)
                {
                    tempY.ParentNode.LeftChild &＃61; tempX;
                }
                else
                {
                    tempY.ParentNode.RightChild &＃61; tempX;
                }
            }

            if (tempY !&＃61; node)
            {
                node.Value &＃61; tempY.Value;
            }

            // if black node is deleted the black height rule must be violated, fix it.
            if (tempY.Color &＃61;&＃61; NodeColor.Black)
                DeleteFixup(tempX,tempY.ParentNode);

        }

        ///

/// Find the node with specified value.
///

        /// specified value
        ///
        public RedBlackTreeNode<S> FindNode(S value)
        {
            RedBlackTreeNode<S> temp &＃61; root;
            if (root &＃61;&＃61; null)
            {
                return null;
            }
            do
            {
                if(value.CompareTo(temp.Value)&＃61;&＃61;0)
                {
                    return temp;
                }
                else if (temp.LeftChild !&＃61; null && value.CompareTo(temp.Value) < 0)
                {
                    temp &＃61; temp.LeftChild;
                }
                else if (temp.RightChild !&＃61; null && value.CompareTo(temp.Value) > 0)
                {
                    temp &＃61; temp.RightChild;
                }
                else
                {
                    return null;
                }
            } while (true);
        }

        ///

        /// Find the successer of specific node,
        /// if the right child is not empty, the successor is the far left node of the subtree.
        /// If it has a successor and its right child is null, the successor must be the nearest
        /// ancestor, and the left child of the successor is ancestor of the specific node.
        ///

        /// the specific node
        ///
        private RedBlackTreeNode<S> GetSuccessor(RedBlackTreeNode<S> currentNode)
        {
            RedBlackTreeNode<S> temp &＃61; null;
            if (currentNode.RightChild !&＃61; null)
            {
                temp &＃61; currentNode.RightChild;
                while (temp.LeftChild !&＃61; null)
                {
                    temp &＃61; temp.LeftChild;
                }
                return temp;
            }
            else
            {
                while (temp.ParentNode !&＃61; null)
                {
                    if (temp &＃61;&＃61; temp.ParentNode.LeftChild)
                    {
                        return temp.ParentNode;
                    }
                    else
                    {
                        temp &＃61; temp.ParentNode;
                    }
                }
                return null;
            }
        }
        ///

        /// Fix up red black tree after inserting node. Three cases:
        /// 1) the uncle of the node is red;
        /// 2) the uncle of the node is black and the node is right child(left rotate to case 3);
        /// 3) the uncle of the node is black and the node is left child;
        ///

        ///
        private void InsertFixup(RedBlackTreeNode<S> node)
        {
            RedBlackTreeNode<S> temp &＃61; null;

            while (node !&＃61; root && node.ParentNode.Color &＃61;&＃61; NodeColor.Red)
            {
                if (node.ParentNode &＃61;&＃61; node.ParentNode.ParentNode.LeftChild)
                {
                    temp &＃61; node.ParentNode.ParentNode.RightChild;
                    if (temp !&＃61; null && temp.Color &＃61;&＃61; NodeColor.Red)
                    {
                        node.ParentNode.Color &＃61; NodeColor.Black;
                        temp.Color &＃61; NodeColor.Black;
                        node.ParentNode.ParentNode.Color &＃61; NodeColor.Red;
                        node &＃61; node.ParentNode.ParentNode;
                    }
                    else
                    {
                        if (node &＃61;&＃61; node.ParentNode.RightChild)
                        {
                            node &＃61; node.ParentNode;
                            LeftRotate(node);
                        }
                        node.ParentNode.Color &＃61; NodeColor.Black;
                        node.ParentNode.ParentNode.Color &＃61; NodeColor.Red;

                        RightRotate(node.ParentNode.ParentNode);
                    }
                }
                else
                {
                    temp &＃61; node.ParentNode.ParentNode.LeftChild;
                    if (temp !&＃61; null && temp.Color &＃61;&＃61; NodeColor.Red)
                    {
                        node.ParentNode.Color &＃61; NodeColor.Black;
                        temp.Color &＃61; NodeColor.Black;
                        node.ParentNode.ParentNode.Color &＃61; NodeColor.Red;
                        node &＃61; node.ParentNode.ParentNode;
                    }
                    else
                    {
                        if (node &＃61;&＃61; node.ParentNode.LeftChild)
                        {
                            node &＃61; node.ParentNode;
                            RightRotate(node);
                        }
                        node.ParentNode.Color &＃61; NodeColor.Black;
                        node.ParentNode.ParentNode.Color &＃61; NodeColor.Red;

                        LeftRotate(node.ParentNode.ParentNode);

                    }
                }
            }
            root.Color &＃61; NodeColor.Black;
        }

        ///

        /// Fix up tree property after delete node from tree
        /// 1) node&＃39;s sibling w is red;
        /// 2) node&＃39;s sibling w is black, and both of w&＃39;s children are black;
        /// 3) node&＃39;s sibling w is black, w&＃39;s left child is red, and w&＃39;s right child is black;
        /// 4) node&＃39;s sibling w is black, and w&＃39;s right child is red
        ///

        ///
        private void DeleteFixup(RedBlackTreeNode<S> node,RedBlackTreeNode<S> parentNode)
        {
            RedBlackTreeNode<S> tempX &＃61; null;
            while (node !&＃61; root && (node &＃61;&＃61; null||node.Color &＃61;&＃61; NodeColor.Black))
            {
                if (node &＃61;&＃61; parentNode.LeftChild)
                {
                    tempX &＃61; parentNode.RightChild;
                    if (tempX !&＃61; null && tempX.Color &＃61;&＃61; NodeColor.Red)
                    {
                        tempX.Color &＃61; NodeColor.Black;
                        node.ParentNode.Color &＃61; NodeColor.Red;
                        LeftRotate(node.ParentNode);

                    }
                    else
                    {
                        if ((tempX.LeftChild &＃61;&＃61; null && tempX.RightChild &＃61;&＃61; null)
                            || (tempX.LeftChild.Color &＃61;&＃61; NodeColor.Black && tempX.RightChild.Color &＃61;&＃61; NodeColor.Black))
                        {
                            tempX.Color &＃61; NodeColor.Red;
                            node &＃61; parentNode;
                            parentNode &＃61; node.ParentNode;
                        }
                        else
                        {
                            if (tempX.RightChild &＃61;&＃61; null || tempX.RightChild.Color &＃61;&＃61; NodeColor.Black)
                            {
                                if (tempX.RightChild !&＃61; null)
                                {
                                    tempX.LeftChild.Color &＃61; NodeColor.Black;
                                    tempX.Color &＃61; NodeColor.Red;
                                }
                                RightRotate(tempX);
                                tempX &＃61; parentNode.RightChild;
                            }
                            tempX.Color &＃61; parentNode.Color;
                            parentNode.Color &＃61; NodeColor.Black;
                            tempX.RightChild.Color &＃61; NodeColor.Black;
                            LeftRotate(parentNode);
                            node &＃61; root;
                        }
                    }
                }
                else
                {
                    tempX &＃61; parentNode.LeftChild;
                    if (tempX !&＃61; null && tempX.Color &＃61;&＃61; NodeColor.Red)
                    {
                        tempX.Color &＃61; NodeColor.Black;
                        parentNode.Color &＃61; NodeColor.Red;
                        RightRotate(parentNode);
                    }
                    else
                    {
                        if ((tempX.LeftChild &＃61;&＃61; null && tempX.RightChild &＃61;&＃61; null)
                           || (tempX.LeftChild.Color &＃61;&＃61; NodeColor.Black && tempX.RightChild.Color &＃61;&＃61; NodeColor.Black))
                        {
                            tempX.Color &＃61; NodeColor.Red;
                            node &＃61; parentNode;
                            parentNode &＃61; node.ParentNode;
                        }
                        else
                        {
                            if (tempX.RightChild &＃61;&＃61; null || tempX.RightChild.Color &＃61;&＃61; NodeColor.Black)
                            {
                                if (tempX.RightChild !&＃61; null)
                                {
                                    tempX.RightChild.Color &＃61; NodeColor.Black;
                                    tempX.Color &＃61; NodeColor.Red;
                                }
                                LeftRotate(tempX);
                                tempX &＃61; parentNode.LeftChild;
                            }
                            tempX.Color &＃61; parentNode.Color;
                            parentNode.Color &＃61; NodeColor.Black;
                            tempX.LeftChild.Color &＃61; NodeColor.Black;
                            RightRotate(parentNode);
                            node &＃61; root;
                        }
                    }
                }
            }
            node.Color &＃61; NodeColor.Black;
        }

        ///

/// Right rotate the node, used when fix up tree property
///

        ///
        private void RightRotate(RedBlackTreeNode<S> node)
        {
            if (node.LeftChild &＃61;&＃61; null)
                return;
            RedBlackTreeNode<S> child &＃61; node.LeftChild;
            if (node.ParentNode !&＃61; null)
            {
                if (node.ParentNode.LeftChild !&＃61; null && node.ParentNode.LeftChild &＃61;&＃61; node)
                {
                    node.ParentNode.LeftChild &＃61; child;
                }
                else
                {
                    node.ParentNode.RightChild &＃61; child;
                }
            }
            else
            {
                node.LeftChild.ParentNode &＃61; null;
            }
            node.LeftChild &＃61; child.RightChild;
            child.RightChild &＃61; node;
            RecheckRoot();
        }

        ///

/// Left rotate the node, used when fix up tree property
///

        ///
        private void LeftRotate(RedBlackTreeNode<S> node)
        {
            if (node.RightChild &＃61;&＃61; null)
                return;

            RedBlackTreeNode<S> child &＃61; node.RightChild;
            if (node.ParentNode !&＃61; null)
            {
                if (node.ParentNode.LeftChild !&＃61; null && node.ParentNode.LeftChild &＃61;&＃61; node)
                {
                    node.ParentNode.LeftChild &＃61; child;
                }
                else
                {
                    node.ParentNode.RightChild &＃61; child;
                }
            }
            else
            {
                node.RightChild.ParentNode &＃61; null;
            }
            node.RightChild &＃61; child.LeftChild;
            child.LeftChild &＃61; node;
            RecheckRoot();
        }

        ///

/// the rotation may change the root, check and reset the root node.
///

        private void RecheckRoot()
        {
            while (root.ParentNode !&＃61; null)
            {
                root &＃61; root.ParentNode;
            }
        }
    }
}

RedBlackTreeNode.cs

using System;

namespace Cn.Linc.Algorithms.BasicStructure
{
    public class RedBlackTreeNode<T> where T : IComparable

    {
        private T value;

        public T Value
        {
            get { return this.value; }
            set { this.value &＃61; value; }
        }
        private NodeColor color;

        public NodeColor Color
        {
            get { return color; }
            set { color &＃61; value; }
        }
        private RedBlackTreeNode<T> leftChild;

        public RedBlackTreeNode<T> LeftChild
        {
            get { return leftChild; }
            set
            {
                if (value !&＃61; null)
                    value.ParentNode &＃61; this;
                leftChild &＃61; value;
            }
        }
        private RedBlackTreeNode<T> rightChild;

        public RedBlackTreeNode<T> RightChild
        {
            get { return rightChild; }
            set
            {
                if (value !&＃61; null)
                    value.ParentNode &＃61; this;
                rightChild &＃61; value;
            }
        }

        private RedBlackTreeNode<T> parentNode;

        public RedBlackTreeNode<T> ParentNode
        {
            get { return parentNode; }
            set { parentNode &＃61; value; }
        }

        public RedBlackTreeNode(T nodeValue)
        {
            value &＃61; nodeValue;
            color &＃61; NodeColor.Red;
        }
    }
}

转:https://www.cnblogs.com/SharpDeveloper/archive/2010/12/27/1918407.html

推荐阅读

list
欢乐的票圈重构之旅——RecyclerView的头尾布局增加

项目重构的Git地址：https:github.comrazerdpFriendCircletreemain-dev项目同步更新的文集：http:www.jianshu.comno ... [详细]

蜡笔小新 2023-12-11 19:09:56
list
向QTextEdit拖放文件的方法及实现步骤

本文介绍了在使用QTextEdit时如何实现拖放文件的功能，包括相关的方法和实现步骤。通过重写dragEnterEvent和dropEvent函数，并结合QMimeData和QUrl等类，可以轻松实现向QTextEdit拖放文件的功能。详细的代码实现和说明可以参考本文提供的示例代码。 ... [详细]

蜡笔小新 2023-12-14 16:06:38
list
推荐系统遇上深度学习(十七）详解推荐系统中的常用评测指标

原创：石晓文小小挖掘机2018-06-18笔者是一个痴迷于挖掘数据中的价值的学习人，希望在平日的工作学习中，挖掘数据的价值， ... [详细]

蜡笔小新 2023-12-13 19:35:25
ip
ASP.NET Tips: 获取插入记录的ID的方法详解

本文详细介绍了在ASP.NET中获取插入记录的ID的几种方法，包括使用SCOPE_IDENTITY()和IDENT_CURRENT()函数，以及通过ExecuteReader方法执行SQL语句获取ID的步骤。同时，还提供了使用这些方法的示例代码和注意事项。对于需要获取表中最后一个插入操作所产生的ID或马上使用刚插入的新记录ID的开发者来说，本文提供了一些有用的技巧和建议。 ... [详细]

蜡笔小新 2023-12-13 17:03:18
ip
Java项目管理工具及配置教程推荐

本文介绍了一些Java开发项目管理工具及其配置教程，包括团队协同工具worktil，版本管理工具GitLab，自动化构建工具Jenkins，项目管理工具Maven和Maven私服Nexus，以及Mybatis的安装和代码自动生成工具。提供了相关链接供读者参考。 ... [详细]

蜡笔小新 2023-12-13 06:45:16
list
Kotlin中扩展函数的惯用用法及其合理性

本文讨论了Kotlin中扩展函数的一些惯用用法以及其合理性。作者认为在某些情况下，定义扩展函数没有意义，但官方的编码约定支持这种方式。文章还介绍了在类之外定义扩展函数的具体用法，并讨论了避免使用扩展函数的边缘情况。作者提出了对于扩展函数的合理性的质疑，并给出了自己的反驳。最后，文章强调了在编写Kotlin代码时可以自由地使用扩展函数的重要性。 ... [详细]

蜡笔小新 2023-12-12 19:17:21
php
CEPH LIO iSCSI Gateway及其使用参考文档

本文介绍了CEPH LIO iSCSI Gateway以及使用该网关的参考文档，包括Ceph Block Device、CEPH ISCSI GATEWAY、USING AN ISCSI GATEWAY等。同时提供了多个参考链接，详细介绍了CEPH LIO iSCSI Gateway的配置和使用方法。 ... [详细]

蜡笔小新 2023-12-12 10:10:14
php
文件压缩解压的哈夫曼树实现

本文介绍了使用哈夫曼树实现文件压缩和解压的方法。首先对数据结构课程设计中的代码进行了分析，包括使用时间调用、常量定义和统计文件中各个字符时相关的结构体。然后讨论了哈夫曼树的实现原理和算法。最后介绍了文件压缩和解压的具体步骤，包括字符统计、构建哈夫曼树、生成编码表、编码和解码过程。通过实例演示了文件压缩和解压的效果。本文的内容对于理解哈夫曼树的实现原理和应用具有一定的参考价值。 ... [详细]

蜡笔小新 2023-12-11 14:13:46
ip
开源Keras Faster RCNN模型介绍及代码结构解析

本文介绍了开源Keras Faster RCNN模型的环境需求和代码结构，包括FasterRCNN源码解析、RPN与classifier定义、data_generators.py文件的功能以及损失计算。同时提供了该模型的开源地址和安装所需的库。 ... [详细]

蜡笔小新 2023-12-10 17:44:07
ip
Wince程序内存和存储内存的分析及作用

本文分析了Wince程序内存和存储内存的分布及作用。Wince内存包括系统内存、对象存储和程序内存，其中系统内存占用了一部分SDRAM，而剩下的30M为程序内存和存储内存。对象存储是嵌入式wince操作系统中的一个新概念，常用于消费电子设备中。此外，文章还介绍了主电源和后备电池在操作系统中的作用。 ... [详细]

蜡笔小新 2023-12-10 16:21:27
list
Java多线程总结（8）concurrent.locks包下的锁机制的使用

1Lock与ReadWriteLock1.1LockpublicinterfaceLock{voidlock();voidlockInterruptibl ... [详细]

蜡笔小新 2023-12-09 09:15:17
list
判断编码是否可立即解码的程序及电话号码一致性判断程序

本文介绍了两个编程题目，一个是判断编码是否可立即解码的程序，另一个是判断电话号码一致性的程序。对于第一个题目，给出一组二进制编码，判断是否存在一个编码是另一个编码的前缀，如果不存在则称为可立即解码的编码。对于第二个题目，给出一些电话号码，判断是否存在一个号码是另一个号码的前缀，如果不存在则说明这些号码是一致的。两个题目的解法类似，都使用了树的数据结构来实现。 ... [详细]

蜡笔小新 2023-12-09 02:47:15
case
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
tags
使用在线工具jsonschema2pojo根据json生成java对象

本文介绍了使用在线工具jsonschema2pojo根据json生成java对象的方法。通过该工具，用户只需将json字符串复制到输入框中，即可自动将其转换成java对象。该工具还能解析列表式的json数据，并将嵌套在内层的对象也解析出来。本文以请求github的api为例，展示了使用该工具的步骤和效果。 ... [详细]

蜡笔小新 2023-12-13 21:23:45
tags
开关稳压器设计的PCB布局布线的重要性及准则

本文介绍了开关稳压器设计中PCB布局布线的重要性，并提供了相应的准则。开关稳压器作为一种高效的电源，逐渐取代了线性稳压器。开关模式电源的工作原理是通过一定的开启时间和关闭时间来实现电压转换。开关频率并不是影响系统的最大因素，而开关转换的速度才是关键。在系统噪声方面，开关频率或其谐波可能会对系统产生影响。严格遵守PCB布局布线的准则，可以将开关模式电源的相关问题降到最小。 ... [详细]

蜡笔小新 2023-12-13 21:21:50

劈腿年代shui还相信真爱

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章