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

问题

红黑树是一种自平衡的二叉查找树,它可以在O(logn)时间内执行查找、插入和删除。在c++ STL,linux内核中都有使用。

红黑树本身是有序的,现在问题是对于指定的元素,如何能快速查到它在整个元素集的排名,或者根据排名快速查询对应的元素?

思路

排名分顺序和逆序,这里只讨论顺序的情况。顺序的话排名就是求比当前元素小的元素的个数,根据红黑树的性质,左子树的节点都比根节点小,右子树的节点都比根节点大,求排名就等价于求节点左子树元素的个数。

根据树的递归性质,我们只需要在每个节点增加一个字段count用来统计当前节点子树的个数,同时在红黑树做插入、删除操作的时候更新count字段,就能在O(logn)的时间内查询到该元素的排名。

实现

红黑树节点增加count字段,count[x]表示x节点子节点元素的个数,包括它的左子树,它的右子树和它自己本身。

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

红黑树旋转的时候,保证count满足我们的定义就可以。

左旋

左旋后:

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

插入和删除的时候对于count的修改比较简单,只修改节点所有祖先节点的count,插入的时候,我们先按照红黑树的规则插入到指定位置,然后对该节点的所有祖先节点的count都增加1,然后再做平衡调整,删除的时候类似。

根据排名查询元素

跟红黑树普通的查询类似,只不过用来比较的域换成了count,这里分为三种情况:

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]

查询排名

红黑树普通查询,O(logn)可以查询到指定元素的排名

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]

总结

插入、删除、查找算法都是在原红黑树的基础上进行简单修改,时间复杂度均为O(logn)。

红黑树增加count扩展后,增加的count操作主要在红黑树的旋转,每次红黑树平衡最多3次旋转,所以对红黑树的性能影响很小,可以用来实现游戏中常见的排行榜功能。但是当元素集合的总量达到一定规模比如千万级,可能会有性能问题,主要消耗在红黑树key的字符串比较上。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏五分钟学算法

每天一算:Binary Tree Preorder Traversal

下面这种写法使用了一个辅助结点p,这种写法其实可以看作是一个模版,对应的还有中序和后序的模版写法,形式很统一,方便于记忆。后续更新的中序和后序文章中都会补充该写...

632
来自专栏Java开发者杂谈

堆排序与快速排序

前言   前面差不多学习了插入排序、选择排序、冒泡排序、归并排序。这些排序除了归并排序在时间上消耗为:θ(nlgn)外,其余排序时间消耗都为:θ(n2).  接...

35311
来自专栏腾讯数据库技术

如何利用红黑树实现排名?

1563
来自专栏趣学算法

数据结构 第12讲 二叉树的层次遍历

二叉树的遍历一般有先序遍历、中序遍历和后序遍历,这三种遍历比较简单。今天我们讲二叉树的另一种遍历方式,层次遍历。即按照层次进行遍历。如图1所示:

723
来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题26复杂链表的复制

本题详细解析均在代码注释中: /** * 题目:请复制一个复杂链表。每个结点除了有一个next指针指向下一个结点外,还有一个sibling指向链表中的任意一个...

2594
来自专栏彭湖湾的编程世界

【算法】二叉查找树(BST)实现字典API

参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结...

3429
来自专栏决胜机器学习

PHP数据结构(十三) ——动态查找表(二叉排序树)

PHP数据结构(十三) ——动态查找表(二叉排序树) (原创内容,转载请注明来源,谢谢) 一、概念 1、动态查找表特点 当对动态查找表进行查...

45110
来自专栏数据结构与算法

二叉树的遍历

解决二叉树的很多问题的方案都是基于对二叉树的遍历。遍历二叉树的前序,中序,后序三大方法算是计算机科班学生必写代码了。其递归遍历是人人都能信手拈来,可是在手生时写...

3344
来自专栏小二的折腾日记

牛客网-剑指offer-2

二叉树是觉得很烦的东西了,比链表复杂很多,看着头都有点疼啊,但是没办法,生活就是这样,只有把不会的会了才会进步,怕的变得不怕才能越来越厉害。 常规的理解一下:二...

1452
来自专栏前端儿

重建二叉树

题目很简单,给你一棵二叉树的后序和中序序列,求出它的前序序列(So easy!)。

1071

扫码关注云+社区