红黑树

什么是“平衡二叉查找树”?

二叉树中任意一个节点的左右子树的高度相差不能大于1。
平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。

如何定义一颗“红黑树”？

• 根节点是黑色的；
• 每个叶子节点都是黑色的空节点（NIL）,也就是说 叶子节点不存储数据；
• 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；

• 每个节点，从该节点到达可达叶子节点的所有路径，都包含相同数目的黑色节点；

  
  红黑树

问题引出：为什么工程中都喜欢用红黑树，而不是其他平衡二叉查找树呢？

AVL树（平衡查找二叉树）是一种高度平衡的二叉树，所以查询的效率非常高，但是，有利有弊，AVL树为维持这种高度的平衡，就要付出更多的代价。每次插入、删除都要做调整，就比较复杂、耗时。
而红黑树只是做到了近似平衡，并不是严格的平衡，所以在维护平衡的成本上，要比AVL树要低。红黑树的插入、删除、查找各种操作性能都比较稳定,其时间复杂度都为O（logn）。符合工业级工程的要求。