数据结构|数据结构——平衡二叉树（AVL）数据结构|java

基本介绍

1）、平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树，可以保证查询效率较高。
2）、具有以下特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。
3）、如下：

文章图片

思路分析单旋转-左旋转

文章图片

单旋转-右旋转 【数据结构|数据结构——平衡二叉树（AVL）】

文章图片

双旋转

前面举例所列出的数列，进行单旋转（即一次旋转）就可以将非平衡二叉树转成平衡二叉树，但是在某些情况下，单旋转不能完成平衡二叉树的转换，如：int[] arr = {10,11,7,6,8,9}，int[] arr = {2,1,6,5,7,3}，根据上面的思路进行操作之后，并没有转成AVL树。

文章图片
问题分析：

当符合右旋转的条件时
如果它的左子树的右子树高度大于左子树的左子树的高度
先对当前这个节点的左节点进行坐旋转
再对当前节点进行右旋转操作即可。

文章图片

示例代码示例代码只展示了平衡二叉树的添加操作，其余操作同二叉排序树（BST），详情请移驾数据结构——二叉排序树（BST）

public class AVLTreeDemo { public static void main(String[] args) {//int[] arr = {4, 3, 6, 5, 7, 8}; //int[] arr = {10, 8, 12, 7, 9, 6}; int[] arr ={10,11,7,6,8,9}; //int[] arr = { 9, 6,12,33}; AVLTree avlTree = new AVLTree(); for (int item : arr) { avlTree.addNode(new Node(item)); } avlTree.infixOrder(); System.out.println("平衡处理之前："); System.out.println("根节点：" + avlTree.getRoot()); System.out.println("树的高度：" + avlTree.getRoot().height()); System.out.println("左子树的高度：" + avlTree.getRoot().leftHeight()); System.out.println("右子树的高度：" + avlTree.getRoot().rightHeight()); } }@Data class AVLTree {private Node root; /** * 中序遍历 */ public void infixOrder() { if (root == null) { System.out.println("空树，无法进行遍历"); } else { root.infixOrder(); } }/** * 添加节点 * * @param node */ public void addNode(Node node) { if (node == null) { return; } /*如果根节点为空，待添加的节点直接加到根节点即可*/ if (root == null) { root = node; } else { root.add(node); } } }@Data class Node { private int value; private Node left; private Node right; public Node(int value) { this.value = https://www.it610.com/article/value; }@Override public String toString() { return"Node{" + "value="https://www.it610.com/article/+ value +'}'; }/** * 中序遍历 */ public void infixOrder() { if (this.left != null) { this.left.infixOrder(); } System.out.println(this); if (this.right != null) { this.right.infixOrder(); } }/** * 添加节点 * * @param node */ public void add(Node node) { /*如果当前节点的值大于待添加节点的值，则待添加节点应加入到当前节点的左子树*/ if (node.value < value) { /*如果左子树为空，说明已找到待添加的位置*/ if (this.left == null) { this.left = node; } else { /*向左递归查找添加位置*/ this.left.add(node); } /*如果当前节点的值小于等于待添加节点的值，则待添加节点应加入到当前节点的右子树*/ } else { /*如果右子树为空，说明已找到待添加的位置*/ if (this.right == null) { this.right = node; } else { /*向右递归查找添加位置*/ this.right.add(node); } } /*平衡二叉树操作*/ AVLtree(); }private void AVLtree(){ /*当添加完一个节点后，如果（右子树的高度 - 左子树的高度）> 1 ,左旋转*/ if (rightHeight() - leftHeight() > 1) { /*如果右子树的左子树高度大于右子树的右子树的高度*/ if(right != null && right.leftHeight() > right.rightHeight()){ /*对右子树进行右旋转*/ right.rightRotate(); } leftRotate(); return; }/*当添加完一个节点后，如果（左子树的高度 - 右子树的高度）> 1 ,右旋转*/ if (leftHeight() - rightHeight() > 1) { /*如果左子树的右子树高度大于它的左子树的高度*/ if(left != null && left.rightHeight() > left.leftHeight()){ /*先对当前节点的左节点（左子树）→ 左旋转*/ left.leftRotate(); } rightRotate(); return; } }/** * 返回以当前节点为根节点的左子树的高度 * * @return */ public int leftHeight() { if (left == null) { return 0; } return left.height(); }/** * 返回以当前节点为根节点的右子树的高度 * * @return */ public int rightHeight() { if (right == null) { return 0; } return right.height(); }/** * 返回以当前节点为根节点的树的高度 * * @return */ public int height() { return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1; }/** * 左转方法 */ public void leftRotate() { /*创建新的节点，节点值为当前根节点的值*/ Node newNode = new Node(value); /*把新的节点的左子树设置成当前节点的左子树*/ newNode.left = left; /*新节点的右子树指向当前节点右子树的左子树*/ newNode.right = right.left; /*把当前节点的值替换成右子节点的值*/ value = https://www.it610.com/article/right.value; /*把当前节点右子树设置成当前节点右子树的右子树*/ right = right.right; /*把当前节点的左子树（左子节点设置成新的节点）*/ left = newNode; }public void rightRotate() { /*创建新的节点，节点值为当前根节点的值*/ Node newNode = new Node(value); /*把新的节点的右子树设置成当前节点的右子树*/ newNode.right = right; /*新节点的左子树指向当前节点左子树的右子树*/ newNode.left = left.right; /*把当前节点的值替换成左子节点的值*/ value = left.value; /*把当前节点右子树设置成当前节点右子树的右子树*/ left = left.left; /*把当前节点的左子树（左子节点设置成新的节点）*/ right = newNode; } }