红黑树是一种自平衡的二叉查找树，是一种常用的数据结构 1972年出现，在当时被称为平衡二叉B树。后来1978年被修改为如今的“红黑树” 它是一个特殊的二叉查找树，红黑树的每一个节点上都有储存位表示节点的颜色 每一个节点可以是红或者黑，红黑树不是高度平衡的，而是通过红黑规则来实现的 回忆一下：平衡二叉树要求左右子树高度差不能大于1 所以说： 红黑树是一个二叉查找树：小在左 大在右 红黑树不是高度平衡的 不是要求左右子树高度差小于1 特有的红黑规则： 分析红黑规则： 1.每一个节点可能是红色的，也可能是黑色的 2.根节点必须是黑色的 3.如果一个节点没有子节点或者父节点，那么节点的指针属性值为Nil 视为叶节点 4.如果某一个节点是红色的，那么它的子节点必须是黑色的（不能出现两个红色节点相连） 5.对于每一个节点，从这个节点到后代所有节点的简单路径上，均包含相同数目的黑色节点 所以我们现在可以分析一个红黑树节点的构成 A.父节点地址 B.值大小 C左子节点地址 D.右节点地址 E.颜色 举个很简单的例子 根节点就没有父节点 那么父节点的位置就记录为Nil(空的意思) 这个记录的细节就是记录一个地址：指向一个数据为空的节点（叶节点） —————————————————————————————————————————————————————————————————— 添加的节点：默认是红色的（红色的效率高）
![[<span style='color:red;'>数据</span><span style='color:red;'>结构</span>]<span style='color:red;'>红</span><span style='color:red;'>黑</span><span style='color:red;'>树</span><span style='color:red;'>的</span><span style='color:red;'>原理</span>及其实现](https://img-blog.csdnimg.cn/direct/285c8c4970e149d09320750d87c96453.png)
