平衡二叉树 (平衡查找树)

小咪咪 2021-10-29 07:24 510阅读 0赞

## **平衡二叉树(AVL 树)** ##

### 看一个案例(说明二叉排序树可能的问题) ###

![1460404-20190609204205330-1398837969.png][]

#### **上边 BST 存在的问题分析:** ####

1.  左子树全部为空，从形式上看，更像一个单链表.
2.  插入速度没有影响
3.  查询速度明显降低(因为需要依次比较), 不能发挥 BST

### **基本介绍** ###

1.  平衡二叉树也叫平衡**二叉搜索树**（Self-balancing binary search tree）又被称为 AVL 树， 可以保证查询效率较高。
2.  具有以下特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵。

平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

### **应用案例-单旋转(左旋转)** ###

//左旋转方法
    
    
    
    private void leftRotate() {
    
    
    
    
    
    //创建新的结点，以当前根结点的值
    
    
    
    Node newNode = new Node(value);
    
    
    
    //把新的结点的左子树设置成当前结点的左子树
    
    
    
    newNode.left = left;
    
    
    
    //把新的结点的右子树设置成带你过去结点的右子树的左子树
    
    
    
    newNode.right = right.left;
    
    
    
    //把当前结点的值替换成右子结点的值
    
    
    
    value = right.value;
    
    
    
    //把当前结点的右子树设置成当前结点右子树的右子树
    
    
    
    right = right.right;
    
    
    
    //把当前结点的左子树(左子结点)设置成新的结点
    
    
    
    left = newNode;
    
    
    
    }

### **应用案例-单旋转(右旋转)** ###

//右旋转
    
    
    
    private void rightRotate() {
    
    
    
    Node newNode = new Node(value); 
    
    newNode.right = right; 
    
    newNode.left = left.right;
    
    value = left.value; 
    
    left = left.left; 
    
    right = newNode;
    
    }

### **应用案例-双旋转** ###

#### **解决思路分析** ####

1.  当符合右旋转的条件时
2.  如果它的左子树的右子树高度大于它的左子树的高度
3.  先对当前这个结点的左节点进行左旋转
4.  在对当前结点进行右旋转的操作即可

#### **代码实现\[AVL 树的汇总代码(完整代码)\]** ####

