久久丝袜精品在线,欧美大黄频在线观看,99精品久久一

一、平衡二叉樹(shù)

平衡二叉樹(shù) 也稱(chēng)平衡二叉搜索樹(shù)（Self-balancing binary search tree）是一種結(jié)構(gòu)平衡的二分搜索樹(shù)。

平衡二叉樹(shù)由二分搜索樹(shù)發(fā)展而來(lái)，在二分搜索樹(shù)的基礎(chǔ)上平衡二叉樹(shù)需要滿(mǎn)足兩個(gè)條件：

1、它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1。
2、左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)

平衡因子

某結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)的高度(深度)差即為該結(jié)點(diǎn)的平衡因子（BF,Balance Factor）。平衡二叉樹(shù)上所有結(jié)點(diǎn)的平衡因子只可能是 -1，0 或 1。如果某一結(jié)點(diǎn)的平衡因子絕對(duì)值大于1則說(shuō)明此樹(shù)不是平衡二叉樹(shù)。為了方便計(jì)算每一結(jié)點(diǎn)的平衡因子我們可以為每個(gè)節(jié)點(diǎn)賦予height這一屬性，表示此節(jié)點(diǎn)的高度。

常見(jiàn)的平衡二叉搜索樹(shù)有：

AVL樹(shù)
紅黑樹(shù)
Treap

二、AVL樹(shù)

AVL樹(shù) 是由 G. M. Adelson- V elsky 和 E. M. Landis于1962年提出。AVL樹(shù)是最早的平衡二叉樹(shù)。

AVL樹(shù)維護(hù)自身的平衡涉及到兩個(gè)概念：

1、節(jié)點(diǎn)的高度
2、節(jié)點(diǎn)的平衡因子

節(jié)點(diǎn)的高度就是從根節(jié)點(diǎn)到該節(jié)點(diǎn)的邊的總和

節(jié)點(diǎn)的平衡因子是左子樹(shù)的高度減去它的右子樹(shù)的高度

帶有平衡因子1、0或 -1的節(jié)點(diǎn)被認(rèn)為是平衡的，因?yàn)樗淖笥易訕?shù)高度差不超過(guò) 1。

面的兩張圖片，左邊的是AVL樹(shù)，它的任何節(jié)點(diǎn)的兩個(gè)子樹(shù)的高度差別都<=1；而右邊的不是AVL樹(shù)，因?yàn)?的兩顆子樹(shù)的高度相差為2(以2為根節(jié)點(diǎn)的樹(shù)的高度是3，而以8為根節(jié)點(diǎn)的樹(shù)的高度是1)。

三、AVL樹(shù)代碼實(shí)現(xiàn)

3.1 基礎(chǔ)設(shè)計(jì)

首先我們可以設(shè)計(jì)出AVL樹(shù)節(jié)點(diǎn)，并且實(shí)現(xiàn)一些簡(jiǎn)單通用的方法供后續(xù)操作。

public class AVLTree<K extends Comparable<K>, V> {

    //AVLTree 樹(shù)節(jié)點(diǎn)類(lèi)
    private class Node<K extends Comparable<K>, V>{

        public K key;

        public V value;

        public Node<K, V> left;

        public Node<K, V> right;

        //當(dāng)前節(jié)點(diǎn)所處的高度值
        public int height;

        public Node(K key, V value){
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
            //初始化新的節(jié)點(diǎn)都是葉子節(jié)點(diǎn)，高度都為1
            this.height = 1;
        }

        @Override
        public String toString() {
            return key.toString() +" : " + value.toString();
        }
    }

    // 根節(jié)點(diǎn)
    private Node<K, V> root;

    // 樹(shù)容量
    private Integer size;

    public AVLTree(){
        root = null;
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int getSize() {
        return size;
    }

    /**
     * 判斷該二叉樹(shù)是否是一棵平衡二叉樹(shù)
     * @return
     */
    private boolean isBalanced(){
        return isBalanced(root);
    }

    /**
     * 判斷該二叉樹(shù)是否是一棵平衡二叉樹(shù), 遞歸調(diào)用函數(shù)
     * @param node
     * @return
     */
    private boolean isBalanced(Node<K,V> node){
        //node == null 代表該樹(shù)是一顆平衡二叉樹(shù)，
        //平衡二叉樹(shù)左右子樹(shù)高度相差不超過(guò)1
        // 因?yàn)榭諛?shù)的左右子樹(shù)高度相差不超過(guò)1
        if(node == null){
            return true;
        }

        //獲取平衡因子
        int balanceFactor = getBalanceFactor(node);

        //左右子樹(shù)高度相差超過(guò)1，則不是平衡二叉樹(shù)
        if(Math.abs(balanceFactor) > 1){
            return false;
        }
        //遞歸調(diào)用該節(jié)點(diǎn)的左右子樹(shù)，判斷是否是平衡二叉樹(shù)
        return isBalanced(node.left) && isBalanced(node.right);
    }


    /**
     * 返回node節(jié)點(diǎn)的高度值
     * @param node
     * @return
     */
    private int getHeight(Node<K, V> node){
        if(node == null){
            return 0;
        }
        return node.height;
    }

    /**
     * 獲取節(jié)點(diǎn)node的平衡因子
     * @param node
     * @return
     */
    private int getBalanceFactor(Node<K, V> node){
        if(node == null){
            return 0;
        }
        return getHeight(node.left) - getHeight(node.right);
    }
}

3.2 添加節(jié)點(diǎn)

往平衡二叉樹(shù)中添加節(jié)點(diǎn)很可能會(huì)導(dǎo)致二叉樹(shù)失去平衡，所以我們需要在每次插入節(jié)點(diǎn)后進(jìn)行平衡的維護(hù)操作。插入節(jié)點(diǎn)破壞平衡性有如下四種情況：

3.2.1 LL（右旋）

LL的意思是向左子樹(shù)（L）的左孩子（L）中插入新節(jié)點(diǎn)后導(dǎo)致不平衡，這種情況下需要右旋操作，而不是說(shuō)LL的意思是右旋，后面的也是一樣。

我們將這種情況抽象出來(lái)，得到下圖：

我們需要對(duì)節(jié)點(diǎn)y進(jìn)行平衡的維護(hù)。步驟如下圖所示：

