平衡二叉树的左右旋以及双旋转的图文详解

高度平衡的搜索二叉树

一棵平衡树，或是空树，或是具有以下性质的二叉搜索树：左子树和右子树都是AVL树，且左右子树的高度之差的绝对值不超过1。

该二叉树，根结点的右子树高度为3，左子树高度为2。结点上方的数字为平衡因子，因为右子树高度比左子树高度大1，所以根结点的平衡因子为1。

一颗平衡二叉树，如果有n个结点，其高度可保持O(log2^n),平均搜索长度也可以保持在O(log2^n)

平衡化旋转

AVL树相较于普通的二叉搜索树，自主要的就是做了平衡化处理，使得二叉树变的平衡，高度降低。

在插入一个结点后应该沿搜索路径将路径上的结点平衡因子进行修改，当平衡因子大于1时，就需要进行平衡化处理。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点，如果这三个结点在一条直线上，则采用单旋转进行平衡化，如果这三个结点位于一条折线上，则采用双旋转进行平衡化。

单旋转

左单旋

动图演示，图片内容可以无视，看懂操作进行了

将右子树的左子树链接到父亲节点的右孩子结点，父亲节点作为ptr结点的左孩子结点便完成了旋转

右单旋

右单旋是左单旋的镜像旋转.

当前节点ptr，与父亲节点和当前节点的左孩子结点位于一条直线上时，使用右单旋进行平衡。

双旋转

先左后右双旋转

当在ptr的左子树的右子树中插入一个结点后，造成了ptr平衡因子为-2的不平衡，将ptr向下找到当前结点的左孩子的右孩子，先进行左单旋ptr->left = subL，然后将ptr的右子树断开指向subR，此时便完成了旋转，最后将平衡因子进行更新。

先右后左双旋转

先右单旋再左单旋，是先左后右的镜像旋转，这里就不做赘述了。

总结