红黑树的左旋和右旋
本文章只是学习笔记
参考文章:高性能服务器开发公众号里的历史文章
为什么要旋转?
因为红黑树经过添加删除元素之后,就容易不满足红黑树的5个特性了,通过旋转可以再次满足红黑树的特性。
特性再复习一下:
1.根节点是黑色
2.叶子节点是黑色(NULL)
3.如果一个节点是红色,则它的孩子一定是黑色
4.从某个节点到叶子节点的完整路径上黑色节点的数目都是相同的。
5.每个节点的颜色要么是红色,要么是黑色
左旋:比较复杂~~~~~
简单的说就是让自己X的右孩子Y取代自己的位置,然后自己X变为Y的左孩子,然后现在自己X没有右孩子了嘛(就是右孩子Y变成了自己的父亲),
作为补偿Y原来的左孩子变成自己X的右孩子。其他父子关系不变
右旋:
类似的,自己Y进行右旋则让自己Y的左孩子X取代自己的位置,然后自己Y变成X的右孩子,现在自己Y没有左孩子了,
同样作为补偿,X的右孩子变成现在自己Y的左孩子
为了容易理解,最好画画图