 * 右旋轉(zhuǎn)
 * // 對(duì)節(jié)點(diǎn)y進(jìn)行向右旋轉(zhuǎn)操作，返回旋轉(zhuǎn)后新的根節(jié)點(diǎn)x
 * //        y                              x
 * //       / \                           /   \
 * //      x   T4     向右旋轉(zhuǎn) (y)        z     y
 * //     / \       - - - - - - - ->    / \   / \
 * //    z   T3                       T1  T2 T3 T4
 * //   / \
 * // T1   T2

/**
 * 右旋轉(zhuǎn)
 * // 對(duì)節(jié)點(diǎn)y進(jìn)行向右旋轉(zhuǎn)操作，返回旋轉(zhuǎn)后新的根節(jié)點(diǎn)x
 * //        y                              x
 * //       / \                           /   \
 * //      x   T4     向右旋轉(zhuǎn) (y)        z     y
 * //     / \       - - - - - - - ->    / \   / \
 * //    z   T3                       T1  T2 T3 T4
 * //   / \
 * // T1   T2
 * @param y
 * @return
 */
private Node<K, V> rightRotate(Node<K, V> y){
    Node<K, V> x = y.left;
    Node<K, V> T3 = x.right;
    //向右旋轉(zhuǎn)過(guò)程
    x.right = y;
    y.left = T3;

    //更新節(jié)點(diǎn)的高度height值
    y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
    return x;
}

3.2.2 RR（左旋）

我們將這種情況抽象出來(lái)，得到下圖：

我們需要對(duì)節(jié)點(diǎn)y進(jìn)行平衡的維護(hù)。步驟如下圖所示：

 * 向左旋轉(zhuǎn)
 * // 對(duì)節(jié)點(diǎn)y進(jìn)行向左旋轉(zhuǎn)操作，返回旋轉(zhuǎn)后新的根節(jié)點(diǎn)x
 * //    y                             x
 * //  /  \                          /   \
 * // T1   x      向左旋轉(zhuǎn) (y)       y     z
 * //     / \   - - - - - - - ->   / \   / \
 * //   T2  z                     T1 T2 T3 T4
 * //      / \
 * //     T3 T4

/**
 * 向左旋轉(zhuǎn)
 * // 對(duì)節(jié)點(diǎn)y進(jìn)行向左旋轉(zhuǎn)操作，返回旋轉(zhuǎn)后新的根節(jié)點(diǎn)x
 * //    y                             x
 * //  /  \                          /   \
 * // T1   x      向左旋轉(zhuǎn) (y)       y     z
 * //     / \   - - - - - - - ->   / \   / \
 * //   T2  z                     T1 T2 T3 T4
 * //      / \
 * //     T3 T4
 * @param y
 * @return
 */
private Node<K, V> leftRotate(Node<K, V> y){
    Node<K, V> x = y.right;
    Node<K, V> T2 = x.left;
    //向左旋轉(zhuǎn)過(guò)程
    x.left = y;
    y.right = T2;

    //更新節(jié)點(diǎn)的高度height值
    y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
    return x;
}

3.2.3 LR

我們將這種情況抽象出來(lái)，得到下圖：

我們需要對(duì)節(jié)點(diǎn)y進(jìn)行平衡的維護(hù)。步驟如下圖所示：

3.2.4 RL

我們將這種情況抽象出來(lái)，得到下圖：

我們需要對(duì)節(jié)點(diǎn)y進(jìn)行平衡的維護(hù)。步驟如下圖所示：

添加節(jié)點(diǎn)代碼

/**
 * 向AVL樹(shù)添加新的元素(key,value)
 * @param key
 * @param value
 */
public void add(K key, V value){
    //向根節(jié)點(diǎn)添加元素e
    root = add(root, key, value);
}

/**
 * 向以node為根的AVL樹(shù)中插入元素(key,value)，遞歸算法
 * @param node
 * @param key
 * @param value
 * @return 返回插入新元素的AVL樹(shù)的根
 */
private Node<K, V> add(Node<K, V> node, K key, V value){
    if(node == null){
        size ++;
        return new Node<>(key, value);
    }

    //遞歸調(diào)用，元素添加到node.left
    if(key.compareTo(node.key) < 0){
        node.left = add(node.left, key, value);
    }else if(key.compareTo(node.key) > 0){
        //遞歸調(diào)用，元素添加到node.right
        node.right = add(node.right, key, value);
    }else {
        node.value = value;
    }

    //更新節(jié)點(diǎn)的高度height
    node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;

    //計(jì)算平衡因子
    int balanceFactor = getBalanceFactor(node);

    //平衡維護(hù)
    //LL
    // 左子樹(shù)比右子樹(shù)高度超過(guò)了1，說(shuō)明當(dāng)前節(jié)點(diǎn)的平衡被打破
    // 且新添加的節(jié)點(diǎn)是在左子樹(shù)的左子樹(shù)的左側(cè)
    if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0){
        //右旋轉(zhuǎn)
        return rightRotate(node);
    }

    //RR
    // 右子樹(shù)比左子樹(shù)高度超過(guò)了1，說(shuō)明當(dāng)前節(jié)點(diǎn)的平衡被打破
    // 且新添加的節(jié)點(diǎn)是在右子樹(shù)的右子樹(shù)的右側(cè)
    if(balanceFactor < -1 && getBalanceFactor(node.right) <= 0){
        //左旋轉(zhuǎn)
        return leftRotate(node);
    }

    //LR
    // 左子樹(shù)比右子樹(shù)高度超過(guò)了1，說(shuō)明當(dāng)前節(jié)點(diǎn)的平衡被打破
    // 且新添加的節(jié)點(diǎn)是在左子樹(shù)的左子樹(shù)的右側(cè)
    if(balanceFactor > 1 && getBalanceFactor(node.left) < 0){
        //先對(duì)node.left進(jìn)行左旋轉(zhuǎn)
        node.left = leftRotate(node.left);
        //然后對(duì)node進(jìn)行右旋轉(zhuǎn)
        return rightRotate(node);
    }

    //RL
    // 右子樹(shù)比左子樹(shù)高度超過(guò)了1，說(shuō)明當(dāng)前節(jié)點(diǎn)的平衡被打破
    // 且新添加的節(jié)點(diǎn)是在右子樹(shù)的右子樹(shù)的左側(cè)
    if(balanceFactor < -1 && getBalanceFactor(node.right) > 0){
        //先對(duì)node.right進(jìn)行右旋轉(zhuǎn)
        node.right = rightRotate(node.right);
        //然后對(duì)node進(jìn)行左旋轉(zhuǎn)
        return leftRotate(node);
    }

    //返回當(dāng)前根節(jié)點(diǎn)
    return node;
}

3.3 刪除節(jié)點(diǎn)

在刪除AVL樹(shù)節(jié)點(diǎn)前需要知道二分搜索樹(shù)的節(jié)點(diǎn)刪除操作，和二分搜索樹(shù)刪除節(jié)點(diǎn)不同的是我們刪除AVL樹(shù)的節(jié)點(diǎn)后需要進(jìn)行平衡的維護(hù)操作。

/**
 * 返回以node為根的二分搜索樹(shù)的最小值所在的節(jié)點(diǎn)
 * @param node
 * @return
 */
private Node<K, V> minimum(Node<K, V> node){
    if(node.left == null){
        return node;
    }
    return minimum(node.left);
}

/**
 * 從二分搜索樹(shù)中刪除元素鍵為key的節(jié)點(diǎn), 并返回value, 不存在返回null
 * @param key
 * @return
 */
public V remove(K key){
   Node<K, V> node = getNode(root, key);
    if(node == null){
        //不存在直接返回null
        return null;
    }
    //存在
    root = remove(root, key);
    return node.value;
}

/**
 * 刪除以node為根的二分搜索樹(shù)中鍵為key的節(jié)點(diǎn)，遞歸遞歸方式
 * 返回刪除節(jié)點(diǎn)后新的二分搜索樹(shù)的根
 * @param node
 * @param key
 * @return
 */
