8.3 红黑树原理与性能特性



1.树



解析：1.父节点可以查找子节点；2.子节点可以找到父节点。



2.二叉排序树

左子树上所有结点的值均小于等于它的根节点的值。

右子树上所有结点的值均大于等于它的根节点的值。

左右子树也分别为二叉排序树。

时间复杂度O(logn).

3.不平衡的二叉排序树

        解析：有序添加元素。蜕化成链表。

4.平衡二叉(排序)树

解析：从任何一节点触发，左右子树深度之差的绝对值不超过1.

          左右子树仍然为平衡二叉树。

时间复杂度：O(N)

5.旋转二叉树恢复平衡

#########################################################################

解析：插入时，最多需要两次旋转就会重新恢复平衡。

          删除时，需要维护从被删节点到根节点这条路径上所有节点的平衡性，时间复杂度O(logN).

6.红黑（排序）树

解析：1.每个节点只有两种颜色。

          2.根节点是黑色。（根黑）

          3.每个叶子结点（null）都是黑色的空节点。(叶黑)

          4.从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。（相同黑色数）

          5.从根节点到叶子节点，不会出现两个连续的红色节点。（红色不连续）

增删节点的时候，红黑树通过染色和旋转，保持红黑树保持定义。

6.红黑树 VS 平衡二叉树

      红黑树最多只需3次旋转就会重新达到红黑平衡，时间复杂度O(1).

      在大量增删的情况下，红黑树的效率更高。

      红黑树的平衡性不如平衡二叉树，查找效率要差一些。

      红黑树：增删效率高。

      平衡二叉树：查询效率高。（深度差不超过1）

7.跳表

       跳表代替红黑树，提升查询效率。

 ########################################################################

########################################################################

解析：复杂度2*O（logn）。

          优点：查询效率高，算法简单。

          缺点：空间复杂度比较高。