欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

詳解Java數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹

 更新時間：2022年02月01日 08:14:39   作者：炒雞辣雞123  
平衡二叉樹（Balanced?Binary?Tree）又被稱為AVL樹（有別于AVL算法），且具有以下性質(zhì)：它是一?棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。本文將詳解介紹一下平衡二叉樹的原理與實(shí)現(xiàn)，需要的可以參考一下

什么是二叉搜索樹

簡單來說，就是方便搜索的二叉樹，是一種具備特定結(jié)構(gòu)的二叉樹，即，對于節(jié)點(diǎn)n，其左子樹的所有節(jié)點(diǎn)的值都小于等于其值，其右子樹的所有節(jié)點(diǎn)的值都大于等于其值。?

以序列2,4,1,3,5,10,9,8為例，如果以二叉搜索樹建樹的方式，我們建立出來的逐個步驟應(yīng)該為

第一步：

第二步：

第三步：

第四步：

第五步：

第六步：

第七步：

第八步：

按照不平衡的普通方法生成的二叉搜索樹就是這么一個樣子。其實(shí)現(xiàn)代碼如下：

package com.chaojilaji.book.searchtree;

import com.chaojilaji.auto.autocode.utils.Json;

import java.util.Objects;

public class SearchTreeUtils {

? ? public static SearchTree buildTree(SearchTree searchTree, Integer value) {
? ? ? ? if (value >= searchTree.getValue()) {
? ? ? ? ? ? if (Objects.isNull(searchTree.getRightChild())) {
? ? ? ? ? ? ? ? SearchTree searchTree1 = new SearchTree();
? ? ? ? ? ? ? ? searchTree1.setValue(value);
? ? ? ? ? ? ? ? searchTree.setRightChild(searchTree1);
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? buildTree(searchTree.getRightChild(), value);
? ? ? ? ? ? }
? ? ? ? } else {
? ? ? ? ? ? if (Objects.isNull(searchTree.getLeftChild())) {
? ? ? ? ? ? ? ? SearchTree searchTree1 = new SearchTree();
? ? ? ? ? ? ? ? searchTree1.setValue(value);
? ? ? ? ? ? ? ? searchTree.setLeftChild(searchTree1);
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? buildTree(searchTree.getLeftChild(), value);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return searchTree;
? ? }

? ? public static void main(String[] args) {
? ? ? ? int[] a = new int[]{2, 4, 1, 3, 5, 10, 9, 8};
? ? ? ? SearchTree searchTree = new SearchTree();
? ? ? ? searchTree.setValue(a[0]);
? ? ? ? for (int i = 1; i < a.length; i++) {
? ? ? ? ? ? searchTree = buildTree(searchTree,a[i]);
? ? ? ? }
? ? ? ? System.out.println(Json.toJson(searchTree));
? ? }
}

運(yùn)行的結(jié)果如下：

{
    "value": 2,
    "left_child": {
        "value": 1,
        "left_child": null,
        "right_child": null
    },
    "right_child": {
        "value": 4,
        "left_child": {
            "value": 3,
            "left_child": null,
            "right_child": null
        },
        "right_child": {
            "value": 5,
            "left_child": null,
            "right_child": {
                "value": 10,
                "left_child": {
                    "value": 9,
                    "left_child": {
                        "value": 8,
                        "left_child": null,
                        "right_child": null
                    },
                    "right_child": null
                },
                "right_child": null
            }
        }
    }
}

與我們的目標(biāo)結(jié)果是一致的。

好了，那我們本節(jié)就完畢了?？墒寝D(zhuǎn)過頭可能你也發(fā)現(xiàn)了，直接生成的這個二叉搜索樹似乎有點(diǎn)太長了，層數(shù)有點(diǎn)太多了，一般來說，一個長度為8的序列，四層結(jié)構(gòu)的二叉樹就可以表現(xiàn)出來了，這里卻使用了六層，顯然這樣的結(jié)果不盡人意，同時太深的層數(shù)，也增加了查找的時間復(fù)雜度。

這就給我們的樹提了要求，我們需要將目前構(gòu)造出來的樹平衡一下，讓這棵二叉搜索樹的左右子樹“重量”最好差不多。

平衡二叉搜索樹

首先需要掌握兩個概念

  • 平衡因子
  • 旋轉(zhuǎn)

平衡因子就是對于這棵二叉搜索樹的每個節(jié)點(diǎn)來說，其左子樹的高度減去右子樹的高度即為該節(jié)點(diǎn)的平衡因子，該數(shù)值能很快的辨別出該節(jié)點(diǎn)究竟是左子樹高還是右子樹高。在平衡二叉樹中規(guī)定，當(dāng)一個節(jié)點(diǎn)的平衡因子的絕對值大于等于2的時候，我們就認(rèn)為該節(jié)點(diǎn)不平衡，需要進(jìn)行調(diào)整。那么這種調(diào)整的手段稱之為節(jié)點(diǎn)與節(jié)點(diǎn)的旋轉(zhuǎn)，通俗來說，旋轉(zhuǎn)就是指的節(jié)點(diǎn)間的指向關(guān)系發(fā)生變化，在c語言中就是指針指向的切換。

在調(diào)用旋轉(zhuǎn)之前，我們需要判斷整棵樹是否平衡，即，這棵二叉搜索樹的所有平衡因子是否有絕對值大于等于2的，如果有，就找出最小的一棵子樹?？梢源_定的是，如果前一次二叉搜索樹是平衡的，那么此時如果加一個節(jié)點(diǎn)進(jìn)去，造成不平衡，那么節(jié)點(diǎn)從葉子開始回溯，找到的第一個大于等于2的節(jié)點(diǎn)勢必為最小不平衡子樹的根節(jié)點(diǎn)。

對于這棵最小不平衡的子樹，我們需要得到兩個值，即根節(jié)點(diǎn)的平衡因子a，以及左右子樹根節(jié)點(diǎn)中平衡因子絕對值較大者的平衡因子b。
我們可以將需要旋轉(zhuǎn)的類型抽象為以下四種：?

1.左左型（正正型，即 a>0 && b>0）

左左型最后想要達(dá)到的目標(biāo)是第二個節(jié)點(diǎn)成為根節(jié)點(diǎn)，第一個節(jié)點(diǎn)成為第二個節(jié)點(diǎn)的右節(jié)點(diǎn)。

所以用偽代碼展示就是（設(shè)a1，a2，a3分別為圖里面從上到下的三個節(jié)點(diǎn)）

a2的右子樹 = (合并(a2的右子樹,a1的右子樹) + a1頂點(diǎn)值) 一起構(gòu)成的二叉搜索樹;

返回 a2 

2.左右型（正負(fù)型，即 a>0 && b<0）

設(shè)a1，a2，a3分別為圖里面從上到下的三個節(jié)點(diǎn)

首先應(yīng)該通過將a3和a2調(diào)換上下位置，使之變成左左型，然后再調(diào)用左左型的方法就完成了。

從左右型調(diào)換成左左型，即將a2及其左子樹成為a3左子樹的一部分，然后將a1的左子樹置為a3即可。

偽代碼如下：

a3的左子樹 = a2及其左子樹與a3的左子樹合并成的一棵二叉搜索樹;

a1的左子樹 = a3;

3.右右型（負(fù)負(fù)型，即 a<0 && b<0）

設(shè)a1，a2，a3分別為圖里面從上到下的三個節(jié)點(diǎn)

右右型與左左型類似，要達(dá)到的目的就是a1成為a2左子樹的一部分，偽代碼為：

a2的左子樹 = （合并a2的左子樹和a1的左子樹）+ a1頂點(diǎn)的值構(gòu)成的二叉搜索樹;

返回a2

4.右左型（負(fù)正型，即 a<0 && b>0）

設(shè)a1，a2，a3分別為圖里面從上到下的三個節(jié)點(diǎn)

右左型需要先轉(zhuǎn)換成右右型，然后在調(diào)用右右型的方法即可。

從右左型到右右型，即需要將a2及其右子樹成為a3右子樹的一部分，然后將a1的右子樹置為a3即可。

偽代碼如下：

a3的右子樹 = a2及其右子樹與a3的右子樹合并成的一棵二叉搜索樹;

a1的右子樹 = a3;

從上面的分析可以得出，我們不僅僅需要實(shí)現(xiàn)旋轉(zhuǎn)的方法，還需要實(shí)現(xiàn)合并二叉樹等方法，這些方法都是基礎(chǔ)方法，讀者需要確保會快速寫出來。

請讀者朋友們根據(jù)上面的內(nèi)容，先嘗試寫出集中平衡化的方法。

平衡二叉搜索樹建樹程序

平衡二叉搜索樹建樹，需要在二叉搜索樹建樹的基礎(chǔ)上加上平衡的過程，即子樹之間指針轉(zhuǎn)換的問題，同時，由于這種指針轉(zhuǎn)換引起的子樹的子樹也會產(chǎn)生不平衡，所以上面提到的四種旋轉(zhuǎn)調(diào)整方式都是遞歸的。

首先，先構(gòu)建節(jié)點(diǎn)基礎(chǔ)結(jié)構(gòu)：

public class SearchTree {

? ? private Integer value;

? ? private SearchTree leftChild;
? ? private SearchTree rightChild;
? ? private Integer balanceNumber = 0;
? ? private Integer height = 0;
}

值，高度，平衡因子，左子樹，右子樹

計算每個節(jié)點(diǎn)的高度

這是計算二叉搜索樹中每個平衡因子的基礎(chǔ)，我們設(shè)最低層為高度1，則計算節(jié)點(diǎn)高度的代碼為：

public static Integer countHeight(SearchTree searchTree) {
    if (Objects.isNull(searchTree)) {
        return 0;
    }
    searchTree.setHeight(Math.max(countHeight(searchTree.getLeftChild()),
                                  countHeight(searchTree.getRightChild())) + 1);
    return searchTree.getHeight();
}

這里有個半動態(tài)規(guī)劃的結(jié)論：當(dāng)前節(jié)點(diǎn)的高度，等于左右子樹的最大高度+1；這里的寫法有點(diǎn)樹形DP的味道。

計算每個節(jié)點(diǎn)的平衡因子

public static void countBalanceNumber(SearchTree searchTree, MaxNumber max, SearchTree fatherTree, Integer type) {
? ? if (Objects.nonNull(searchTree.getValue())) {
? ? ? ? if (Objects.isNull(searchTree.getLeftChild())?
? ? ? ? ? ? && Objects.nonNull(searchTree.getRightChild())) {
? ? ? ? ? ? searchTree.setBalanceNumber(-searchTree.getRightChild().getHeight());
? ? ? ? }
? ? ? ? if (Objects.nonNull(searchTree.getLeftChild())?
? ? ? ? ? ? && Objects.isNull(searchTree.getRightChild())) {
? ? ? ? ? ? searchTree.setBalanceNumber(searchTree.getLeftChild().getHeight());
? ? ? ? }
? ? ? ? if (Objects.isNull(searchTree.getLeftChild())?
? ? ? ? ? ? && Objects.isNull(searchTree.getRightChild())) {
? ? ? ? ? ? searchTree.setBalanceNumber(0);
? ? ? ? }
? ? ? ? if (Objects.nonNull(searchTree.getLeftChild())?
? ? ? ? ? ? && Objects.nonNull(searchTree.getRightChild())) {
? ? ? ? ? ? searchTree.setBalanceNumber(searchTree.getLeftChild().getHeight()?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? - searchTree.getRightChild().getHeight());
? ? ? ? }
? ? }

? ? if (Objects.nonNull(searchTree.getLeftChild())) {
? ? ? ? countBalanceNumber(searchTree.getLeftChild(), max, searchTree, 1);
? ? }
? ? if (Objects.nonNull(searchTree.getRightChild())) {
? ? ? ? countBalanceNumber(searchTree.getRightChild(), max, searchTree, 2);
? ? }

}

本質(zhì)上講，平衡因子就是左子樹高度減去右子樹高度，注意這里左右子樹都有可能不存在，所以加入了一堆特判。

判斷當(dāng)前二叉樹是否平衡

static class MaxNumber {
? ? public Integer max;
? ? public SearchTree childTree;
? ? public SearchTree fatherTree;
? ? public Integer flag = 0; // 0 代表自己就是根,1代表childTree是左子樹，2代表childTree是右子樹
}

public static MaxNumber checkBalance(SearchTree searchTree) {
? ? MaxNumber max = new MaxNumber();
? ? max.max = 0;
? ? countBalanceNumber(searchTree, max, null, 0);
? ? return max;
}

public static void countBalanceNumber(SearchTree searchTree, MaxNumber max, SearchTree fatherTree, Integer type) {
? ? if (Objects.nonNull(searchTree.getValue())) {
? ? ? ? if (Objects.isNull(searchTree.getLeftChild())?
? ? ? ? ? ? && Objects.nonNull(searchTree.getRightChild())) {
? ? ? ? ? ? searchTree.setBalanceNumber(-searchTree.getRightChild().getHeight());
? ? ? ? }
? ? ? ? if (Objects.nonNull(searchTree.getLeftChild())?
? ? ? ? ? ? && Objects.isNull(searchTree.getRightChild())) {
? ? ? ? ? ? searchTree.setBalanceNumber(searchTree.getLeftChild().getHeight());
? ? ? ? }
? ? ? ? if (Objects.isNull(searchTree.getLeftChild())?
? ? ? ? ? ? && Objects.isNull(searchTree.getRightChild())) {
? ? ? ? ? ? searchTree.setBalanceNumber(0);
? ? ? ? }
? ? ? ? if (Objects.nonNull(searchTree.getLeftChild())?
? ? ? ? ? ? && Objects.nonNull(searchTree.getRightChild())) {
? ? ? ? ? ? searchTree.setBalanceNumber(searchTree.getLeftChild().getHeight()?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? - searchTree.getRightChild().getHeight());
? ? ? ? }
? ? }


? ? if (Objects.nonNull(searchTree.getLeftChild())) {
? ? ? ? countBalanceNumber(searchTree.getLeftChild(), max, searchTree, 1);
? ? }
? ? if (Objects.nonNull(searchTree.getRightChild())) {
? ? ? ? countBalanceNumber(searchTree.getRightChild(), max, searchTree, 2);
? ? }
? ? if (Math.abs(searchTree.getBalanceNumber()) >= Math.abs(max.max)) {
? ? ? ? if (Math.abs(searchTree.getBalanceNumber()) == Math.abs(max.max)?
? ? ? ? ? ? && max.childTree == null) {
? ? ? ? ? ? max.childTree = searchTree;
? ? ? ? ? ? max.fatherTree = fatherTree;
? ? ? ? ? ? max.flag = type;
? ? ? ? ? ? max.max = searchTree.getBalanceNumber();
? ? ? ? }
? ? ? ? if (Math.abs(searchTree.getBalanceNumber()) > Math.abs(max.max)) {
? ? ? ? ? ? max.childTree = searchTree;
? ? ? ? ? ? max.fatherTree = fatherTree;
? ? ? ? ? ? max.flag = type;
? ? ? ? ? ? max.max = searchTree.getBalanceNumber();
? ? ? ? }
? ? }
}

其中，MaxNumber類是為了保存第一棵不平衡的子樹而存在的結(jié)構(gòu)，為了使這棵子樹平衡之后能重新回到整棵樹中，需要在MaxNumber中存儲當(dāng)前子樹父節(jié)點(diǎn)，同時標(biāo)明當(dāng)前子樹是父節(jié)點(diǎn)的左子樹還是右子樹，還是本身。

合并二叉樹

public static void getAllValue(SearchTree tree, Set<Integer> sets) {
? ? if (Objects.isNull(tree)) return;
? ? if (Objects.nonNull(tree.getValue())) {
? ? ? ? sets.add(tree.getValue());
? ? }
? ? if (Objects.nonNull(tree.getLeftChild())) {
? ? ? ? getAllValue(tree.getLeftChild(), sets);
? ? }
? ? if (Objects.nonNull(tree.getRightChild())) {
? ? ? ? getAllValue(tree.getRightChild(), sets);
? ? }
}

/**
? ? ?* 合并兩棵二叉搜索樹
? ? ?*
? ? ?* @param a
? ? ?* @param b
? ? ?* @return
? ? ?*/
public static SearchTree mergeTree(SearchTree a, SearchTree b) {
? ? Set<Integer> vals = new HashSet<>();
? ? getAllValue(b, vals);
? ? for (Integer c : vals) {
? ? ? ? a = buildTree(a, c);
? ? }
? ? return a;
}

將一棵樹轉(zhuǎn)成數(shù)字集合，然后通過建樹的方式建到另外一棵樹上即可。

旋轉(zhuǎn)調(diào)整函數(shù)

1.左左型旋轉(zhuǎn)
/**
     * 左左
     *
     * @param searchTree
     * @return
     */
public static SearchTree leftRotate1(SearchTree father, SearchTree searchTree) {
    SearchTree b = father;
    SearchTree newRight = mergeTree(father.getRightChild(), searchTree.getRightChild());
    newRight = buildTree(newRight, b.getValue());
    countHeight(newRight);
    while (Math.abs(checkBalance(newRight).childTree.getBalanceNumber()) >= 2) {
        newRight = rotate(checkBalance(newRight).childTree);
        countHeight(newRight);
    }
    searchTree.setRightChild(newRight);
    return searchTree;
}

2.右右型旋轉(zhuǎn)

/**
     * 右右
     * @param father
     * @param searchTree
     * @return
     */
public static SearchTree rightRotate1(SearchTree father, SearchTree searchTree) {
    SearchTree b = father;
    SearchTree newLeft = mergeTree(father.getLeftChild(), searchTree.getLeftChild());
    newLeft = buildTree(newLeft, b.getValue());
    countHeight(newLeft);
    while (Math.abs(checkBalance(newLeft).childTree.getBalanceNumber()) >= 2) {
        newLeft = rotate(checkBalance(newLeft).childTree);
        countHeight(newLeft);
    }
    searchTree.setLeftChild(newLeft);
    return searchTree;
}

3.左右型旋轉(zhuǎn)

/**
     * 左右
     *
     * @param searchTree
     * @return
     */
public static SearchTree rightRotate2(SearchTree father, SearchTree searchTree) {
    SearchTree a1 = father;
    SearchTree a2 = searchTree;
    SearchTree a3 = searchTree.getRightChild();
    SearchTree newLeft = mergeTree(a2.getLeftChild(), a3.getLeftChild());
    newLeft = buildTree(newLeft, a2.getValue());
    countHeight(newLeft);
    while (Math.abs(checkBalance(newLeft).childTree.getBalanceNumber()) >= 2) {
        newLeft = rotate(checkBalance(newLeft).childTree);
        countHeight(newLeft);
    }
    a3.setLeftChild(newLeft);
    a1.setLeftChild(a3);
    return a1;
}

4.右左型旋轉(zhuǎn)

/**
     * 右左
     *
     * @param searchTree
     * @return
     */
public static SearchTree leftRotate2(SearchTree father, SearchTree searchTree) {
    SearchTree a1 = father;
    SearchTree a2 = searchTree;
    SearchTree a3 = searchTree.getLeftChild();
    SearchTree newRight = mergeTree(a2.getRightChild(), a3.getRightChild());
    newRight = buildTree(newRight, a2.getValue());
    countHeight(newRight);
    while (Math.abs(checkBalance(newRight).childTree.getBalanceNumber()) >= 2) {
        newRight = rotate(checkBalance(newRight).childTree);
        countHeight(newRight);
    }
    a3.setRightChild(newRight);
    a1.setRightChild(a3);
    return a1;
}

旋轉(zhuǎn)調(diào)用函數(shù)：

public static SearchTree rotate(SearchTree searchTree) {
    int a = searchTree.getBalanceNumber();
    if (Math.abs(a) < 2) {
        return searchTree;
    }
    int b = Objects.isNull(searchTree.getLeftChild()) ? 0 
        : searchTree.getLeftChild().getBalanceNumber();
    int c = Objects.isNull(searchTree.getRightChild()) ? 0 
        : searchTree.getRightChild().getBalanceNumber();
    if (a > 0) {
        if (b > 0) {
            // TODO: 2022/1/13 左左
            searchTree = leftRotate1(searchTree, searchTree.getLeftChild());
        } else {
            // TODO: 2022/1/13 左右
            searchTree = rightRotate2(searchTree, searchTree.getLeftChild());
            searchTree = leftRotate1(searchTree, searchTree.getLeftChild());
        }
    } else {
        if (c > 0) {
            // TODO: 2022/1/13 右左
            searchTree = leftRotate2(searchTree, searchTree.getRightChild());
            searchTree = rightRotate1(searchTree, searchTree.getRightChild());
        } else {
            // TODO: 2022/1/13 右右
            searchTree = rightRotate1(searchTree, searchTree.getRightChild());
        }
    }
    return searchTree;
}

整體代碼

package com.chaojilaji.book.searchtree;

import com.chaojilaji.auto.autocode.utils.Json;
import com.chaojilaji.book.tree.Handle;
import com.chaojilaji.book.tree.Tree;
import org.omg.CORBA.OBJ_ADAPTER;

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

public class SearchTreeUtils {


    static class MaxNumber {
        public Integer max;
        public SearchTree childTree;
        public SearchTree fatherTree;
        public Integer flag = 0; // 0 代表自己就是根,1代表childTree是左子樹，2代表childTree是右子樹
    }

    public static SearchTree rotate(SearchTree searchTree) {
        int a = searchTree.getBalanceNumber();
        if (Math.abs(a) < 2) {
            return searchTree;
        }
        int b = Objects.isNull(searchTree.getLeftChild()) ? 0 : searchTree.getLeftChild().getBalanceNumber();
        int c = Objects.isNull(searchTree.getRightChild()) ? 0 : searchTree.getRightChild().getBalanceNumber();
        if (a > 0) {
            if (b > 0) {
                // TODO: 2022/1/13 左左
                searchTree = leftRotate1(searchTree, searchTree.getLeftChild());
            } else {
                // TODO: 2022/1/13 左右
                searchTree = rightRotate2(searchTree, searchTree.getLeftChild());
                searchTree = leftRotate1(searchTree, searchTree.getLeftChild());
            }
        } else {
            if (c > 0) {
                // TODO: 2022/1/13 右左
                searchTree = leftRotate2(searchTree, searchTree.getRightChild());
                searchTree = rightRotate1(searchTree, searchTree.getRightChild());
            } else {
                // TODO: 2022/1/13 右右
                searchTree = rightRotate1(searchTree, searchTree.getRightChild());
            }
        }
        return searchTree;
    }

    public static void getAllValue(SearchTree tree, Set<Integer> sets) {
        if (Objects.isNull(tree)) return;
        if (Objects.nonNull(tree.getValue())) {
            sets.add(tree.getValue());
        }
        if (Objects.nonNull(tree.getLeftChild())) {
            getAllValue(tree.getLeftChild(), sets);
        }
        if (Objects.nonNull(tree.getRightChild())) {
            getAllValue(tree.getRightChild(), sets);
        }
    }

    /**
     * 合并兩棵二叉搜索樹
     *
     * @param a
     * @param b
     * @return
     */
    public static SearchTree mergeTree(SearchTree a, SearchTree b) {
        Set<Integer> vals = new HashSet<>();
        getAllValue(b, vals);
        for (Integer c : vals) {
            a = buildTree(a, c);
        }
        return a;
    }

    /**
     * 左左
     *
     * @param searchTree
     * @return
     */
    public static SearchTree leftRotate1(SearchTree father, SearchTree searchTree) {
        SearchTree b = father;
        SearchTree newRight = mergeTree(father.getRightChild(), searchTree.getRightChild());
        newRight = buildTree(newRight, b.getValue());
        countHeight(newRight);
        while (Math.abs(checkBalance(newRight).childTree.getBalanceNumber()) >= 2) {
            newRight = rotate(checkBalance(newRight).childTree);
            countHeight(newRight);
        }
        searchTree.setRightChild(newRight);
        return searchTree;
    }

    /**
     * 右左
     *
     * @param searchTree
     * @return
     */
    public static SearchTree leftRotate2(SearchTree father, SearchTree searchTree) {
        SearchTree a1 = father;
        SearchTree a2 = searchTree;
        SearchTree a3 = searchTree.getLeftChild();
        SearchTree newRight = mergeTree(a2.getRightChild(), a3.getRightChild());
        newRight = buildTree(newRight, a2.getValue());
        countHeight(newRight);
        while (Math.abs(checkBalance(newRight).childTree.getBalanceNumber()) >= 2) {
            newRight = rotate(checkBalance(newRight).childTree);
            countHeight(newRight);
//            System.out.println(Json.toJson(newRight));
        }
        a3.setRightChild(newRight);
        a1.setRightChild(a3);
        return a1;
    }

    /**
     * 右右
     * @param father
     * @param searchTree
     * @return
     */
    public static SearchTree rightRotate1(SearchTree father, SearchTree searchTree) {
        SearchTree b = father;
        SearchTree newLeft = mergeTree(father.getLeftChild(), searchTree.getLeftChild());
        newLeft = buildTree(newLeft, b.getValue());
        countHeight(newLeft);
//         TODO: 2022/1/13 合并后的也有可能有問題
        while (Math.abs(checkBalance(newLeft).childTree.getBalanceNumber()) >= 2) {
            newLeft = rotate(checkBalance(newLeft).childTree);
            countHeight(newLeft);
//            System.out.println(Json.toJson(newLeft));
        }
        searchTree.setLeftChild(newLeft);
        return searchTree;
    }

    /**
     * 左右
     *
     * @param searchTree
     * @return
     */
    public static SearchTree rightRotate2(SearchTree father, SearchTree searchTree) {
        SearchTree a1 = father;
        SearchTree a2 = searchTree;
        SearchTree a3 = searchTree.getRightChild();
        SearchTree newLeft = mergeTree(a2.getLeftChild(), a3.getLeftChild());
        newLeft = buildTree(newLeft, a2.getValue());
        countHeight(newLeft);
        while (Math.abs(checkBalance(newLeft).childTree.getBalanceNumber()) >= 2) {
            newLeft = rotate(checkBalance(newLeft).childTree);
            countHeight(newLeft);
        }
        a3.setLeftChild(newLeft);
        a1.setLeftChild(a3);
        return a1;
    }

    public static MaxNumber checkBalance(SearchTree searchTree) {
        MaxNumber max = new MaxNumber();
        max.max = 0;
        countBalanceNumber(searchTree, max, null, 0);
        return max;
    }


    public static Integer countHeight(SearchTree searchTree) {
        if (Objects.isNull(searchTree)) {
            return 0;
        }
        searchTree.setHeight(Math.max(countHeight(searchTree.getLeftChild()), countHeight(searchTree.getRightChild())) + 1);
        return searchTree.getHeight();
    }


    public static void countBalanceNumber(SearchTree searchTree, MaxNumber max, SearchTree fatherTree, Integer type) {
        if (Objects.nonNull(searchTree.getValue())) {
            if (Objects.isNull(searchTree.getLeftChild()) && Objects.nonNull(searchTree.getRightChild())) {
                searchTree.setBalanceNumber(-searchTree.getRightChild().getHeight());
            }
            if (Objects.nonNull(searchTree.getLeftChild()) && Objects.isNull(searchTree.getRightChild())) {
                searchTree.setBalanceNumber(searchTree.getLeftChild().getHeight());
            }
            if (Objects.isNull(searchTree.getLeftChild()) && Objects.isNull(searchTree.getRightChild())) {
                searchTree.setBalanceNumber(0);
            }
            if (Objects.nonNull(searchTree.getLeftChild()) && Objects.nonNull(searchTree.getRightChild())) {
                searchTree.setBalanceNumber(searchTree.getLeftChild().getHeight() - searchTree.getRightChild().getHeight());
            }
        }


        if (Objects.nonNull(searchTree.getLeftChild())) {
            countBalanceNumber(searchTree.getLeftChild(), max, searchTree, 1);
        }
        if (Objects.nonNull(searchTree.getRightChild())) {
            countBalanceNumber(searchTree.getRightChild(), max, searchTree, 2);
        }
        if (Math.abs(searchTree.getBalanceNumber()) >= Math.abs(max.max)) {
            if (Math.abs(searchTree.getBalanceNumber()) == Math.abs(max.max) && max.childTree == null) {
                max.childTree = searchTree;
                max.fatherTree = fatherTree;
                max.flag = type;
                max.max = searchTree.getBalanceNumber();
            }
            if (Math.abs(searchTree.getBalanceNumber()) > Math.abs(max.max)) {
                max.childTree = searchTree;
                max.fatherTree = fatherTree;
                max.flag = type;
                max.max = searchTree.getBalanceNumber();
            }
        }
    }

    public static SearchTree buildTree(SearchTree searchTree, Integer value) {
        if (Objects.isNull(searchTree)) {
            searchTree = new SearchTree();
        }
        if (Objects.isNull(searchTree.getValue())) {
            searchTree.setValue(value);
            return searchTree;
        }
        if (value >= searchTree.getValue()) {
            if (Objects.isNull(searchTree.getRightChild())) {
                SearchTree searchTree1 = new SearchTree();
                searchTree1.setValue(value);
                searchTree.setRightChild(searchTree1);
            } else {
                buildTree(searchTree.getRightChild(), value);
            }
        } else {
            if (Objects.isNull(searchTree.getLeftChild())) {
                SearchTree searchTree1 = new SearchTree();
                searchTree1.setValue(value);
                searchTree.setLeftChild(searchTree1);
            } else {
                buildTree(searchTree.getLeftChild(), value);
            }
        }
        return searchTree;
    }

    public static void main(String[] args) {
//        int[] a = new int[]{2, 4, 1, 3, 5, 10, 9, 8};
        int[] a = new int[]{2, 4, 1, 3, 5, 10, 9, 8, 6, 7};
        SearchTree searchTree = new SearchTree();
        for (int i = 0; i < a.length; i++) {
            searchTree = buildTree(searchTree, a[i]);
            countHeight(searchTree);
            MaxNumber maxNumber = checkBalance(searchTree);
            SearchTree searchTree1 = maxNumber.childTree;
            if (Math.abs(searchTree1.getBalanceNumber()) >= 2) {
                searchTree1 = rotate(searchTree1);
                if (maxNumber.flag == 0) {
                    maxNumber.fatherTree = searchTree1;
                    searchTree = searchTree1;
                } else if (maxNumber.flag == 1) {
                    maxNumber.fatherTree.setLeftChild(searchTree1);
                } else if (maxNumber.flag == 2) {
                    maxNumber.fatherTree.setRightChild(searchTree1);
                }
                countHeight(searchTree);
            }

        }
        System.out.println("最終為\n" + Json.toJson(searchTree));
    }
}

以序列2, 4, 1, 3, 5, 10, 9, 8, 6, 7為例，構(gòu)造的平衡二叉搜索樹結(jié)構(gòu)為

{
    "value": 4,
    "left_child": {
        "value": 2,
        "left_child": {
            "value": 1,
            "left_child": null,
            "right_child": null,
            "balance_number": 0,
            "height": 1
        },
        "right_child": {
            "value": 3,
            "left_child": null,
            "right_child": null,
            "balance_number": 0,
            "height": 1
        },
        "balance_number": 0,
        "height": 2
    },
    "right_child": {
        "value": 8,
        "left_child": {
            "value": 6,
            "left_child": {
                "value": 5,
                "left_child": null,
                "right_child": null,
                "balance_number": 0,
                "height": 1
            },
            "right_child": {
                "value": 7,
                "left_child": null,
                "right_child": null,
                "balance_number": 0,
                "height": 1
            },
            "balance_number": 0,
            "height": 2
        },
        "right_child": {
            "value": 10,
            "left_child": {
                "value": 9,
                "left_child": null,
                "right_child": null,
                "balance_number": 0,
                "height": 1
            },
            "right_child": null,
            "balance_number": 1,
            "height": 2
        },
        "balance_number": 0,
        "height": 3
    },
    "balance_number": -1,
    "height": 4
}

以上就是詳解Java數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹的詳細(xì)內(nèi)容，更多關(guān)于Java平衡二叉樹的資料請關(guān)注腳本之家其它相關(guān)文章！

相關(guān)文章

  • Java面向接口編程之命令模式實(shí)例詳解

    Java面向接口編程之命令模式實(shí)例詳解

    這篇文章主要介紹了Java面向接口編程之命令模式,結(jié)合實(shí)例形式詳細(xì)分析了Java面向接口編程命令模式的定義、使用方法及相關(guān)操作注意事項,需要的朋友可以參考下
    2019-09-09
  • spring框架集成flyway項目的詳細(xì)過程

    spring框架集成flyway項目的詳細(xì)過程

    今天通過本文給大家分享spring框架集成flyway項目的詳細(xì)過程，由于大多數(shù)都是springboot集成flyway，很少見到spring框架的項目，今天就抽空給大家介紹下spring框架集成flyway項目的方法，一起看看吧
    2021-07-07
  • Java中的CopyOnWriteArrayList容器解析

    Java中的CopyOnWriteArrayList容器解析

    這篇文章主要介紹了Java中的CopyOnWriteArrayList容器解析,CopyOnWriteArrayList容器允許并發(fā)讀，讀操作是無鎖的，性能較高。至于寫操作，比如向容器中添加一個元素，則首先將當(dāng)前容器復(fù)制一份，然后在新副本上執(zhí)行寫操作,需要的朋友可以參考下
    2023-12-12
  • Java?實(shí)現(xiàn)使用Comparable按照我們指定的規(guī)則排序

    Java?實(shí)現(xiàn)使用Comparable按照我們指定的規(guī)則排序

    這篇文章主要介紹了Java?如何使用Comparable按照我們指定的規(guī)則排序，通過練習(xí)創(chuàng)建TreeSet集合使用無參構(gòu)造方法，并按照年齡從小到大的順序排序，若年齡相同再按照姓名的字母順序排序展開內(nèi)容,需要的朋友可以參考一下
    2022-04-04
  • Vue中computed計算屬性和data數(shù)據(jù)獲取方式

    Vue中computed計算屬性和data數(shù)據(jù)獲取方式

    這篇文章主要介紹了Vue中computed計算屬性和data數(shù)據(jù)獲取方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
    2022-03-03
  • SpringAop日志找不到方法的處理

    SpringAop日志找不到方法的處理

    這篇文章主要介紹了SpringAop日志找不到方法的處理方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
    2021-06-06
  • java開發(fā)建造者模式驗證實(shí)例詳解

    java開發(fā)建造者模式驗證實(shí)例詳解

    這篇文章主要為大家介紹了java開發(fā)中建造者模式的驗證實(shí)例詳解，文中附含詳細(xì)示例代碼，有需要的朋友可以借鑒參考下，希望能夠有所幫助
    2021-10-10
  • Java內(nèi)部類深入解析

    Java內(nèi)部類深入解析

    這篇文章主要介紹了Java內(nèi)部類深入解析,在java中,我們被允許在編寫一個類(外部類OuterClass)時,在其內(nèi)部再嵌套一個類(嵌套類NestedClass),java將嵌套類分為兩種,非靜態(tài)內(nèi)部類(簡稱內(nèi)部類)和 靜態(tài)內(nèi)部,需要的朋友可以參考下
    2023-12-12
  • JVM實(shí)戰(zhàn)系列之CPU100%和內(nèi)存100%排查

    JVM實(shí)戰(zhàn)系列之CPU100%和內(nèi)存100%排查

    本文主要介紹了JVM實(shí)戰(zhàn)系列之CPU100%和內(nèi)存100%排查，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-06-06
  • win10 java（jdk安裝）環(huán)境變量配置和相關(guān)問題

    win10 java（jdk安裝）環(huán)境變量配置和相關(guān)問題

    這篇文章主要介紹了win10java（jdk安裝）環(huán)境變量配置和相關(guān)問題解決,非常不錯，具有一定的參考借鑒價值，需要的朋友可以參考下
    2019-12-12

最新評論