二叉排序树

非空二叉排序树具有如下特点：

• 二叉排序树中，如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；
• 二叉排序树中，如果其根结点有右子树，那么右子树上所有结点的值都大小根结点的值；
• 二叉排序树的左右子树也要求都是二叉排序树；

如果我们想要查找一个数字11，过程是怎么样的呢？

image.png

按照二叉树排序的特点进行数据的插入，可能会产生以下这种情况：

image.png

一颗二叉查找树的优势完全丧失了

红黑树

为了解决二叉排序树多次插入新节点导致的不平衡问题，诞生了红黑树。

红黑树（ Red black tree）是一种自平衡二叉査找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。红黑树和AVL树类似，都是在进行插λ和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的：它可以在O（logn）时间内做查找，插入和删除，这里的n是树中元素的数目。

image.png

红黑树（RBT）的定义：它或者是一颗空树，或者是具有一下性质的二叉查找树：

• 节点非红即黑。
• 根节点是黑色。
• 所有NULL结点称为叶子节点，且认为颜色为黑。
• 所有红节点的子节点都为黑色。
• 从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点。

所有性质1~5合起来约束了该树的平衡性能--即该树上的最长路径不可能会大于2倍最短路径。
因为，最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。

当在对红黑树进行插入和删除等操作时，对树做了修改，可能会违背红黑树的性质。为了保持红黑树的性质，可以通过对树进行旋转，即修改树中某些结点的颜色及指针结构，以保持它特有的性质。
有两种旋转方式：左旋和右旋，如下图:

image.png

恢复红黑属性需要少量的颜色变更并且在删除节点不超过三次树旋转，插入不超过两次树旋转

注：红黑树的时间复杂度为: O(lgn)
一棵含有n个节点的红黑树的高度至多为2log(n+1).

应用场景：

1. java8 hashmap中链表转红黑树。

• 优势：时间复杂度从O(n)-->O(logn) ，且自旋开销较其他树较低（不用整体平衡）。

2. epoll在内核中的实现，用红黑树管理事件块（文件描述符,epoll，binder，事件）。
   优势：

• 因为内核态需要维护一个长久存放fd的数据结构，而fd变动十分频繁，且需要支持快速查询，且所以红黑树很适合。
• 红黑树可以判断是否是重复的fd

3、Java的TreeMap实现

• 相对与hashMap优势，内部key保持有序，且支持自定义排序比较器。
  适用场景，对数据需要排序统计

4、linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块

• CFS 背后的主要想法是维护为任务提供处理器时间方面的平衡（公平性）。这意味着应给进程分配相当数量的处理器

时间复杂度

image.png image.png

原文链接：https://blog.csdn.net/ThinPikachu/article/details/113865133