前言

二叉搜索树存在一个bug:极端情况下会退化成一个链表（如：（13,15,11,9,7,5,2），动画演示地址：https://visualgo.net/en/bst）
image.png
这个时候数据的查找时间复杂度为O(N)，并没有提高查找效率，所以需要一些手段防止其退化成链表，于是出现了平衡二叉搜索树，主要有两种：AVL和红黑树

AVL

称为平衡二叉搜索树，是一种特殊的二叉搜索树，其具有以下特性：

  • 树中所有节点的左右子树高度差的绝对值不超过1
  • 所有节点的左右子树仍然是平衡二叉树

image.png

红黑树

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

演示地址：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
下载.png

性质

  • 每个结点非红即黑；
  • 根节点是黑的；
  • 每个叶节点（叶节点即树尾端NULL指针或NULL结点）都是黑的；
  • 如果一个结点是红色的，则它的子节点必须是黑色的；
  • 对于任何结点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑结点

时间复杂度

O(logn)

AVL和红黑树区别

AVL树是高度平衡的，频繁的插入和删除，会引起频繁的rebalance，导致效率下降；红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。所以在实际的应用场景中，大多使用红黑树