private Node<K, V> remove(Node<K, V> node, K key){
    //節(jié)點(diǎn)為空，直接返回
    if(node == null){
        return null;
    }

    //聲明要返回去的node
    Node<K, V> retNode;

    if(key.compareTo(node.key) < 0){
        //待刪除元素key小于當(dāng)前節(jié)點(diǎn)的鍵，向左遞歸尋找
        node.left = remove(node.left, key);
        retNode = node;
    }else if(key.compareTo(node.key) > 0){
        //待刪除元素key大于當(dāng)前節(jié)點(diǎn)的鍵，向右遞歸尋找
        node.right = remove(node.right, key);
        retNode = node;
    }else {
        //待刪除節(jié)點(diǎn)左子樹(shù)為空
        if(node.left == null){
            Node<K, V> rightNode = node.right;
            node.right = null;
            size --;
            retNode = rightNode;
        }

        //待刪除節(jié)點(diǎn)右子樹(shù)為空
        else if(node.right == null){
            Node<K, V> rightNode = node.left;
            node.left = null;
            size --;
            retNode = rightNode;
        }else {
            //待刪除節(jié)點(diǎn)左、右子樹(shù)不為空
            //找到比待刪除節(jié)點(diǎn)大的最小節(jié)點(diǎn)，即待刪除節(jié)點(diǎn)右子樹(shù)最小節(jié)點(diǎn)
            //用這個(gè)節(jié)點(diǎn)頂替待刪除節(jié)點(diǎn)的位置

            //找到比待刪除節(jié)點(diǎn)大的最小節(jié)點(diǎn)，即待刪除節(jié)點(diǎn)右子樹(shù)最小節(jié)點(diǎn)
            Node<K, V> successor = minimum(node.right);
            //刪除比待刪除節(jié)點(diǎn)大的最小節(jié)點(diǎn)，并將返回值給succeer的右孩子
            //successor.right = removeMin(node.right);
            successor.right = remove(node.right, successor.key);

            //node.left賦值給successor.left
            successor.left = node.left;
            //node節(jié)點(diǎn)和二分搜索樹(shù)脫離關(guān)系
            node.left = node.right = null;
            retNode = successor;
        }
    }

    if(retNode == null){
        //如果刪除了該節(jié)點(diǎn)，返回的二叉樹(shù)節(jié)點(diǎn)的根節(jié)點(diǎn)為空的話(huà)
        return null;
    }

    //更新節(jié)點(diǎn)的高度height
    retNode.height = Math.max(getHeight(retNode.left), getHeight(retNode.right)) + 1;

    //計(jì)算平衡因子
    int balanceFactor = getBalanceFactor(retNode);

    //平衡維護(hù)
    //LL
    // 左子樹(shù)比右子樹(shù)高度超過(guò)了1，說(shuō)明當(dāng)前節(jié)點(diǎn)的平衡被打破
    // 且新添加的節(jié)點(diǎn)是在左子樹(shù)的左子樹(shù)的左側(cè)
    if(balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0){
        //右旋轉(zhuǎn)
        return rightRotate(retNode);
    }

    //RR
    // 右子樹(shù)比左子樹(shù)高度超過(guò)了1，說(shuō)明當(dāng)前節(jié)點(diǎn)的平衡被打破
    // 且新添加的節(jié)點(diǎn)是在右子樹(shù)的右子樹(shù)的右側(cè)
    if(balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0){
        //左旋轉(zhuǎn)
        return leftRotate(retNode);
    }

    //LR
    // 左子樹(shù)比右子樹(shù)高度超過(guò)了1，說(shuō)明當(dāng)前節(jié)點(diǎn)的平衡被打破
    // 且新添加的節(jié)點(diǎn)是在左子樹(shù)的左子樹(shù)的右側(cè)
    if(balanceFactor > 1 && getBalanceFactor(retNode.left) < 0){
        //先對(duì)node.left進(jìn)行左旋轉(zhuǎn)
        retNode.left = leftRotate(retNode.left);
        //然后對(duì)node進(jìn)行右旋轉(zhuǎn)
        return rightRotate(retNode);
    }

    //RL
    // 右子樹(shù)比左子樹(shù)高度超過(guò)了1，說(shuō)明當(dāng)前節(jié)點(diǎn)的平衡被打破
    // 且新添加的節(jié)點(diǎn)是在右子樹(shù)的右子樹(shù)的左側(cè)
    if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0){
        //先對(duì)node.right進(jìn)行右旋轉(zhuǎn)
        retNode.right = rightRotate(retNode.right);
        //然后對(duì)node進(jìn)行左旋轉(zhuǎn)
        return leftRotate(retNode);
    }

    //如果刪除節(jié)點(diǎn)后，沒(méi)有打破平衡，直接返回當(dāng)前根節(jié)點(diǎn)
    return retNode;
}

3.4 完整代碼

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: huangyibo
 * @Date: 2022/2/26 20:24
 * @Description: AVL Tree
 */

public class AVLTree<K extends Comparable<K>, V> {

    //AVLTree 樹(shù)節(jié)點(diǎn)類(lèi)
    private class Node<K extends Comparable<K>, V>{

        public K key;

        public V value;

        public Node<K, V> left;

        public Node<K, V> right;

        //當(dāng)前節(jié)點(diǎn)所處的高度值
        public int height;

        public Node(K key, V value){
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
            //初始化新的節(jié)點(diǎn)都是葉子節(jié)點(diǎn)，高度都為1
            this.height = 1;
        }

