二叉排序树可能出现的问题给定一个序列{1,2,3,4,5,6}，要求创建一棵二叉排序树（BST),问题分析问题分析：左子树全为空，从形式上看更像是一个单链表；插入速度没有影响；查询速度明显降低（因为需要比较），不能发挥BST的优势。因为每次都比较左子树，所以它的查询速度比单向链表慢。解决方案-平衡二叉树（ALV）基本介绍平衡二叉树又称为平衡二叉搜索树（Self-balancingbinarysearchtree），又名AVL树，可以保证较高的查询效率。它具有以下特点：为一棵空树或其左右子树高度差的绝对值不超过1，且左右子树均为平衡二叉树。平衡二叉树常见的实现方式有红黑树、AVL、scapegoattree、Treap、stretchtree等；比如下图中的前两个就是平衡二叉树。左右子树高度差的绝对值为0，第三个的左右子树高度差的绝对值为2，所以第三个不是平衡二叉树；平衡二叉树左旋步骤：创建一个新节点newNode，其值等于当前根节点的值。将新节点的左子树设置为当前节点的左子树。将新节点的右子树设置为当前节点右子树的左子树。用当前右子节点的值替换当前节点的值。将当前节点的右子树设置为右子树的右子树。将当前节点的左子树设置为新节点。平衡二叉树的右旋步骤：创建一个新节点，其值等于当前根节点的值。将新节点的右子树设置为当前节点的右子树。将新节点的左子树设置为当前节点左子树的右子树。将当前节点的值转置为左子节点的值。将当前节点的左子树设置为左子树的左子树。将当前节点的右子树设置为新节点。平衡二叉树的二次旋转在某些情况下，一次旋转无法完成平衡二叉树的转换，需要二次旋转。如果其右子树的左子树的高度大于其右子树的右子树的高度，则需要先将右子树向右旋转，再将当前节点向左旋转。如果其左子树的右子树的高度大于其左子树的左子树的高度，则需要先对左子树进行左旋转，再对当前节点进行右旋转。代码示例packagecom.xie.avl；publicclassAVLTreeDemo{publicstaticvoidmain(String[]args){int[]arr={4,3,6,5,7,8};AVLTreeavlTree=newAVLTree();for(inti=0;i=this.value){//如果搜索到的节点的值小于当前节点的值，递归搜索到左子树返回this。right.searchParent(node);}else{returnnull;}}}/***找到要删除的节点**@paramvalue要删除的节点的值*@return要删除的节点*/publicNodesearch(intvalue){if(value==this.value){returnthis;}elseif(value1，执行左旋if(rightHeight()-leftHeight()>1){//如果其右子树的左子树的高度大于其右子树的右子树的高度，则需要先将右子树向右旋转,然后将当前节点向左旋转if(right!=null&&right.leftHeight()>right.rightHeight()){right.rightRotate();leftRotate();}else{//可以直接向左旋转leftRotate();}return;}//当一个是添加节点后，if(左子树高度-右子树高度)>1，进行右旋转if(leftHeight()-rightHeight()>1){//如果其左子树的右子树高度大于其的左子树的左子树高度需要先将左子树向左旋转，然后再向右旋转当前节点if(left!=null&&left.rightHeight()>left.leftHeight()){left.leftRotate();rightRotate();}else{//直接向右旋转rightRotate();}}}//中序遍历publicvoidinfixOrder(){if(this.left!=null){this.left.infixOrder();}System.out.println(this);if(this.right!=null){this.right.infixOrder();}}@OverridepublicStringtoString(){return"Node{"+"value="+value+'}';}}【小编推荐】微服务面试必问的Dubbo，详细到你还怕找不到工作？2021年值得关注的5大IT行业发展趋势免费安全软件是孤独的！尴尬的是界面UI即将大改！Windows1021H2最新预览版抢先看微软为Windows101909推送KB5000850更新，修复资源管理器搜索等问题
