Java 데이터 구조의 AVL 트리에 대한 자세한 설명

이 글은 균형 이진 트리(AVL 트리)에 대한 관련 지식을 주로 소개하는 java에 대한 관련 지식을 제공합니다. AVL 트리는 본질적으로 균형 기능을 갖춘 이진 검색 트리입니다. 함께 살펴보세요. 모두를 돕습니다.

추천 학습: "java 비디오 튜토리얼"

AVL 트리 소개

이진 트리 검색은 검색 효율성이 매우 높지만 이진 트리 검색은 다음과 같은 극단적인 상황으로 이어집니다.

이러한 이진 트리 검색 효율성은 연결리스트보다 낮습니다. 검색 이진 트리를 기반으로 나타나는 균형 이진 트리(AVL 트리)가 이 문제를 해결합니다. 균형 이진 트리(AVL 트리)에서 노드의 왼쪽 하위 트리와 오른쪽 하위 트리 간 높이 차이의 절대값이 1보다 큰 경우 회전 작업을 통해 높이 차이가 줄어듭니다.

기본 개념

AVL 트리는 본질적으로 이진 검색 트리입니다. 그 특성은 다음과 같습니다.

1. 자체는 먼저 이진 검색 트리입니다.
二叉搜索树。
2. 每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。
3. 当插入一个节点或者删除一个节点时，导致某一个节点的左右子树高度差的绝对值大于1，这时需要通过左旋和右旋的操作使二叉树再次达到平衡状态。

平衡因子(balanceFactor)

• 一个结点的左子树与右子树的高度之差。
• AVL树中的任意结点的BF只可能是-1，0和1。

基础设计

下面是AVL树需要的简单方法和属性：

public class AVLTree <e>>{
    class Node{
        E value;
        Node left;
        Node right;
        int height;
        public Node(){}
        public Node(E value){
            this.value = value;
            height = 1;
            left = null;
            right = null;
        }
        public void display(){
            System.out.print(this.value + " ");
        }
    }
    Node root;
    int size;
    public int size(){
        return size;
    }
    public int getHeight(Node node) {
        if(node == null) return 0;
        return node.height;
    }
    //获取平衡因子(左右子树的高度差，大小为1或者0是平衡的，大小大于1不平衡)
    public int getBalanceFactor(){
        return getBalanceFactor(root);
    }
    public int getBalanceFactor(Node node){
        if(node == null) return 0;
        return getHeight(node.left) - getHeight(node.right);
    }

    //判断一个树是否是一个平衡二叉树
    public boolean isBalance(Node node){
        if(node == null) return true;
        int balanceFactor = Math.abs(getBalanceFactor(node.left) - getBalanceFactor(node.right));
        if(balanceFactor > 1) return false;
        return isBalance(node.left) && isBalance(node.right);
    }
    public boolean isBalance(){
        return isBalance(root);
    }

    //中序遍历树
    private  void inPrevOrder(Node root){
        if(root == null) return;
        inPrevOrder(root.left);
        root.display();
        inPrevOrder(root.right);
    }
    public void inPrevOrder(){
        System.out.print("中序遍历：");
        inPrevOrder(root);
    }}</e>

RR(左旋)

往一个树右子树的右子树上插入一个节点，导致二叉树变得不在平衡，如下图，往平衡二叉树中插入5，导致这个树变得不再平衡，此时需要左旋操作，如下：

代码如下：

//左旋,并且返回新的根节点
    public Node leftRotate(Node node){
        System.out.println("leftRotate");
       Node cur = node.right;
       node.right = cur.left;
       cur.left = node;
       //跟新node和cur的高度
        node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1;
        cur.height = Math.max(getHeight(cur.left),getHeight(cur.right)) + 1;
        return cur;
    }

LL(右旋)

往一个AVL树左子树的左子树上插入一个节点，导致二叉树变得不在平衡，如下图，往平衡二叉树中插入2，导致这个树变得不再平衡，此时需要左旋操作，如下：

代码如下：

 //右旋，并且返回新的根节点
    public Node rightRotate(Node node){
        System.out.println("rightRotate");
        Node cur = node.left;
        node.left = cur.right;
        cur.right = node;
        //跟新node和cur的高度
        node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1;
        cur.height = Math.max(getHeight(cur.left),getHeight(cur.right)) + 1;
        return cur;
    }

LR(先左旋再右旋)

往AVL树左子树的右子树上插入一个节点，导致该树不再平衡，需要先对左子树进行左旋，再对整棵树右旋，如下图所示，插入节点为5.

RL(先右旋再左旋)

