再回首数据结构—红黑树（一）

　　红黑树与AVL树一样同为二分搜索树，红黑树又称为是保持“黑平衡”的二叉树，红黑树最大高度为：2logn，红黑树由这么几个独特的特征：
　　1、每个节点或黑或红
　　2、根节点为黑色
　　3、每个叶子节点（最后的空节点）都为黑色
　　4、如果一个节点为红色，则他孩子节点全为黑色
　　5、从任意节点到叶子节点，经过的黑色节点为一样多的
　　6、所有红色节点都向左倾斜

　　在之前的二叉搜索树中我们在实现的节点结构中定义了用于存储元素的e、用于存放左子树的left、用于存放右子树的right等对象，而在AVL树中比二叉搜索树有所不同由于AVL需要维护左右子树的节点高度所以多了一个元素height用于存放节点的高度；
　　红黑树也是基于之前二叉搜索树变体而来的，在红黑树中节点也只比二叉搜索树多一个元素，二叉搜索树的节点由以下元素组成：

　　**e ：**用于存储节点元素
　　left： 用于存储左子树
　　**right：**用于存储右子树
　　**color：**用于标志节点颜色，节点是红色或黑色

红黑树的代码定义：

 type RBT struct {
    root    *RBTNode
    size    int
    compare Comparable
 }

 type RBTNode struct {
    e     interface{}
    left  *RBTNode
    right *RBTNode
    color bool
 }

根据红黑树的特性、定义可知：
　　1、大小为N的红黑树其高度不超过2logN
　　2、最坏情况下插入、查找元素的时间复杂度为：2logN
　　3、平均情况下插入、查找元素的平均复杂度为：logN

　　这里只简单介绍了红黑树的相关概念，下面将从代码实现的角度具体分析红黑树的实现；

FEATURED TAGS

Agent 大模型 ChatGPT HA 智能家居 LSM Linux Dapr 开发插件 Linux,虚拟机,ubuntu 缓存图片 Flink 反射内置函数 go 限流大数据,Spark,Kafka 面向对象镜像 docker,hadoop,镜像 kafka,java 求导链式法则微积分源码快照协议 ZooKeeper ZAB tomcat Hadoop Spark python 自动微分 React Native React Node.js Android Kafka lambda jvm rasp 框架 SPI asm maven idea 依赖管理 module helm 逻辑回归 S函数 IOS Fiddler Andriod Protocol Buffer kryo 车联网，大数据，神经网络字节序最小二乘法线性代数线性回归最大似然法网络编程大数据树莓派 Raspbian redis 海南分析人口函数式编程 clojure 线程并行 actor 红黑树数组动态数组 tcp 编程 markdown 二叉搜索树 AVL树数据结构 golang 梯度下降法 skaffold k8s 机器学习选法一致性算法分布式 paxos Raft 一致性协议引擎容器通信微服务 Kubernetes docker 文件系统 NFS 神经网络神经元深度学习 poi 反向传播 java 并发模型并发多线程 Scala

再回首数据结构—红黑树（一）

红黑树的代码定义：

CATALOG

FEATURED TAGS

FRIENDS