PS：本文为转载文章，原文可读性会更好，文末有原文链接1.可能出现的问题withbinarysortingtrees2.balancedbinarytree2.1balancedbinarytree的基本介绍2.2二叉树的左旋转1.二叉排序树可能存在的问题在二叉排序树（Java实现）一文中，我们了解了二叉排序树，但是它可能会存在一些问题，假设我们得到一个序列数组={3,4,5,6,7,8,9}，从小到大排序，那么构建的二叉排序树如图1所示；图片来自图11可以看出构造的二叉排序树存在以下问题：左子树全为空，像单向链表；插入速度不受影响；查询速度会降低，无法充分发挥二叉排序树的优势。还需要比较左子树，其查询速度比单链表慢；这时，如果要解决图1的问题，就必须引入平衡二叉树。2.平衡二叉树2.1平衡二叉树基本介绍平衡二叉树也称为平衡二叉搜索树或AVL树，可以保证查询效率；为空树或其左右子树的高度差绝对值不超过1，左右子树均为平衡二叉树。好吧，为了方便平衡二叉树的理解，我这里列举两种情况；案例1：看图2中的二叉树，根节点的左子节点2（取2个节点作为“根节点”，此时红框内树中的3个节点也可以看做是一棵小二叉树），其高度为2，根节点的右分段为5（5个节点视为“根节点”，红框内的1节点也可以视为一棵小二叉树）的高度为1，此时根节点的左右子树高度差的绝对值为1，不超过1，所以图2中的二叉树是平衡二叉树树。图片案例2：看图3的二叉树，根节点的左子节点8的高度（8个节点视为“根节点”，红框内的4个节点也可以视为asmallbinarytree)is3,theheightoftherightsubsection11oftherootnode(11节点被视为“根节点”，红框中的1节点也可以被视为一棵小二叉树)高度为1，此时根节点的左右子树高度差的绝对值为2，超过1，所以图3中的二叉树不是平衡二叉树。图2、2二叉树的左旋我们对一棵二叉树进行左旋，目的无非是让这棵二叉树成为一颗平衡二叉树；那么左旋转无非就是这个二叉树不是平衡二叉树，它的左子树的高度比右子树的高小，这个值至少要为2。好吧，假设我们得到一个序列数组={2,1,4,3,5,6}，根据本文学习到的二叉排序树知识（Java实现），我们构建的二叉排序树如图4;图片见图4，左子树的高度为1，右子树的高度为3，显然不是平衡二叉树，左子树的高度小于右子树的高度,而这个值为2，所以如果我们要将图4中的二叉树变成平衡二叉树，就需要将图4中的二叉树向左旋转。如何进行左旋？我们来分析一下。(1)新建一个节点，其值等于根节点的值，如图5所示；图（2）我们以根节点为当前节点，将新节点的左子树指向当前节点树的左子树，将新节点的右子树指向右子树的左子树当前节点，则得到如图6所示的结构图；图（3）将当前节点的值更改为当前节点右子树的Value，此时得到图7所示的结构图；图（4）将当前节点的右子树指向右子树的右子树（即红色数字4的右子树指向节点5），并设置当前节点的左子树指向新节点（即红色数字4的左子树指向红色数字2），则得到图8所示的结构图；图（5）此时红色数字4的节点作为新的根节点，而白色数字4的节点没有节点指向它，我们省略它，我们将图8的结构图简化得到图9所示的二叉树；图（6）第一次左旋完成后，判断二叉树是否为平衡二叉树，如果不是，则进行下一轮左旋；显然，图9中二叉树的左子树和右子树的高度都为2，因此是一棵平衡二叉树。对比图4和图9，我们发现经过一轮左旋后，旧根节点的右子树变成了新根节点，新根节点的左子树变成了旧根节点。新根节点的根节点，新根节点的左子树成为旧根节点的右子树；这里左旋的规则无非就是把旧的右孩子节点作为新的根节点，旧的根节点新根节点的左孩子用旧根节点的右孩子的左孩子作为右新根节点的左孩子的孩子。好了，我们现在为序列数组={2,1,4,3,5,6}构建二叉排序树，并进行左旋，现在用代码实现；(1)新建节点类Node：packagecom.xiaoer.binarysorttree；publicclassNode{privateNodeleftNode;privateNoderightNode;privateintvalue;//返回左子树的高度publicintleftHeight(){intheight=leftNode==null?0:左节点.height();returnheight;}//返回右子树的高度publicintrightHeight(){intheight=rightNode==null?0:右节点.height();returnheight;}//返回当前节点的高度publicintheight(){intheight=Math.max(leftNode==null?0:leftNode.height(),rightNode==null?0:rightNode.height())+1;returnheight;}publicNode(intvalue){super();this.value=value;}//添加节点方法publicvoidaddNode(Nodenode){if(node==null){System.out.println("该节点为空，请勿添加");return;}//判断传入节点的值是否小于当前节点的值if(node.value