        @Override
        public String toString() {
            return key.toString() +" : " + value.toString();
        }
    }

    // 根節(jié)點(diǎn)
    private Node<K, V> root;

    // 樹(shù)容量
    private Integer size;

    public AVLTree(){
        root = null;
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int getSize() {
        return size;
    }

    /**
     * 判斷該二叉樹(shù)是否是一棵二分搜索樹(shù)
     * @return
     */
    private boolean isBST(){
        List<K> keys = new ArrayList<>();
        inOrder(root, keys);
        for (int i = 1; i < keys.size(); i++) {
            if(keys.get(i - 1).compareTo(keys.get(i)) > 0){
                return false;
            }
        }
        return true;
    }

    //中序遍歷
    private void inOrder(Node<K,V> node, List<K> keys) {
        if(node == null){
            return;
        }
        inOrder(node.left, keys);
        keys.add(node.key);
        inOrder(node.right, keys);
    }

    /**
     * 判斷該二叉樹(shù)是否是一棵平衡二叉樹(shù)
     * @return
     */
    private boolean isBalanced(){
        return isBalanced(root);
    }

    /**
     * 判斷該二叉樹(shù)是否是一棵平衡二叉樹(shù), 遞歸調(diào)用函數(shù)
     * @param node
     * @return
     */
    private boolean isBalanced(Node<K,V> node){
        //node == null 代表該樹(shù)是一顆平衡二叉樹(shù)，
        //平衡二叉樹(shù)左右子樹(shù)高度相差不超過(guò)1
        // 因?yàn)榭諛?shù)的左右子樹(shù)高度相差不超過(guò)1
        if(node == null){
            return true;
        }

        //獲取平衡因子
        int balanceFactor = getBalanceFactor(node);

        //左右子樹(shù)高度相差超過(guò)1，則不是平衡二叉樹(shù)
        if(Math.abs(balanceFactor) > 1){
            return false;
        }
        //遞歸調(diào)用該節(jié)點(diǎn)的左右子樹(shù)，判斷是否是平衡二叉樹(shù)
        return isBalanced(node.left) && isBalanced(node.right);
    }


    /**
     * 返回node節(jié)點(diǎn)的高度值
     * @param node
     * @return
     */
    private int getHeight(Node<K, V> node){
        if(node == null){
            return 0;
        }
        return node.height;
    }

    /**
     * 獲取節(jié)點(diǎn)node的平衡因子
     * @param node
     * @return
     */
    private int getBalanceFactor(Node<K, V> node){
        if(node == null){
            return 0;
        }
        return getHeight(node.left) - getHeight(node.right);
    }

    /**
     * 右旋轉(zhuǎn)
     * // 對(duì)節(jié)點(diǎn)y進(jìn)行向右旋轉(zhuǎn)操作，返回旋轉(zhuǎn)后新的根節(jié)點(diǎn)x
     * //        y                              x
     * //       / \                           /   \
     * //      x   T4     向右旋轉(zhuǎn) (y)        z     y
     * //     / \       - - - - - - - ->    / \   / \
     * //    z   T3                       T1  T2 T3 T4
     * //   / \
     * // T1   T2
     * @param y
     * @return
     */
    private Node<K, V> rightRotate(Node<K, V> y){
        Node<K, V> x = y.left;
        Node<K, V> T3 = x.right;
        //向右旋轉(zhuǎn)過(guò)程
        x.right = y;
        y.left = T3;

        //更新節(jié)點(diǎn)的高度height值
        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
        return x;
    }


    /**
     * 向左旋轉(zhuǎn)
     * // 對(duì)節(jié)點(diǎn)y進(jìn)行向左旋轉(zhuǎn)操作，返回旋轉(zhuǎn)后新的根節(jié)點(diǎn)x
     * //    y                             x
     * //  /  \                          /   \
     * // T1   x      向左旋轉(zhuǎn) (y)       y     z
     * //     / \   - - - - - - - ->   / \   / \
     * //   T2  z                     T1 T2 T3 T4
     * //      / \
     * //     T3 T4
     * @param y
     * @return
     */
    private Node<K, V> leftRotate(Node<K, V> y){
        Node<K, V> x = y.right;
        Node<K, V> T2 = x.left;
        //向左旋轉(zhuǎn)過(guò)程
        x.left = y;
        y.right = T2;

        //更新節(jié)點(diǎn)的高度height值
        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
        return x;
    }


    /**
     * 向AVL樹(shù)添加新的元素(key,value)
     * @param key
     * @param value
     */
    public void add(K key, V value){
        //向根節(jié)點(diǎn)添加元素e
        root = add(root, key, value);
    }

    /**
     * 向以node為根的AVL樹(shù)中插入元素(key,value)，遞歸算法
     * @param node
     * @param key
     * @param value
     * @return 返回插入新元素的AVL樹(shù)的根
     */
    private Node<K, V> add(Node<K, V> node, K key, V value){
        if(node == null){
            size ++;
            return new Node<>(key, value);
        }

        //遞歸調(diào)用，元素添加到node.left
        if(key.compareTo(node.key) < 0){
            node.left = add(node.left, key, value);
        }else if(key.compareTo(node.key) > 0){
            //遞歸調(diào)用，元素添加到node.right
            node.right = add(node.right, key, value);
        }else {
            node.value = value;
        }

        //更新節(jié)點(diǎn)的高度height
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;

        //計(jì)算平衡因子
        int balanceFactor = getBalanceFactor(node);

        //平衡維護(hù)
        //LL
        // 左子樹(shù)比右子樹(shù)高度超過(guò)了1，說(shuō)明當(dāng)前節(jié)點(diǎn)的平衡被打破
        // 且新添加的節(jié)點(diǎn)是在左子樹(shù)的左子樹(shù)的左側(cè)
        if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0){
            //右旋轉(zhuǎn)
            return rightRotate(node);
        }

        //RR
        // 右子樹(shù)比左子樹(shù)高度超過(guò)了1，說(shuō)明當(dāng)前節(jié)點(diǎn)的平衡被打破
        // 且新添加的節(jié)點(diǎn)是在右子樹(shù)的右子樹(shù)的右側(cè)
        if(balanceFactor < -1 && getBalanceFactor(node.right) <= 0){
            //左旋轉(zhuǎn)
            return leftRotate(node);
        }

        //LR
        // 左子樹(shù)比右子樹(shù)高度超過(guò)了1，說(shuō)明當(dāng)前節(jié)點(diǎn)的平衡被打破
        // 且新添加的節(jié)點(diǎn)是在左子樹(shù)的左子樹(shù)的右側(cè)
        if(balanceFactor > 1 && getBalanceFactor(node.left) < 0){
            //先對(duì)node.left進(jìn)行左旋轉(zhuǎn)
            node.left = leftRotate(node.left);
            //然后對(duì)node進(jìn)行右旋轉(zhuǎn)
            return rightRotate(node);
        }

        //RL
        // 右子樹(shù)比左子樹(shù)高度超過(guò)了1，說(shuō)明當(dāng)前節(jié)點(diǎn)的平衡被打破
        // 且新添加的節(jié)點(diǎn)是在右子樹(shù)的右子樹(shù)的左側(cè)
        if(balanceFactor < -1 && getBalanceFactor(node.right) > 0){
            //先對(duì)node.right進(jìn)行右旋轉(zhuǎn)
            node.right = rightRotate(node.right);
            //然后對(duì)node進(jìn)行左旋轉(zhuǎn)
            return leftRotate(node);
        }

        //返回當(dāng)前根節(jié)點(diǎn)
        return node;
    }



