二叉排序树的弊端
比如给数列{1,2,3,4,5,6}，创建一颗二叉排序树，会出现如下情况：
1、 左子树为空，像一个单链表；
2、 插入速度没有影响，但是查询速度会降低，因为每次都需要比较左子树，比单链表的情况还慢；
这时候就需要平衡二叉树
平衡二叉树特点
1、 平衡二叉树可以是一颗空树；
2、 左右子树的高度差不超过1，且左右两个子树都是平衡二叉树；
左旋
如果二叉树右节点过长的话需要左旋
步骤如下：
1、 创建一个新节点NewNode，值等于当前根节点的值；
2、 新节点的左子树设置当前节点的左子树：newNode.left=left；
3、 新节点的右子树，设置为当前节点的右子树的左子树：newNode.right=right.left；
4、 把当前节点的值置换为右子节点的值：value=right.value；
5、 把当前节点的右子树设置成右子树的右子树：right=right.right；
6、 把当前节点的左子树设置为新节点；
转换示例图：
右旋
如果二叉树左子结点过长的话需要右旋
步骤如下：
1、 创建一个新的节点，值等于当前根节点的值；
2、 把新节点的右子树设置为当前节点的右子树；
3、 把新节点的左子树设置为当前节点的左子树的右子树；
4、 把当前节点的值换为左子结点的值；
5、 把当前节点的左子树设置为左子树的左子树；
6、 把当前节点的右子树设置为新的节点；
转换示例图：
双旋
问题分析：
1、 当符合有旋转条件时；
2、 如果它的左子树的高度大于右子树的高度；
3、 先对当前节点的左节点进行左旋转；
4、 再对当前节点进行右旋转即可；
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: