平衡二叉查找树
这种二叉查找树就退化成了链表，由于树的深度变得多了，查找的效率也会大幅下降
所以需要对这种二叉树进行自平衡，红黑树就是一种自平衡的二叉查找树
红黑树（Red Black Tree）
除了二叉查找树(BST)的特征外，还有以下特征：
- 每个节点要么是黑色，要么是红色
- 根节点是黑色
- 每个叶子节点都是黑色的空结点（NIL结点）（为了简单期间，一般会省略该节点）
- 如果一个节点是红色的，则它的子节点必须是黑色的（父子不能同为红）
- 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点（平衡的关键）
- 新插入节点默认为红色，插入后需要校验红黑树是否符合规则，不符合则需要进行平衡
一颗典型的红黑树：
在对红黑树进行添加或者删除操作时可能会破坏这些特点，所以红黑树采取了很多方式来维护这些特
点，从而维持平衡。主要包括：左旋转、右旋转和颜色反转
左旋（RotateLeft）
逆时针旋转红黑树的两个结点，使得父结点被自己的右孩子取代，而自己成为自己的左孩子
版权声明：本文为qq_19520877原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。