一、红黑树概念

红黑树是一棵二叉搜索树，它在每个节点上增加了一个存储位用来表示节点颜色(红色或者黑色)，红黑树通过约束颜色，可以保证最长路径不超过最短路径的两倍，因而近似平衡，而且在实际应用中发现红黑树性能确实比 AVL树性能高

红黑树具有以下性质：

• 每个节点不是红色就是黑色的
• 根节点和所有外部节点都是黑色的
• 根节点到所有外部节点的简单路径上，没有两个连续的红色节点
• 任一节点到其所有后代外部节点的简单路径上，黑色节点的数量都相同

引申问题

为什么满足上面的颜色约束性质，红黑树就能保证最长路径不超过最短路径的两倍？
答：最短路径在极端情况下一定是全黑的，假设其数量是 x，而最长路径的黑色节点数量也是 x，并且极端情况下，掺杂的红色节点数量是 x - 1，所以最长路径肯定不超过最短路径的两倍

二、红黑树操作

查找 + 插入 + 删除