摘要：class BalancedBinaryTree {private Node root;public Node getRoot {return root;}//添加结点public void add(Node node) {//root为空则让root指向no
数据结构经常被大厂考察，比如：平衡二叉树？失衡问题...等等，下面我就重点谈谈平衡二叉树@mikechen
平衡二叉树，英文名Balanced Binary Tree，是一种自平衡的树，也叫AVL树。
平衡二叉树具有以下性质：
平衡二叉树规定了左结点小于根节点，右结点大于根节点；并且还规定了左子树和右子树的高度差不得超过1，这样保证了它不会成为线性的链表；如下图所示：
在二叉查找树中存在退化成单链表的极端情况，例如序列，构建二叉查找树如图所示：
此时构造的二叉搜索树为右斜树，同时二叉树退化成单链表，搜索效率降低为 O(n)，在此二叉搜索树中查找元素 6 需要查找 6 次，严重影响了查询效率。
怎样才能提升查询效率呢？
我们发现：二叉搜索树的查找效率取决于树的高度，因此保持树的高度最小，即可保证树的查找效率。
那如何去恢复平衡，使得二叉搜索树依然成立为一棵平衡树？
主要的解决办法：就是通过左旋和右旋来解决，防止特殊情况出现上面的线性结构。
1.左旋的情况
为了调整高度差，则通过左旋便可修复，如下图所示：
还是动态演示下，这样更容易理解左旋。
2.右旋的情况
备注：这样的方式也有对应的缺点，由于要维持自身的平衡，所以进行插入和删除结点操作的时候，需要对结点进行频繁的旋转。
class BalancedBinaryTree {private Node root;public Node getRoot {return root;}//添加结点public void add(Node node) {//root为空则让root指向nodeif (this.root == null) {this.root = node;} else {this.root.add(node);}}//中序遍历public void infixOrder {if (this.root == null) {System.out.println("二叉排序树为空，无法遍历！");} else {this.root.infixOrder;}}}class Node {int value;Node left;Node right;public Node(int value) {this.value = value;}@Overridepublic String toString {return "Node{" +"value=" + value +'}';}//左旋转public void leftRotate {//创建一个新结点 将当前结点的值赋值给它Node newNode = new Node(this.value);//将新结点的左子树设置成当前结点的左子树newNode.left = this.left;//将新结点的右子树设置为当前结点的右子结点的左子树newNode.right = this.right.left;//把当前结点的值换成右子结点的值this.value = this.right.value;//把当前结点的右子树设置成当前结点的右子结点的右子树this.right = this.right.right;//把当前结点的左子结点设置成新结点this.left = newNode;}//右旋转public void rightRotate {//创建一个新结点，把当前结点的值赋值给新结点Node newNode = new Node(this.value);//将新结点的右子树设置成当前结点的右子树newNode.right = this.right;//将新结点的左子树设置成当前结点的左子结点的右子树newNode.left = this.left.right;//将当前结点的值设置成当前结点左子结点的值this.value = this.left.value;//将当前结点的右子结点设置成新结点this.right = newNode;//将当前结点的左子结点设置成左子结点的左子树this.left = this.left.left;}//返回以当前结点为根结点的树的高度public int height {//返回左子树和右子树中较大的高度再加上当前结点的高度return Math.max(left == null ? 0 : left.height, right == null ? 0 : right.height) + 1;}//返回左子树的高度public int leftHeight {if (this.left == null) {return 0;}return this.left.height;}//返回右子树的高度public int rightHeight {if (this.right == null) {return 0;}return this.right.height;}//添加结点public void add(Node node) {if (node == null) {return;}//判断传入的结点的值与当前子树的根结点的关系//要添加的结点的值小于当前结点的值if (node.value this.value) {//要添加的结点的值大于当前结点的值//当前结点的右子结点为空if (this.right == null) {this.right = node;} else {//递归向右子树添加this.right.add(node);}}//当添加完一个结点后，如果右子树的高度-左子树的高度 > 1 则左旋转if (rightHeight - leftHeight > 1) {//如果当前结点的右子树的左子树的高度大于当前结点的右子树的右子树的高度//则需要先对当前结点的右子树进行右旋转//因为rightHeight - leftHeight > 1 所以this.right肯定不为nullif (this.right.leftHeight > this.right.rightHeight) {this.right.rightRotate;}//左旋转leftRotate;//一定要return！因为旋转完后已经平衡，//如果还让下面的进行判断，很有可能出问题return;}//左子树的高度-右子树的高度 > 1 则右旋转if (leftHeight - rightHeight > 1) {//如果当前结点的左子树的右子树的高度大于当前结点的左子树的左子树的高度//则需要先对当前结点的左子树进行左旋转//因为leftHeight - rightHeight > 1 所以this.left肯定不为nullif (this.left.rightHeight > this.left.leftHeight) {this.left.leftRotate;}//右旋转rightRotate;return;}}//中序遍历public void infixOrder {if (this.left != null) {this.left.infixOrder;}System.out.println(this);if (this.right != null) {this.right.infixOrder;}}}本文作者：mikechen睿哥
文章来源：mikechen.cc
来源：肥学教育
免责声明：本站系转载，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与本站联系，我们将在第一时间删除内容!
