本质还是一颗二叉搜索树，只是在其基础上增加了AddFix和RemoveFix来做平衡性修正，确保不会出现极端不平衡的情况。 【规则】a)根节点为黑b)红色节点的子节点只能是2个黑c)黑色节点的子节点只能是：1个红，2个红，2个黑或没有子节点，不可能出现1个黑（如下图所示）d) 任一结点到各个叶子结点的路径都包含数量相同的黑色结点e)新添加的节点一开始总是为红色，后面根据需要调整颜色 #根据上面的规则，下面的这些情况也不可能出现a)  b) c)  #红黑树看似很复杂，其实只是过程比较繁琐而已。他对什么情况做什么操作都已经规定死了，只要照着这些规定的步骤走就行了。【添加】#当遇到新添加节点后，出

本质还是一颗二叉搜索树，只是在其基础上增加了AddFix和RemoveFix来做平衡性修正，确保不会出现极端不平衡的情况。 【规则】a)根节点为黑b)红色节点的子节点只能是2个黑c)黑色节点的子节点只能是：1个红，2个红，2个黑或没有子节点，不可能出现1个黑（如下图所示）d) 任一结点到各个叶子结点的路径都包含数量相同的黑色结点e)新添加的节点一开始总是为红色，后面根据需要调整颜色 #根据上面的规则，下面的这些情况也不可能出现a)  b) c)  #红黑树看似很复杂，其实只是过程比较繁琐而已。他对什么情况做什么操作都已经规定死了，只要照着这些规定的步骤走就行了。【添加】#当遇到新添加节点后，出

title:红黑树date:2022-03-3110:41:30sidebar:autocategories:-数据结构-二叉树tags:-红黑树一、树1.1树的定义树是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。树结构是一种非线性存储结构，存储的是具有“一对多”关系的数据元素的集合。1.2树的特点每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；树是一种特殊的图1.3树与图的区别树是没有环的图（在图里面，环的路线是开始

title:红黑树date:2022-03-3110:41:30sidebar:autocategories:-数据结构-二叉树tags:-红黑树一、树1.1树的定义树是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。树结构是一种非线性存储结构，存储的是具有“一对多”关系的数据元素的集合。1.2树的特点每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；树是一种特殊的图1.3树与图的区别树是没有环的图（在图里面，环的路线是开始