红黑树解决了什么问题

by Worktile 项目协作工具

红黑树解决了的问题有以下2个：1.自平衡BST(self-balancing BST) 库函数问题；2.实现 Linux 操作系统的 CPU 调度。红黑树（Red Black Tree）是一颗自平衡（self-balancing）的二叉排序树（BST）。

什么是红黑树？

红黑树（Red Black Tree）是一颗自平衡（self-balancing）的二叉排序树（BST），树上的每一个结点都遵循下面的规则（特别提醒，这里的自平衡和平衡二叉树AVL的高度平衡有别）：

  1. 每一个结点都有一个颜色，要么为红色，要么为黑色；
  2. 树的根结点为黑色；
  3. 树中不存在两个相邻的红色结点（即红色结点的父结点和孩子结点均不能是红色）；
  4. 从任意一个结点（包括根结点）到其任何后代 NULL 结点（默认是黑色的）的每条路径都具有相同数量的黑色结点。

为什么要有红黑树？

大多数二叉排序树BST的操作（查找、最大值、最小值、插入、删除等等）都是O(h)的时间复杂度，h 为树的高度。但是对于斜树而言（BST极端情况下出现），BST的这些操作的时间复杂度将达到 ​O(n)。为了保证BST的所有操作的时间复杂度的上限为O(logn)，就要想办法把一颗BST树的高度一直维持在logn，而红黑树就做到了这一点，红黑树的高度始终都维持在log(n)，n 为树中的顶点数目。