package com.kyrie.avl;
    
    
    
    public class AVLTreeDemo {
    
    
    
        public static void main(String[] args) {
    
    //        int[] arr = { 4, 3, 6, 5, 7, 8 };
    
            int[] arr = { 10, 11, 7, 6, 8, 9 };
    
    
    
            // AVLTree
    
            AVLTree avlTree = new AVLTree();
    
            // 添加节点
    
            for (int i = 0; i < arr.length; i++) {
    
                avlTree.add(new Node(arr[i]));
    
            }
    
    
    
            // 遍历
    
            System.out.println("中序遍历");
    
            avlTree.infixOrder();
    
    
    
            System.out.println("平衡处理后：");
    
            System.out.println("树高 = " + avlTree.getRoot().height());
    
            System.out.println("左子树高度 = " + avlTree.getRoot().leftHeight());
    
            System.out.println("右子树高度 = " + avlTree.getRoot().rightHeight());
    
            System.out.println("根节点为 = " + avlTree.getRoot());
    
    
    
        }
    
    
    
    }
    
    
    
    //创建AVL树    AVL:平衡二叉树 (平衡查找树)
    
    class AVLTree {
    
        private Node root;// 根节点
    
    
    
        public Node getRoot() {
    
            return root;
    
        }
    
    
    
        // 添加节点的方法
    
        public void add(Node node) {
    
            if (root == null) {
    
                root = node;
    
            } else {
    
                root.add(node);
    
            }
    
        }
    
    
    
        // 中序遍历
    
        public void infixOrder() {
    
            if (root != null) {
    
                root.infixOrder();
    
            } else {
    
                // 此树为空
    
                System.out.println("此树为空，无法遍历");
    
            }
    
        }
    
    
    
    }
    
    
    
    class Node {
    
        int value; // 当前节点的值
    
        Node left; // 左孩子
    
        Node right; // 右孩子
    
    
    
        public Node(int value) {
    
            this.value = value;
    
        }
    
    
    
        @Override
    
        public String toString() {
    
            return "Node [value = " + value + "]";
    
        }
    
    
    
        // 左子树树高
    
        public int leftHeight() {
    
            if (left == null) {
    
                return 0;
    
            }
    
            return left.height();
    
        }
    
    
    
        // 右子树树高
    
        public int rightHeight() {
    
            if (right == null) {
    
                return 0;
    
            }
    
            return right.height();
    
        }
    
    
    
        // 得到树高
    
        public int height() {
    
            return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    
        }
    
    
    
        // 左旋转方法
    
        private void leftRotate() {
    
            // 创建心得节点，值为当前树的根节点的值
    
            Node newNode = new Node(value);
    
            // 把新的节点的左孩子设置成当前节点的左孩子
    
            newNode.left = left;
    
            // 把新的节点的右孩子设置成当前节点的右孩子的左孩子
    
            newNode.right = right.left;
    
            // 把当前节点的值替换成右孩子的值
    
            value = right.value;
    
            // 把当前节点的右孩子设置成当前节点右孩子的右孩子
    
            right = right.right;
    
            // 把当前节点的左孩子设置成新的节点
    
            this.left = newNode;
    
        }
    
    
    
        // 右旋转方法
    
        private void rightRotate() {
    
            Node newNode = new Node(value);
    
            newNode.right = right;
    
            newNode.left = left.right;
    
            value = left.value;
    
            left = left.left;
    
            this.right = newNode;
    
        }
    
    
    
        // 添加节点的方法
    
        // 递归实现，且需要满足二叉查找树的特点，左子树全小于根节点，右子树全大于根节点
    
        public void add(Node node) {
    
            if (node == null) {
    
                return;
    
            }
    
            // 判断传入节点的值与当前子树的根节点的值的关系
    
            if (node.value < this.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);
    
                }
    
            }
    
    
    
            // 判断是否满足AVL的定义 : 左右子树的高度差的绝对值不能超过1
    
            // 1.左旋转 : 右子树高度 - 左子树高度 > 1
    
            if ((rightHeight() - leftHeight()) > 1) {
    
                // 根节点的右孩子的 左子树的高度 > 根节点的右孩子的右子树高度
    
                if (right != null && right.leftHeight() > right.rightHeight()) {
    
                    // 先进行右旋转
    
                    right.rightRotate();
    
                    // 再对根节点进行左旋转
    
                    leftRotate();
    
                } else {
    
                    // 直接进行左旋转
    
                    leftRotate();
    
                }
    
    
    
                return; // 很关键，假如这个已经旋转过了，直接返回就可以了，避免节外生枝
    
            }
    
    
    
            // 2 右旋转 : 左子树高度 - 右子树高度 > 1
    
            if ((leftHeight() - rightHeight()) > 1) {
    
                if (left != null && left.rightHeight() > right.leftHeight()) {
    
                    left.leftRotate();
    
    
    
                    rightRotate();
    
                } else {
    
                    rightRotate();
    
                }
    
    
    
            }
    
    
    
        }
    
    
    
        // 中序遍历
    
        public void infixOrder() {
    
            if (this.left != null) {
    
                this.left.infixOrder();
    
            }
    
            System.out.println(this);
    
            if (this.right != null) {
    
                this.right.infixOrder();
    
            }
    
        }
    
    
    
    }

转载于:https://www.cnblogs.com/kyrie211/p/10994772.html

[1460404-20190609204205330-1398837969.png]: /images/20211029/621910e38bd3438598d122a9c896a7c1.png