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

树的旋转

树的旋转是一种特殊操作,保持中序遍历结果不变的情况下,改变树的结构。
树的左旋
上图中a所示二叉搜索树经过左旋变换为b所示的树。(右旋操作是左旋的逆变换)

函数定义
将非空二叉树记为三元组 T=(Tl,k,Tr) ,则:

rotateL(T)={((a,X,b),Y,c)T:T=(a,x,(b,Y,c)):

rotateR(T)={(a,X,(b,Y,c)T:T=((a,X,b),Y,c):

红黑树的定义

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

  1. 任一节点要么是红色,要么是黑色;
  2. 根节点为黑色
  3. 所有的叶子结点(NIL节点)为黑色
  4. 如果一个节点为红色,则它的两个子节点都是黑色;
  5. 对任一节点,从它出发到所有叶子结点的路径上包含相同数量的黑色节点。

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

数据组织

红黑树的节点:

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,Tl,k,Tr)

balance(T)={(R,(B,A,x,B),y,(B,C,z,D))T:match(T):

函数 match(T) 用以判断树是否符合上图中4中需要修复的情况。定义如下:
match(T):T=(B,(R,(R,A,x,B),y,C),z,D)(B,(R,A,x,(R,B,y,Z)),z,D)(B,A.x,(R,B,y,(R,C,z,D)))(B,A,x,(R,(R,B,y,C),z,D))

定义好 balance(T) 后,就可以修改二叉搜索树的插入函数,使其支持红黑树:
insesrt(T,k)=makeBlack(ins(T,k))

其中 ins(T,k) 函数定义如下:
ins(T,k)=(R,ϕ,k,ϕ)balance((ins(Tl,k),k,Tr))balance((Tl,k,ins(Tr,k))):T=ϕ:k<k:k<k

如果待插入的树为空,则创建一个新的红色节点,节点的key就是待插入的k;
否则,记树的左右分支和key分别为 Tl,Trk ,比较 k k 的大小,递归地将它插入子分支中,然后再用balance函数恢复平衡。
最后,使用 makeBlack(T) 函数把根节点染成黑色:
makeBlack(T)=(B,Tl,k,Tr)

算法复杂度:这一插入算法的复杂度为 O(lgn)

删除

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

相关文章
相关标签/搜索