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