Data Structure 06 - Self-balancing Binary Search Tree
# 前置知识
在阅读本文档前,请确保你已经掌握二叉树的基础知识,详见 Data Structure 知识板块中的 05 - Binary Search Tree 文档。
# 基本概念
我们知道,二叉查找树的平均性能非常好,但是它非常容易发生退化,例如,只要我们有序地插入若干个元素,就会得到一条链,那么插入、删除和查找的时间复杂度都会退化到 。考虑到有序插入是一件很常见的事情,这样的结果并不能满足我们的要求。平衡树的产生就是为了解决这一问题。
平衡树 (self-balancing binary search tree, or height-balanced binary search tree) 是一种追加了特殊限制的二叉查找树,在执行插入和删除操作时,在维持查找树性质的同时自动对树的结构进行调整,以保证树的高度在 的数量级。
我们知道,因为二叉查找树的各类操作的时间复杂度均与高度有关,所以高度显然越小越好。而一棵有 个节点的二叉查找树的最小高度为 ,此时近似于完全二叉树,节点分布非常密集。
不过,平衡树并不会保证树的高度为 ,因为要想做到这个地步所需的时间开销实在太大,并无高效的方法能做到这一点。通常各种平衡树只是通过一些调整操作使树的高度为 的常数倍数,并不能保证高度最小,但这也足够了。
和堆类似,平衡树只是一种思想,其具体实现方式有很多种。有些实现方式会保证每次插入和删除操作的时间复杂度均为 ,而另一些实现方式则是保证一系列插入和删除操作的均摊时间复杂度为 ,须知这是不一样的。
常见的平衡树有AVL树、伸展树、树堆、B树、红黑树等。其中AVL树是最先被发明的平衡树,也常有人把平衡树等同于AVL树,这是不对的,AVL树只是这些平衡树中的一种而已。伸展树和树堆在算法竞赛中较为常用,B树更常用于工程代码中(也广泛应用于文件存储系统以及数据库系统中),红黑树则是C++中一些STL容器的底层实现(并且红黑树以极其复杂难写而出名)。
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01