c++ 平衡树
发布日期:2021-06-21 02:54:50 浏览次数:5 分类:技术文章

本文共 794 字,大约阅读时间需要 2 分钟。

平衡树的性质

它其实就是一个 BST(Binary Search Tree 二叉搜索树)。

当然,不同的平衡树会有自己的特性

BST 的性质

只有一个:任意一个节点的左子树的所有节点都比它的优先级高,右子树的所有节点都比他的优先级低。

注意:一个节点也可以当成一颗子树
如下:

Why 平衡树?

看到这里你也许会想:既然平衡树就是一颗 BST ,那还要它干嘛?

看这里:

由于 BST 可能会退化成一条链,使得原本
\(O(log n)\) 的速度退化成
\(O(n)\)
于是,大佬们发明了各种各样的平衡树,避免 BST 退化成一条链

平衡树的分类

\[\text{平衡树} \left\{ \begin{array}{**lr**} \text{旋转平衡树} \left\{ \begin{array}{**lr**} \text{Splay} & \\ \text{Treap} \end{array} \right. & \\ \text{非旋平衡树} \left\{ \begin{array}{**lr**} \text{FHQ Treap} & \\ \text{替罪羊树} \end{array} \right. \end{array} \right. \]

当然这里只是最常用的

还有更多的平衡树等待着你去学习、发明

平衡树的效率

操作 时间复杂度
插入元素 \(O(log n)\)
弹出元素 \(O(log n)\)
查询排名 \(O(log n)\)
查询第 K 大 \(O(log n)\)
查询前驱 \(O(log n)\)
查询后继 \(O(log n)\)

当然这些是基础功能,还有更多的以后会学到

平衡树的解析

FHQ Treap

这是一个最适合新手学习的

包含区间反转、可持久化

Splay

这个也是必须要掌握的

包含区间反转、 LCT



The End

转载地址:https://blog.csdn.net/KonjakuLAF/article/details/115714568 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:c++ 线段树
下一篇:c++ 树状数组

发表评论

最新留言

不错!
[***.144.177.141]2024年03月24日 00时46分35秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章