红黑树就是满足以下特性的二叉树

  1. 所有节点只有红色和黑色
  2. 红色节点的孩子都是黑色（红色节点不能相邻）
  3. 黑色节点到任意叶子节点的简单路径上经过的黑色节点数量相同
  4. 叶子节点不存储值，而且叶子节点都是黑色的 满足这样特性的二叉树高度一定不超过2log(n+1) 下面是证明 如果把红色节点全部删掉，把下面的剩下的所有节点都连接在一起，那么新产生的树就是一颗每个节点最多有四个子节点的树，计算高度可以采用满四叉树的高度来近似计算，即log(n)，而把删除的红色节点加上就是2倍

红黑树相较于AVL，其查找效率略低一点，而插入删除效率高出AVL很多，所以当插入删除操作很多时可以使用红黑树