Javaのデータ構造のAVLツリーの詳細説明-＆＃＆チュートリアル-php.cn

この記事では、java に関する関連知識を提供します。主にバランスバイナリツリー (AVL ツリー) に関する関連知識を紹介します。AVL ツリーは、本質的にはバランス機能を備えたバイナリツリーです。ツリーを見つけて、見てください、皆さんのお役に立てれば幸いです。

Javaのデータ構造のAVLツリーの詳細説明

推奨学習: 「java ビデオチュートリアル」

AVL ツリーの紹介

バイナリツリーの検索は非常に便利です。 high 検索効率は高いですが、二分木の検索では次のような極端な状況が発生します。
Javaのデータ構造のAVLツリーの詳細説明
このような二分木の検索効率は、連結リストの検索効率よりもさらに低くなります。この問題を解決するのが、探索二分木に基づいて現れるバランス二分木（AVLツリー）です。平衡二分木 (AVL ツリー) のノードの左右のサブツリー間の高さの差の絶対値が 1 より大きい場合、それらの高さの差は回転操作によって減少します。

基本概念

AVL ツリーは本質的には二分探索木であり、その特徴は次のとおりです:

それ自体がまず 二分探索木です。 。
各ノードの左右のサブツリーの 高さの差の絶対値 (バランス係数) は最大 1 です。言い換えれば、AVL ツリーは本質的に、 バランシング関数 を備えた二分探索ツリー (二分ソートツリー、二分探索ツリー) です。
ノードを挿入または削除する場合、ノードの左右のサブツリー間の高さの差の絶対値は 1 より大きくなります。この場合、左回転と 右回転#が必要です。 ##この操作により、バイナリツリーは再び平衡状態に戻ります。

バランス係数 (balanceFactor)

。 AVL ツリー内のノードの BF は、

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 (左利き)

Go to one ツリーの右サブツリーの右サブツリーにノードを挿入すると、次の図に示すように、二分木がアンバランスになります。バランスの取れた二分木に 5 を挿入すると、ツリーがアンバランスになります。今回は、次のように左回転操作が必要です。

コードは次のとおりです。 Javaのデータ構造のAVLツリーの詳細説明

//左旋,并且返回新的根节点
    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 を挿入すると、二分木のバランスが崩れます。下図のように、バランスのとれた二分木に 2 を挿入すると、ツリーのバランスが崩れます。次のような操作が必要です。

コードは次のとおりです。 Javaのデータ構造のAVLツリーの詳細説明

 //右旋，并且返回新的根节点
    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 (最初に左折してから右に回転)

Insert a Node to AVL ツリーの右サブツリー

左サブツリーが原因で、ツリーのバランスが取れなくなります。最初に 左サブツリー# で左回転を実行する必要があります。##、次に右回転 ツリー全体 以下の図に示すように、ノード 5.
RL (最初に右折してから左折) Javaのデータ構造のAVLツリーの詳細説明

Insert AVL ツリー

右のサブツリーの左のサブツリー

にノードが追加され、ツリーのバランスが崩れます。まず

右のサブツリー を右回転してから 全体を右回転する必要があります以下の図に示すように、ツリーは左巻きです。、挿入されたノードは 2 です。
ノードの追加 Javaのデータ構造の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;
    }

ログイン後にコピー

ノードの削除

 //删除节点
    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;
    }

ログイン後にコピー

推奨される学習: 「