<h4>定义:</h4>
红黑树(定义1):红黑树是一棵二叉搜索树,在一棵红黑树内,每个节点或红或黑,红结点的两个子节点都是黑色,且从每个结点到其后代叶结点的每条简单路径上,都包含相同数目的黑结点。

红黑树(定义2):一棵红黑树是满足红黑性质的二叉搜索树。

<h4>相关概念:</h4>
二叉搜索树:对任何结点x,其左子树中的关键字最大不超过x.key,其右孩子中的关键字最小不低于x.key。
简单路径:如果路径上的各顶点均不互相重复,称这样的路径为简单路径。

下面主要从红黑树的性质、旋转、插入和删除四个方面记录红黑树的性质和操作:

<h3>红黑树的性质</h3>
1、一些基础概念:

结点的5个属性: color、key、left、right、p;

NIL: 如果一个结点没有子节点父节点,则该结点相应指针属性的值为 NIL;我们将这些 NIL 视为指向二叉搜索树的外部结点(叶节点的指针),把带关键字的结点视为树的内部结点

黑高(black-height):从某个结点x出发(不含该结点)到达一个叶结点的任意一条简单路径上的黑色结点个数成为该结点的黑高,记为bh(x)。 <u>红黑树的黑高为其根结点的黑高。</u>

红黑性质:
(1)每个结点或是红色的,或是黑色的;
(2)根节点是黑色的;
(3)每个叶结点(NIL)是黑色的;
(4)如果一个结点是红色的额,则它的两个子结点都是黑色的;
(5)对每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点。

通过对任何一条从根到叶子的简单路径上的各个结点的颜色进行约束,红黑树确保没有一条路径会比其他路径长出2倍,因而是近似于平衡的



<h3>旋转</h3>

Last modification:April 12th, 2018 at 01:04 am
If you think my article is useful to you, please feel free to appreciate