【数据结构】红黑树——自平衡二叉搜索树

发布时间：2020-12-15 06:34:05 所属栏目：安全来源：网络整理

导读：树的旋转树的旋转是一种特殊操作，保持中序遍历结果不变的情况下，改变树的结构。上图中a所示二叉搜索树经过左旋变换为b所示的树。（右旋操作是左旋的逆变换）函数定义将非空二叉树记为三元组 T = ( T l , k , T r ) ，则： r o t a t e L ( T ) = { (

树的旋转

树的旋转是一种特殊操作，保持中序遍历结果不变的情况下，改变树的结构。

上图中a所示二叉搜索树经过左旋变换为b所示的树。（右旋操作是左旋的逆变换）

函数定义
将非空二叉树记为三元组 $T=(T_l,k,T_r)$ ，则：

r o t a t e L (T) = {((a, X, b), Y, c) T : T = (a, x, (b, Y, c)) : 其 他

$rotateL(T)= begin{cases} ((a,X,b),Y,c)&:T=(a,x,(b,c)) T&:其他 end{cases}$

r o t a t e R (T) = {(a, X, (b, Y, c) T : T = ((a, X, b), Y, c) : 其 他

$rotateR(T)= begin{cases} (a,c)&:T=((a,c) T&:其他 end{cases}$

红黑树的定义

需要在二叉搜索树上增加一个额外的颜色信息，树中的节点可以涂成红色或黑色。
如果一棵二叉搜索树满足下面的全部5条性质，则成为红黑树：

任一节点要么是红色，要么是黑色；
根节点为黑色
所有的叶子结点（NIL节点）为黑色
如果一个节点为红色，则它的两个子节点都是黑色；
对任一节点，从它出发到所有叶子结点的路径上包含相同数量的黑色节点。

关键特性：从根结点出发到达叶子节点的所有路径中，最长路径不会超过最短路径的两倍。

数据组织

红黑树的节点：

function Node(data,color,left,right) {
    this.data = data;
    this.color = color;
    this.left = left;
    this.right = right;
    this.show = show;
}
function show() {
    return this.data;
}

插入

1、插入操作会改变树的结构，因此二叉搜索树可能变得不平衡。因此，为了保持红黑树的特质，需要在插入操作后进行变换来修复平衡问题。
2、当插入一个key时，可以把新节点一律染成红色。只要它不是根节点，除了第4条，所有红黑树性质都可以满足，唯一的问题是可能引入两个相邻的红色节点。
3、共有4种情况会违反红黑树的第4条性质，它们都带有两个相邻的红色节点。但是，它们可以被修复为一个统一形式，如下图：

注意：这一变换会把红色向上“移动一层”。如果进行自底向上的递归修复，最后一步会把根节点染成红色。根据第2条性质，因此要把根节点再染回黑色。

算法函数描述
把节点的颜色记为C，它有两个值，黑色B和红色R。这一棵非空的红黑树可以表达为一个四元组 $T=(C,T_l,T_r)$ 。

b a l a n c e (T) = {(R, (B, A, x, B), y, (B, C, z, D)) T : m a t c h (T) : 其 他

$balance(T)= begin{cases} (R,(B,A,B),y,C,z,D))&:match(T) T&:其他 end{cases}$
函数

match(T) $match(T)$ 用以判断树是否符合上图中4中需要修复的情况。定义如下：

m a t c h (T) : T = ? ? ? ? ? ? ? ? ? (B, (R, (R, A, x, B), y, C), z, D) \lor (B, (R, A, x, (R, B, y, Z)), z, D) \lor (B, A . x, (R, B, y, (R, C, z, D))) \lor (B, A, x, (R, (R, B, y, C), z, D))

$match(T): T=begin{cases} (B,(R,C),D) lor (B,B,Z)),A.x,D))) lor (B,D)) end{cases}$
定义好

balance(T) $balance(T)$ 后，就可以修改二叉搜索树的插入函数，使其支持红黑树：

i n s e s r t (T, k) = m a k e B l a c k (i n s (T, k))

$insesrt(T,k)=makeBlack(ins(T,k))$
其中

ins(T,k) $ins(T,k)$ 函数定义如下：

i n s (T, k) = ? ? ? (R, ?, k, ?) b a l a n c e ((i n s (T l, k), k', T r)) b a l a n c e ((T l, k', i n s (T r, k))) : T = ? : k < k' : k < k'

$ins(T,k)= begin{cases} (R,phi,phi)&:T=phi balance((ins(T_l,k),k',T_r))&:k<k' balance((T_l,ins(T_r,k)))&:k<k' end{cases}$
如果待插入的树为空，则创建一个新的红色节点，节点的key就是待插入的k；
否则，记树的左右分支和key分别为

Tl,Tr和k′ $T_l,T_r和k'$ ，比较

k $k$ 和

k′ $k'$ 的大小，递归地将它插入子分支中，然后再用balance函数恢复平衡。
最后，使用

makeBlack(T) $makeBlack(T)$ 函数把根节点染成黑色：

m a k e B l a c k (T) = (B, T l, k, T r)

$makeBlack(T)=(B,T_r)$

算法复杂度：这一插入算法的复杂度为 $O(lgn)$ 。

删除

删除操作在删除一个黑色的节点时才会引发问题，因为这样会破坏红黑树的第 5 条性质，使得某一路径上的黑色节点数目少于其他的路径。
解决方案： 引入“双重黑色”的概念来恢复第 5 条性质。即节点被删除了，我们把它的黑色保存在它的父节点中。如果父节点是红色的，我们将其变为黑色；如果父节点已经是黑色的，它就会变成一个“双重黑色”的节点。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!