java集合之TreeMap源碼的示例分析

這篇文章主要為大家展示了“java集合之TreeMap源碼的示例分析”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“java集合之TreeMap源碼的示例分析”這篇文章吧。

十年的禮縣網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。成都全網(wǎng)營(yíng)銷的優(yōu)勢(shì)是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整禮縣建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。成都創(chuàng)新互聯(lián)公司從事“禮縣網(wǎng)站設(shè)計(jì)”,“禮縣網(wǎng)站推廣”以來，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。

二叉樹的遍歷

我們知道二叉查找樹的遍歷有前序遍歷、中序遍歷、后序遍歷。

（1）前序遍歷，先遍歷我，再遍歷我的左子節(jié)點(diǎn)，最后遍歷我的右子節(jié)點(diǎn)；

（2）中序遍歷，先遍歷我的左子節(jié)點(diǎn)，再遍歷我，最后遍歷我的右子節(jié)點(diǎn)；

（3）后序遍歷，先遍歷我的左子節(jié)點(diǎn)，再遍歷我的右子節(jié)點(diǎn)，最后遍歷我；

這里的前中后都是以“我”的順序?yàn)闇?zhǔn)的，我在前就是前序遍歷，我在中就是中序遍歷，我在后就是后序遍歷。

下面讓我們看看經(jīng)典的中序遍歷是怎么實(shí)現(xiàn)的：

public class TreeMapTest {

    public static void main(String[] args) {
        // 構(gòu)建一顆10個(gè)元素的樹
        TreeNode<Integer> node = new TreeNode<>(1, null).insert(2)
                .insert(6).insert(3).insert(5).insert(9)
                .insert(7).insert(8).insert(4).insert(10);

        // 中序遍歷，打印結(jié)果為1到10的順序
        node.root().inOrderTraverse();
    }
}

/**
 * 樹節(jié)點(diǎn)，假設(shè)不存在重復(fù)元素
 * @param <T>
 */
class TreeNode<T extends Comparable<T>> {
    T value;
    TreeNode<T> parent;
    TreeNode<T> left, right;

    public TreeNode(T value, TreeNode<T> parent) {
        this.value = value;
        this.parent = parent;
    }

    /**
     * 獲取根節(jié)點(diǎn)
     */
    TreeNode<T> root() {
        TreeNode<T> cur = this;
        while (cur.parent != null) {
            cur = cur.parent;
        }
        return cur;
    }

    /**
     * 中序遍歷
     */
    void inOrderTraverse() {
        if(this.left != null) this.left.inOrderTraverse();
        System.out.println(this.value);
        if(this.right != null) this.right.inOrderTraverse();
    }

    /**
     * 經(jīng)典的二叉樹插入元素的方法
     */
    TreeNode<T> insert(T value) {
        // 先找根元素
        TreeNode<T> cur = root();

        TreeNode<T> p;
        int dir;

        // 尋找元素應(yīng)該插入的位置
        do {
            p = cur;
            if ((dir=value.compareTo(p.value)) < 0) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        } while (cur != null);

        // 把元素放到找到的位置
        if (dir < 0) {
            p.left = new TreeNode<>(value, p);
            return p.left;
        } else {
            p.right = new TreeNode<>(value, p);
            return p.right;
        }
    }
}

TreeMap的遍歷

從上面二叉樹的遍歷我們很明顯地看到，它是通過遞歸的方式實(shí)現(xiàn)的，但是遞歸會(huì)占用額外的空間，直接到線程棧整個(gè)釋放掉才會(huì)把方法中申請(qǐng)的變量銷毀掉，所以當(dāng)元素特別多的時(shí)候是一件很危險(xiǎn)的事。

（上面的例子中，沒有申請(qǐng)額外的空間，如果有聲明變量，則可以理解為直到方法完成才會(huì)銷毀變量）

那么，有沒有什么方法不用遞歸呢？

讓我們來看看java中的實(shí)現(xiàn)：

@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
    Objects.requireNonNull(action);
    // 遍歷前的修改次數(shù)
    int expectedModCount = modCount;
    // 執(zhí)行遍歷，先獲取第一個(gè)元素的位置，再循環(huán)遍歷后繼節(jié)點(diǎn)
    for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
        // 執(zhí)行動(dòng)作
        action.accept(e.key, e.value);

        // 如果發(fā)現(xiàn)修改次數(shù)變了，則拋出異常
        if (expectedModCount != modCount) {
            throw new ConcurrentModificationException();
        }
    }
}

是不是很簡(jiǎn)單？！

（1）尋找第一個(gè)節(jié)點(diǎn)；

從根節(jié)點(diǎn)開始找最左邊的節(jié)點(diǎn)，即最小的元素。

    final Entry<K,V> getFirstEntry() {
        Entry<K,V> p = root;
        // 從根節(jié)點(diǎn)開始找最左邊的節(jié)點(diǎn)，即最小的元素
        if (p != null)
            while (p.left != null)
                p = p.left;
        return p;
    }

（2）循環(huán)遍歷后繼節(jié)點(diǎn)；

尋找后繼節(jié)點(diǎn)這個(gè)方法我們?cè)趧h除元素的時(shí)候也用到過，當(dāng)時(shí)的場(chǎng)景是有右子樹，則從其右子樹中尋找最小的節(jié)點(diǎn)。

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        // 如果當(dāng)前節(jié)點(diǎn)為空，返回空
        return null;
    else if (t.right != null) {
        // 如果當(dāng)前節(jié)點(diǎn)有右子樹，取右子樹中最小的節(jié)點(diǎn)
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        // 如果當(dāng)前節(jié)點(diǎn)沒有右子樹
        // 如果當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的左子節(jié)點(diǎn)，直接返回父節(jié)點(diǎn)
        // 如果當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的右子節(jié)點(diǎn)，一直往上找，直到找到一個(gè)祖先節(jié)點(diǎn)是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)為止，返回這個(gè)祖先節(jié)點(diǎn)的父節(jié)點(diǎn)
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

讓我們一起來分析下這種方式的時(shí)間復(fù)雜度吧。

首先，尋找第一個(gè)元素，因?yàn)榧t黑樹是接近平衡的二叉樹，所以找最小的節(jié)點(diǎn)，相當(dāng)于是從頂?shù)降琢?，時(shí)間復(fù)雜度為O(log n)；

其次，尋找后繼節(jié)點(diǎn)，因?yàn)榧t黑樹插入元素的時(shí)候會(huì)自動(dòng)平衡，最壞的情況就是尋找右子樹中最小的節(jié)點(diǎn)，時(shí)間復(fù)雜度為O(log k)，k為右子樹元素個(gè)數(shù)；

最后，需要遍歷所有元素，時(shí)間復(fù)雜度為O(n)；

所以，總的時(shí)間復(fù)雜度為 O(log n) + O(n * log k) ≈ O(n)。

雖然遍歷紅黑樹的時(shí)間復(fù)雜度是O(n)，但是它實(shí)際是要比跳表要慢一點(diǎn)的，啥？跳表是啥？安心，后面會(huì)講到跳表的。

以上是“java集合之TreeMap源碼的示例分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

分享題目：java集合之TreeMap源碼的示例分析
文章路徑：http://muchs.cn/article26/iioicg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、響應(yīng)式網(wǎng)站、標(biāo)簽優(yōu)化、靜態(tài)網(wǎng)站、虛擬主機(jī)、關(guān)鍵詞優(yōu)化

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容