红黑树和 AVL 树（平衡二叉树）区别

date

May 28, 2021

Last edited time

Mar 27, 2023 09:02 AM

status

Published

slug

difference_between_AVL_and_RedBlack_tree

一，AVL 树（平衡二叉树）

（1）简介

AVL 树是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，左右子树树高不超过 1，和红黑树相比，AVL 树是严格的平衡二叉树，平衡条件必须满足（所有节点的左右子树高度差的绝对值不超过 1）。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是非常耗时的，由此我们可以知道 AVL 树适合用于插入与删除次数比较少，但查找多的情况

（2）局限性 由于维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然，如果应用场景中对插入删除不频繁，只是对查找要求较高，那么 AVL 还是较优于红黑树。（3）应用

1，Windows NT 内核中广泛存在;

二、红黑树

（1）简介 一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树（由于是弱平衡，可以看到，在相同的节点情况下，AVL 树的高度低于红黑树），相对于要求严格的 AVL 树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，我们就用红黑树。

（2）性质

如图 1 所示，每个节点非红即黑;

每个节点非红即黑

根节点是黑的;

每个叶节点（叶节点即树尾端 NULL 指针或 NULL 节点）都是黑的;

如图所示，如果一个节点是红的，那么它的两儿子都是黑的;

对于任意节点而言，其到叶子点树 NULL 指针的每条路径都包含相同数目的黑节点;

每条路径都包含相同的黑节点;

（3）应用 1，广泛用于 C ++ 的 STL 中，地图和集都是用红黑树实现的; 2，着名的 Linux 的的进程调度完全公平调度程序，用红黑树管理进程控制块，进程的虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点，左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间; 3，IO 多路复用的 epoll 的的的实现采用红黑树组织管理的的的 sockfd，以支持快速的增删改查; 4，Nginx 的的的中用红黑树管理定时器，因为红黑树是有序的，可以很快的得到距离当前最小的定时器; 5，Java 的的的中 TreeMap 中的中的实现;