红黑树的规则与Java示例(Red-Black tree)

如果涉及频繁的插入和删除操作,那么,应该首选红黑树。

红黑树的平衡规则

红黑树的特点

1、节点由红色或黑色组成。

2、根节点始终是黑色的,每个叶子(NULL)都是黑色的。

3、如果节点为红色,则其子节点均为黑色--红色节点之间不相邻。

4、从根节点到末尾节点的每个路径,都有相同数量的黑色节点。

说明:如果节点没有子节点,将其称为叶节点(叶子),因为它位于树的外围,子树被定义为,可以从某个节点到达树的一部分,被视为树本身,在红黑树中,假定叶子为空或null。

将一个节点插入到红黑树中,首先,按二叉查找树的操作方式将节点插入,然后,为节点着色标为红色,最后,根据红黑树的特点和规则,通过旋转操作重新着色来修正树,使之满足一棵红黑树的要求。

先看一个红黑树的动态演示程序

红黑树是一种自平衡搜索树(BST-Binary Search Tree)

树在动态环境中保持平衡 - 从而保证搜索时间 O(logn) 。任何树都可以重新平衡 - 但成本相当高 - 更重要的是它可以在O(logn) 时间内重新平衡。

由于,红黑树也是二叉搜索树,所以,必须满足以下约束:

即每个节点包含大于或等于,其左子树中所有节点的值,并且小于或等于,其右子树中的所有节点。这使得快速搜索树,以获取指定值成为可能。

红黑树最初的结构,是由鲁道夫·拜耳于1972年发明的,他称其为“对称二叉树”,但在1978年由里奥·j·古巴斯(Leo J. Guibas)和罗伯特·塞奇维克(Robert Sedgewick)在一篇论文中给了它了现在的名字。

红黑树很复杂,但在最坏情况下运行时间也很好,并且,在实践中很有效:红黑树可以在O(log n)时间内完成搜索、插入和删除,其中n是树中的元素数量。

红黑树通过左旋和右旋保持平衡

无论是左旋还是右旋,被旋转的树,在旋转前是二叉查找树,并且,旋转之后仍然是一颗二叉查找树。对一个节点进行左旋,表示将当前节点的右孩子,变成当前节点的父亲节点,此节点就变成了一个左节点。左旋中的“左”,表示被旋转的节点将变成一个左节点。

对于右旋,表示将左孩子设为当前节点的父亲节点,此节点就变成了一个右节点,右旋中的“右”,表示被旋转的节点,将变成一个右节点。

红黑树删除需要多长时间?

查找要删除的节点,以及找到最左侧的后代,与树的高度成正比,因此它是O(log n)。交换和删除是O(1)。每个单独的修复(旋转等)是 O(1)。

在最坏的情况下,双黑可能会传递到根。由于每次旋转需要恒定的时间,因此,将与树的高度成比例,为O(log n),最坏情况下的删除成本是O(log n)。

红黑树java实现示例代码