一个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

推荐阅读

int
图像相似度对比的多种方法

本文介绍了几种常用的图像相似度对比方法，包括直方图方法、图像模板匹配、PSNR峰值信噪比、SSIM结构相似性和感知哈希算法。每种方法都有其优缺点，适用于不同的应用场景。 ... [详细]

蜡笔小新 2024-11-13 11:04:56
get
python模块之正则

re模块可以读懂你写的正则表达式根据你写的表达式去执行任务用re去操作正则正则表达式使用一些规则来检测一些字符串是否符合个人要求，从一段字符串中找到符合要求的内容。在 ... [详细]

蜡笔小新 2024-11-14 15:52:38
get
Go Echo 框架入门指南【1】

本文介绍了 Go 语言中的高性能、可扩展、轻量级 Web 框架 Echo。Echo 框架简单易用，仅需几行代码即可启动一个高性能 HTTP 服务。 ... [详细]

蜡笔小新 2024-11-14 18:30:58
get
Cookie学习小结

Cookie学习小结 ... [详细]

蜡笔小新 2024-11-14 16:26:25
get
Python基础：使用NLTK和Python构建机器学习应用

本文节选自《NLTK基础教程——用NLTK和Python库构建机器学习应用》一书的第1章第1.2节，作者Nitin Hardeniya。本文将带领读者快速了解Python的基础知识，为后续的机器学习应用打下坚实的基础。 ... [详细]

蜡笔小新 2024-11-13 21:23:34
post
InfluxDB、collectd与Grafana的详细安装与配置指南

本文详细介绍了 InfluxDB、collectd 和 Grafana 的安装与配置流程。首先，按照启动顺序依次安装并配置 InfluxDB、collectd 和 Grafana。InfluxDB 作为时序数据库，用于存储时间序列数据；collectd 负责数据的采集与传输；Grafana 则用于数据的可视化展示。文中提供了 collectd 的官方文档链接，便于用户参考和进一步了解其配置选项。通过本指南，读者可以轻松搭建一个高效的数据监控系统。 ... [详细]

蜡笔小新 2024-11-11 19:54:24
get
在 QQmlPropertyMap 的派生类中无法调用槽函数或 Q_INVOKABLE 方法？

在尝试对 QQmlPropertyMap 类进行测试驱动开发时，发现其派生类中无法正常调用槽函数或 Q_INVOKABLE 方法。这可能是由于 QQmlPropertyMap 的内部实现机制导致的，需要进一步研究以找到解决方案。 ... [详细]

蜡笔小新 2024-11-11 15:34:22
grid
WordPress Duplicator 0.4.4 版本存在跨站脚本攻击漏洞分析

在对WordPress Duplicator插件0.4.4版本的安全评估中，发现其存在跨站脚本（XSS）攻击漏洞。此漏洞可能被利用进行恶意操作，建议用户及时更新至最新版本以确保系统安全。测试方法仅限于安全研究和教学目的，使用时需自行承担风险。漏洞编号：HTB23162。 ... [详细]

蜡笔小新 2024-11-10 13:16:43
int
Python3爬虫实战：突破网站反爬虫机制的方法

本文详细探讨了使用Python3编写爬虫时如何应对网站的反爬虫机制，通过实例讲解了如何模拟浏览器访问，帮助读者更好地理解和应用相关技术。 ... [详细]

蜡笔小新 2024-11-14 19:48:54
get
普通树(每个节点可以有任意数量的子节点)级序遍历

普通树(每个节点可以有任意数量的子节点)级序遍历 ... [详细]

蜡笔小新 2024-11-14 18:53:26
int
DB2 9 认证指南（733 测验）第二部分：数据处理

本文介绍 DB2 中的基本概念，重点解释事务单元（UOW）和事务的概念。事务单元是指作为单个原子操作执行的一个或多个 SQL 查询。 ... [详细]

蜡笔小新 2024-11-14 16:58:15
int
Automated Region Validation in AWS SDK Provider

This feature automatically validates new regions using the AWS SDK, ensuring compatibility and accuracy. ... [详细]

蜡笔小新 2024-11-13 21:40:42
get
杜甫《喜晴》的两种英译比较

本文对比了杜甫《喜晴》的两种英文翻译版本：a. Pleased with Sunny Weather 和 b. Rejoicing in Clearing Weather。a 版由 alexcwlin 翻译并经 Adam Lam 编辑，b 版则由哈佛大学的宇文所安教授 (Prof. Stephen Owen) 翻译。 ... [详细]

蜡笔小新 2024-11-12 15:02:28
get
解决Bootstrap DataTable Ajax请求重复问题

在最近的一个项目中，我们使用了JQuery DataTable进行数据展示，虽然使用起来非常方便，但在测试过程中发现了一个问题：当查询条件改变时，有时查询结果的数据不正确。通过FireBug调试发现，点击搜索按钮时，会发送两次Ajax请求，一次是原条件的请求，一次是新条件的请求。 ... [详细]

蜡笔小新 2024-11-12 13:59:27
get
Xcode 多项目联合调试技巧与实践

在软件开发过程中，经常需要将多个项目或模块进行集成和调试，尤其是当项目依赖于第三方开源库（如Cordova、CocoaPods）时。本文介绍了如何在Xcode中高效地进行多项目联合调试，分享了一些实用的技巧和最佳实践，帮助开发者解决常见的调试难题，提高开发效率。 ... [详细]

蜡笔小新 2024-11-11 18:24:27

劈腿年代shui还相信真爱

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

Tags | 热门标签

RankList | 热门文章