往AVL树右子树的左子树上插入一个节点，导致该树不再平衡，需要先对右子树进行右旋，再对整棵树左旋각 노드의 왼쪽 및 오른쪽 하위 트리 높이 차이의 절대값(균형 요소)은 최대 1입니다. 즉, AVL 트리는 본질적으로 균형 함수를 갖는 이진 검색 트리(이진 정렬 트리, 이진 검색 트리)입니다.
노드를 삽입하거나 삭제할 때 노드의 왼쪽과 오른쪽 하위 트리 사이의 높이 차이의 절대값이 1보다 큽니다. 이 경우 왼쪽 회전 및 오른쪽 회전의 연산은 이진 트리를 다시 균형 잡힌 상태에 도달하게 합니다. 균형 요소(balanceFactor)

노드의 왼쪽 하위 트리와 오른쪽 하위 트리 사이의 높이 차이입니다.

AVL 트리에 있는 모든 노드의 BF는 -1, 0 및 1만 될 수 있습니다.

기본 디자인

다음은 AVL 트리에 필요한 간단한 메서드와 속성입니다.

//添加元素
    public  void add(E e){
        root = add(root,e);
    }
    public Node add(Node node, E value) {
        if (node == null) {
            size++;
            return new Node(value);
        }
        if (value.compareTo(node.value) > 0) {
            node.right = add(node.right, value);
        } else if (value.compareTo(node.value)  1 && getBalanceFactor(node.left) >= 0) {
            return rightRotate(node);
        }
        //该子树不平衡且新插入节点(导致不平衡的节点)在右子树子树的右子树上，此时需要进行左旋
        else if (balanceFactor  1 && getBalanceFactor(node.left)  0
        //该子树不平衡且新插入节点(导致不平衡的节点)在右子树的左子树上，此时需要先对右子树右旋，再整个树左旋
        else if(balanceFactor  0) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }

RR(왼쪽 회전)

🎜트리를 오른쪽 하위 트리에 삽입합니다. 오른쪽 하위 트리 노드로 인해 이진 트리가 불균형해집니다. 아래 그림과 같이 균형 잡힌 이진 트리에 5를 삽입하면 트리가 불균형해집니다. 🎜🎜 코드는 다음과 같습니다. 🎜

 //删除节点
    public E remove(E value){
        root = remove(root,value);
        if(root == null){
            return null;
        }
        return root.value;
    }
    public Node remove(Node node, E value){
        Node retNode = null;
        if(node == null)
            return retNode;
        if(value.compareTo(node.value) > 0){
            node.right = remove(node.right,value);
            retNode = node;
        }
        else if(value.compareTo(node.value)  1 && getBalanceFactor(retNode.left) >= 0) {
            return rightRotate(retNode);
        }
        //该子树不平衡且新插入节点(导致不平衡的节点)在右子树子树的右子树上，此时需要进行左旋
        else if (balanceFactor  1 && getBalanceFactor(retNode.left)  0) {
            retNode.right = rightRotate(retNode.right);
            return leftRotate(retNode);
        }
        return  retNode;
    }

🎜 LL(오른쪽 회전)🎜🎜AVL 트리의 왼쪽 하위 트리를 향해 왼쪽 하위 트리에 노드를 삽입하면 아래 그림과 같이 이진 트리가 불균형해집니다. 균형 이진 트리에 2를 삽입하면 트리가 불균형해집니다. 이때 다음과 같이 좌회전 조작이 필요합니다. 🎜🎜 코드는 다음과 같습니다: 🎜rrreee🎜LR(먼저 왼쪽으로 돌린 다음 오른쪽으로 돌림)🎜🎜AVL 트리의 왼쪽 하위 트리의 오른쪽 하위 트리에 노드를 삽입합니다. 아래 그림과 같이 먼저 왼쪽 하위 트리를 왼쪽으로 회전한 다음 전체 트리를 오른쪽으로 회전해야 합니다. 삽입된 노드는 5입니다.🎜🎜🎜RL (우선 우회전 후 좌회전)🎜🎜AVL 트리의 오른쪽 하위 트리의 왼쪽 하위 트리에 노드를 삽입하면 트리가 더 이상 균형을 이루지 않게 됩니다. 오른쪽 하위 트리에서 오른쪽 회전을 수행한 다음 전체 트리에서 왼쪽 회전을 수행합니다. 아래 그림과 같이 삽입된 노드는 2.🎜🎜 🎜🎜Add입니다. node🎜rrreee🎜Delete node🎜rrreee🎜추천 학습: "🎜java 비디오 튜토리얼🎜"🎜

위 내용은 Java 데이터 구조의 AVL 트리에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!