    /**
     * 根據(jù)key從當(dāng)前以當(dāng)前node為根節(jié)點(diǎn)中尋找value, 不存在返回null
     * @param node
     * @param key
     * @return
     */
    private Node<K, V> getNode(Node<K, V> node, K key){
        //遞歸終止條件
        if(node == null){
            return null;
        }

        //待尋找key比當(dāng)前節(jié)點(diǎn)key小，遞歸調(diào)用node.left
        if(key.compareTo(node.key) < 0){
            return getNode(node.left, key);
        }else if(key.compareTo(node.key) > 0){
            //待尋找key比當(dāng)前節(jié)點(diǎn)key大，遞歸調(diào)用node.right
            return getNode(node.right, key);
        }else {
            //待尋找key和當(dāng)前節(jié)點(diǎn)key相等，直接返回
            return node;
        }
    }


    public boolean contains(K key) {
        return getNode(root, key) != null;
    }


    public void set(K key, V value) {
        Node<K, V> node = getNode(root, key);
        if(node == null){
            //不存在直接拋異常
            throw new IllegalArgumentException(key + " doesn't exist!");
        }

        //key已存在，則更新
        node.value = value;
    }

    public V get(K key) {
        Node<K, V> node = getNode(root, key);
        return node == null ? null : node.value;
    }

    /**
     * 返回以node為根的二分搜索樹(shù)的最小值所在的節(jié)點(diǎn)
     * @param node
     * @return
     */
    private Node<K, V> minimum(Node<K, V> node){
        if(node.left == null){
            return node;
        }
        return minimum(node.left);
    }

    /**
     * 從二分搜索樹(shù)中刪除元素鍵為key的節(jié)點(diǎn), 并返回value, 不存在返回null
     * @param key
     * @return
     */
    public V remove(K key){
       Node<K, V> node = getNode(root, key);
        if(node == null){
            //不存在直接返回null
            return null;
        }
        //存在
        root = remove(root, key);
        return node.value;
    }

