平衡二叉树（Balanced Binary Tree），也称为AVL树，是一种特殊的二叉搜索树。它的特点是任意节点的左右子树高度差不超过1，即左右子树的高度差的绝对值不超过1。
平衡二叉树的设计旨在提供较快的查找、插入和删除操作，相比于非平衡的二叉搜索树，可以保持树的相对平衡，避免出现退化的情况。
实现平衡二叉树的关键在于保持树的平衡性。当插入或删除节点后，如果不满足平衡条件，则需要通过旋转操作进行调整，使其重新恢复平衡。
常见的平衡二叉树实现有AVL树和红黑树。AVL树是最早提出的平衡二叉树，它通过节点的左右子树高度差进行调整。而红黑树是一种近似平衡的二叉搜索树，通过调整节点的颜色和旋转操作来维持树的平衡。
使用平衡二叉树可以在最坏情况下保证查找、插入和删除等操作的时间复杂度为 O(log n)，相对于非平衡二叉搜索树的 O(n)，具备更好的性能。
节点
/** * @description: 节点 * @author: Snow * @date: 2024/1/23 * ************************************************** * 修改记录(时间--修改人--修改说明): */ public class Node { int val; Node left; Node right; Node(int val){ this.val = val; } Node(int val, Node left, Node right){ this.val = val; this.left = left; this.right = right; } /** 添加节点 */ public void add(Node node){ if( node.val <= this.val ){ if( this.left == null ){ this.left = node; return; }else{ this.left.add(node); } }else{ if( this.right == null ){ this.right = node; return; }else{ this.right.add(node); } } } /** 中序遍历 */ public void mid(){ if( this.left != null ){ this.left.mid(); } System.out.print(this.val + " "); if( this.right != null ){ this.right.mid(); } } /** 左旋 */ public void leftRotate(){ // 声明一个新的节点 让这个节点的值等于当前节点的值.左节点的值为当前节点的left值，右节点的值为当前节点的right的left的值 Node newNode = new Node(val, left, right.left); // 当前节点的值换为 当前节点的right的值 this.val = right.val; // 新的节点 设置为 当前节点的左边 this.left = newNode; // 当前节点的右节点的右边 设置为 当前节点的右边 this.right = right.right; } }
平衡二叉树
/** * @description: 平衡二叉树 * @author: Snow * @date: 2024/1/23 * ************************************************** * 修改记录(时间--修改人--修改说明): */ public class BalancedBinaryTree { /** 根节点 */ Node root; /** 添加节点 */ public void add(Node node){ if( node == null ){ return; } if( root == null ){ root = node; return; } root.add(node); } /** 遍历 */ public void traverse(){ if( root != null ){ root.mid(); } } /** * 获取节点高度 * @param node * @return */ public int getHeight(Node node) { return Math.max( node.left == null ? 0 : getHeight(node.left), node.right == null ? 0 : getHeight(node.right) ) + 1; } }
测试
public class BalancedBinaryTreeTest { public static void main(String[] args) { BalancedBinaryTree tree = new BalancedBinaryTree(); int[] arr = {4,3,6,5,7,8}; for (int i : arr) { tree.add(new Node(i)); } tree.traverse(); System.out.println("tree height: " + tree.getHeight(tree.root)); System.out.println("左: " + tree.getHeight(tree.root.left)); System.out.println("右: " + tree.getHeight(tree.root.right)); System.out.println("左旋"); tree.root.leftRotate(); System.out.println("tree height: " + tree.getHeight(tree.root)); System.out.println("左: " + tree.getHeight(tree.root.left)); System.out.println("右: " + tree.getHeight(tree.root.right)); tree.traverse(); } }
