我尝试在这里画一棵红黑树

发表于 | 更新于 | 阅读次数：

但是进度有点慢，我应该打住了，先写一点别的。现在应该可以很快画出来了。

红黑树的性质

  1. 节点有颜色，红色或者是黑色
  2. 根节点是黑的，虽然这个性质用处不是很大，不影响大部分的分析
  3. 为了方便，节点有指向父节点的指针（除了左右子节点的指针之外）
  4. 红色节点的子节点都是黑色的
  5. 根节点到所有叶子节点的路径上黑色节点的数量都是相同的

我们根据上面的性质可以发现，红黑树可以保持一个比较平衡，但又不是完全平衡的状态。

根据性质5和性质4，我们可以发现红黑树最不平衡的状态也就是某些节点的实际深度是另一些的两倍。

而红黑树保持这样相对平衡的状态就可以使得我们可以像其他的平衡的二叉树一样在$O(\log{N})$的时间内完成查找。

实际上红黑树在插入和删除节点的时候消耗的时间也是$O(\log{N})$，这是红黑树的一个非常好的性质。

如果我们需要一个查找、插入、删除节点都很快的数据结构，我们可以选择它。

一些基本的操作

在我们的插入删除的过程中为了保持平衡，我们需要提取一些保持平衡过程中常用的步骤。除了找节点的各个亲戚之外就是树的旋转操作。

那么下面就是常见的操作和简短的代码，代码可能是错的但是不应该影阅响读。

找爸爸

1
2
3
function parent(node) {
    return node.parent;
}

找爷爷

1
2
3
4
5
6
7
function grandParent(node) {
    const parent = parent(node);
    if(parent) {
        return parent(parent);
    }
    return null;
}

找叔叔

1
2
3
4
5
6
7
8
9
10
function uncle(node) {
    const grandParent = grandParent(node);
    if(grandParent) {
        if(grandParent.left === parent(node)) {
            return grandParent.right;
        }
        return grandParent.left;
    }
    return null;
}

找兄弟

1
2
3
4
5
6
7
8
9
10
11
function sibling(node) {
    const parent = parent(node);
    if(parent) {
        if(parent.left == node) {
            return parent.right;
        }else {
            return parent.left;
        }
    }
    return null;
}

左旋

左旋操作应该说是逆时针旋转，把一个节点变成它的右子节点的左子节点，并且继承了右子节点的左子节点为自己的新的右子节点，同时还送出了自己的父亲。具体操作如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function rotateLeft(node) {
    const newNode = node.right;
    const pNode = parent(node);
    if(newNode) {
        node.right = newNode.left;
        node.right.parent = node;
        newNode.left = node;
        node.parent = newNode;
        if(pNode) {
            if(pNode.left === node) {
                pNode.left = newNode;
            }else {
                pNode.right = newNode;
            }
            newNode.parent = pNode;
        }else {
            newNode.parent = null;
        }
    }   
}

右旋

右旋操作，我也更喜欢说是顺时针旋转，如果树是从上往下的话。和左旋相反，是一个节点的左儿子变成自己的父亲的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function rotateRight(node) {
    const newNode = node.left;
    const pNode = node.parent;
    if(newNode) {
        node.left = newNode.right;
        node.left.parent = node;
        newNode.right = node;
        node.parent = newNode;
        if(pNode) {
            if(pNode.left === node) {
                pNode.left = newNode;
            }else {
                pNode.right = newNode;
            }
            newNode.parent = pNode;
        }else {
            newNode.parent = null;
        }
    }
}