【腾讯云CKV缓存】cloud key value·红黑树排名实现过程解析

实现

```count[x] = count[left[x]] + count[right[x]] + 1; // x非空
count[x] = 0; // x为空```

左旋

```count[x] = count[α] + count[β] + 1
count[y] = count[x] + count[γ] + 1```

```LEFT-ROTATE(T, x)
y = right[x]
right[x] = left[y]
p[left[y]] = x
p[y] = p[x]
count[x] = count[left[x]] + count[left[right[x]]] + 1
count[right[x]] = count[left[x]] + count[left[right[x]]] + count[right[right[x]]] + 2
if p[x] == nil
then root[T] = y
else if x == left[p[x]]
then left[p[x]] = y
else right[p[x]] = y
left[y] = x
p[x] = y
```

右旋

```count[y] = count[γ] + count[β] + 1
count[x] = count[x] + count[α] + 1```

```RIGHT-ROTATE(T, y)
x = left[y]
left[y] = right[x]
p[right[x]] = y
p[x] = p[y]
count[y] = count[right[y]] + count[right[left[y]]] + 1
count[left[y]] = count[right[y]] + count[left[left[y]]] + count[right[left[y]]] + 2
if p[y] == nil
then root[T] = x
else if y == right[p[y]]
then right[p[y]] = x
else left[p[y]] = x
right[x] = y
p[y] = x
```

根据排名查询元素

1.节点左子树个数 + 1 == rank，表示已经找到需要查询的元素

2.节点左子树个数 + 1 > rank, 表示当前节点左子树个数大于rank - 1，我们需要在左子树中递归查询

3.节点左子树个数 + 1 < rank, 表示当前节点左子树个数大于rank - 1, 我们需要在右字数中查询，注意这个时候需要修改rank值

```QUERYBYRANK(T, r)
y = root[T]
while y != nil
if count[left[y]] + 1 == r then
// find it
exit
else if count[left[y]] +1 > r then
y = left[y]
else
r = r - count[left[y]] - 1
y = right[y]
```

查询排名

```RANK(T, x)
y = root[T]
while y != nil
if key[x] == key[y] then
// find it
r = count[y]
exit
else if key[x] < key[y] then
y = left[y]
else y = right[y]
```

74 篇文章151 人订阅

0 条评论

相关文章

2489

LeetCode54. 螺旋矩阵&LeetCode59.螺旋矩阵 II&LeetCode48. 旋转图像

要是去找每次移动下标之间的关系就错了，很难找到，应该从宏观角度去看，首先打印的是最外层一圈，然后打印倒数第二层的一圈，...依次下去，所以应该这么做，找到...

782

1300

651

PAT甲级 1053 Path of Equal Weight

Given a non-empty tree with root R, and with weight Wi assigned to each tree nod...

1085

1823

1431

5504