    /**
     * 刪除以node為根的二分搜索樹(shù)中鍵為key的節(jié)點(diǎn)，遞歸遞歸方式
     * 返回刪除節(jié)點(diǎn)后新的二分搜索樹(shù)的根
     * @param node
     * @param key
     * @return
     */
    private Node<K, V> remove(Node<K, V> node, K key){
        //節(jié)點(diǎn)為空，直接返回
        if(node == null){
            return null;
        }

        //聲明要返回去的node
        Node<K, V> retNode;

        if(key.compareTo(node.key) < 0){
            //待刪除元素key小于當(dāng)前節(jié)點(diǎn)的鍵，向左遞歸尋找
            node.left = remove(node.left, key);
            retNode = node;
        }else if(key.compareTo(node.key) > 0){
            //待刪除元素key大于當(dāng)前節(jié)點(diǎn)的鍵，向右遞歸尋找
            node.right = remove(node.right, key);
            retNode = node;
        }else {
            //待刪除節(jié)點(diǎn)左子樹(shù)為空
            if(node.left == null){
                Node<K, V> rightNode = node.right;
                node.right = null;
                size --;
                retNode = rightNode;
            }

            //待刪除節(jié)點(diǎn)右子樹(shù)為空
            else if(node.right == null){
                Node<K, V> rightNode = node.left;
                node.left = null;
                size --;
                retNode = rightNode;
            }else {
                //待刪除節(jié)點(diǎn)左、右子樹(shù)不為空
                //找到比待刪除節(jié)點(diǎn)大的最小節(jié)點(diǎn)，即待刪除節(jié)點(diǎn)右子樹(shù)最小節(jié)點(diǎn)
                //用這個(gè)節(jié)點(diǎn)頂替待刪除節(jié)點(diǎn)的位置

                //找到比待刪除節(jié)點(diǎn)大的最小節(jié)點(diǎn)，即待刪除節(jié)點(diǎn)右子樹(shù)最小節(jié)點(diǎn)
                Node<K, V> successor = minimum(node.right);
                //刪除比待刪除節(jié)點(diǎn)大的最小節(jié)點(diǎn)，并將返回值給succeer的右孩子
                //successor.right = removeMin(node.right);
                successor.right = remove(node.right, successor.key);

                //node.left賦值給successor.left
                successor.left = node.left;
                //node節(jié)點(diǎn)和二分搜索樹(shù)脫離關(guān)系
                node.left = node.right = null;
                retNode = successor;
            }
        }

        if(retNode == null){
            //如果刪除了該節(jié)點(diǎn)，返回的二叉樹(shù)節(jié)點(diǎn)的根節(jié)點(diǎn)為空的話(huà)
            return null;
        }

        //更新節(jié)點(diǎn)的高度height
        retNode.height = Math.max(getHeight(retNode.left), getHeight(retNode.right)) + 1;

        //計(jì)算平衡因子
        int balanceFactor = getBalanceFactor(retNode);

        //平衡維護(hù)
        //LL
        // 左子樹(shù)比右子樹(shù)高度超過(guò)了1，說(shuō)明當(dāng)前節(jié)點(diǎn)的平衡被打破
        // 且新添加的節(jié)點(diǎn)是在左子樹(shù)的左子樹(shù)的左側(cè)
        if(balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0){
            //右旋轉(zhuǎn)
            return rightRotate(retNode);
        }

        //RR
        // 右子樹(shù)比左子樹(shù)高度超過(guò)了1，說(shuō)明當(dāng)前節(jié)點(diǎn)的平衡被打破
        // 且新添加的節(jié)點(diǎn)是在右子樹(shù)的右子樹(shù)的右側(cè)
        if(balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0){
            //左旋轉(zhuǎn)
            return leftRotate(retNode);
        }

        //LR
        // 左子樹(shù)比右子樹(shù)高度超過(guò)了1，說(shuō)明當(dāng)前節(jié)點(diǎn)的平衡被打破
        // 且新添加的節(jié)點(diǎn)是在左子樹(shù)的左子樹(shù)的右側(cè)
        if(balanceFactor > 1 && getBalanceFactor(retNode.left) < 0){
            //先對(duì)node.left進(jìn)行左旋轉(zhuǎn)
            retNode.left = leftRotate(retNode.left);
            //然后對(duì)node進(jìn)行右旋轉(zhuǎn)
            return rightRotate(retNode);
        }

        //RL
        // 右子樹(shù)比左子樹(shù)高度超過(guò)了1，說(shuō)明當(dāng)前節(jié)點(diǎn)的平衡被打破
        // 且新添加的節(jié)點(diǎn)是在右子樹(shù)的右子樹(shù)的左側(cè)
        if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0){
            //先對(duì)node.right進(jìn)行右旋轉(zhuǎn)
            retNode.right = rightRotate(retNode.right);
            //然后對(duì)node進(jìn)行左旋轉(zhuǎn)
            return leftRotate(retNode);
        }

        //如果刪除節(jié)點(diǎn)后，沒(méi)有打破平衡，直接返回當(dāng)前根節(jié)點(diǎn)
        return retNode;
    }
}

四、AVL樹(shù)實(shí)現(xiàn)映射(Map)

Map接口

public interface Map<K, V> {

    /**
     * 添加元素
     * @param key
     * @param value
     */
    void add(K key, V value);

