数据结构--红黑树

概念

前面对树已经有了一个认识，现在看下红黑树的定义。 开始之前提几个问题：

1. 什么是红黑树
2. 有什么用
3. 怎么实现
4. 优缺点

什么是红黑树

红黑树: 又叫二叉平衡树 红黑树又红又黑，真正的意义是什么？为什么要红一下黑一下？

会左旋 和 右旋，不会出现单边增长太多，会平衡。

红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。 它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的：它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

有什么用

为了实现快速定位而设计的算法。

几乎所有基于二叉树的算法，都是基于二分法进行查找的，只要数据100%是按照一定顺序排列的，那么就可以被二分法查找。

假疫有10亿数据只需要不到30次比较就能查找到目标。

二叉查找树这一数据结构并不难，而红黑树之所以难是难在它是自平衡的二叉查找树，在进行插入和删除等可能会破坏树的平衡的操作时，需要重新自处理达到平衡状态。

红黑树特点：

1. 节点要么红、要么黑
2. 根节点是黑色
3. 叶节点null，都是黑色
4. 每个红色节点包含的子节点，一定为黑色
5. 任意一结点到每个叶子结点的路径都包含数量相同的黑子结点。