    /**
     * 刪除元素，返回元素對(duì)應(yīng)的value
     * @param key
     * @return
     */
    V remove(K key);

    /**
     * 是否包含key
     * @param key
     * @return
     */
    boolean contains(K key);

    /**
     * 修改元素key對(duì)應(yīng)的value
     * @param key
     * @param value
     */
    void set(K key, V value);

    /**
     * 獲取key對(duì)應(yīng)的value
     * @param key
     * @return
     */
    V get(K key);

    /**
     * 映射的元素個(gè)數(shù)
     * @return
     */
    int getSize();

    /**
     * 映射是否為空
     * @return
     */
    boolean isEmpty();
}

AVLTreeMap實(shí)現(xiàn)

/**
 * @Author: huangyibo
 * @Date: 2022/2/27 0:47
 * @Description: AVLTreeMap 底層基于AVLTree
 */

public class AVLTreeMap<K extends Comparable<K>, V> implements Map<K, V> {

    private AVLTree<K,V> avlTree;

    public AVLTreeMap(){
        avlTree = new AVLTree<>();
    }

    @Override
    public void add(K key, V value) {
        avlTree.add(key,value);
    }

    @Override
    public V remove(K key) {
        return avlTree.remove(key);
    }

    @Override
    public boolean contains(K key) {
        return avlTree.contains(key);
    }

    @Override
    public void set(K key, V value) {
        avlTree.set(key, value);
    }

    @Override
    public V get(K key) {
        return avlTree.get(key);
    }

    @Override
    public int getSize() {
        return avlTree.getSize();
    }

    @Override
    public boolean isEmpty() {
        return avlTree.isEmpty();
    }
}

五、AVL樹(shù)實(shí)現(xiàn)集合(Set)

集合(Set)接口

public interface Set<E> {

    /**
     * 添加元素
     * @param e
     */
    void add(E e);

    /**
     * 刪除元素
     * @param e
     */
    void remove(E e);

    /**
     * 集合是否包含元素
     * @param e
     * @return
     */
    boolean contains(E e);

    /**
     * 集合的元素個(gè)數(shù)
     * @return
     */
    int getSize();

    /**
     * 集合是否為空
     * @return
     */
    boolean isEmpty();
}

AVLTreeSet實(shí)現(xiàn)

/**
 * @Author: huangyibo
 * @Date: 2022/2/27 0:52
 * @Description: AVLTreeSet 底層基于AVLTree
 */

public class AVLTreeSet<E extends Comparable<E>> implements Set<E> {

    private AVLTree<E, Object> avlTree;

    public AVLTreeSet(){
        avlTree = new AVLTree<>();
    }

    @Override
    public void add(E e) {
        avlTree.add(e, null);
    }

    @Override
    public void remove(E e) {
        avlTree.remove(e);
    }

    @Override
    public boolean contains(E e) {
        return avlTree.contains(e);
    }

    @Override
    public int getSize() {
        return avlTree.getSize();
    }

    @Override
    public boolean isEmpty() {
        return avlTree.isEmpty();
    }
}

參考：
https://chiclaim.blog.csdn.net/article/details/80740418

https://catwing.blog.csdn.net/article/details/89110319

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

數(shù)據(jù)結(jié)構(gòu)——AVL樹(shù)

數(shù)據(jù)結(jié)構(gòu)——AVL樹(shù)

一、平衡二叉樹(shù)

平衡因子

二、AVL樹(shù)

三、AVL樹(shù)代碼實(shí)現(xiàn)

3.1 基礎(chǔ)設(shè)計(jì)

3.2 添加節(jié)點(diǎn)

3.2.1 LL（右旋）

3.2.2 RR（左旋）

3.2.3 LR

3.2.4 RL

添加節(jié)點(diǎn)代碼

3.3 刪除節(jié)點(diǎn)

3.4 完整代碼

四、AVL樹(shù)實(shí)現(xiàn)映射(Map)

五、AVL樹(shù)實(shí)現(xiàn)集合(Set)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

數(shù)據(jù)結(jié)構(gòu)——AVL樹(shù)

一、平衡二叉樹(shù)

平衡因子

二、AVL樹(shù)

三、AVL樹(shù)代碼實(shí)現(xiàn)

3.1 基礎(chǔ)設(shè)計(jì)

3.2 添加節(jié)點(diǎn)

3.2.1 LL（右旋）

3.2.2 RR（左旋）

3.2.3 LR

3.2.4 RL

添加節(jié)點(diǎn)代碼

3.3 刪除節(jié)點(diǎn)

3.4 完整代碼

四、AVL樹(shù)實(shí)現(xiàn)映射(Map)

五、AVL樹(shù)實(shí)現(xiàn)集合(Set)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

一、平衡二叉樹(shù)

二、AVL樹(shù)

三、AVL樹(shù)代碼實(shí)現(xiàn)

四、AVL樹(shù)實(shí)現(xiàn)映射(Map)

五、AVL樹(shù)實(shí)現(xiàn)集合(Set)