第十二章 TreeMap

原文：Chapter 12 TreeMap

譯者：飛龍

協(xié)議：CC BY-NC-SA 4.0

自豪地采用谷歌翻譯

這一章展示了二叉搜索樹，它是個(gè)Map接口的高效實(shí)現(xiàn)扩然。如果我們想讓元素有序挖垛，它非常實(shí)用虑灰。

12.1 哈希哪里不對(duì)惯豆？

此時(shí)害淤，你應(yīng)該熟悉 Java 提供的Map接口和HashMap實(shí)現(xiàn)挖息。通過使用哈希表來制作你自己的Map，你應(yīng)該了解HashMap的工作原理码邻，以及為什么我們預(yù)計(jì)其核心方法是常數(shù)時(shí)間的折剃。

由于這種表現(xiàn)，HashMap被廣泛使用像屋，但并不是唯一的Map實(shí)現(xiàn)怕犁。有幾個(gè)原因可能需要另一個(gè)實(shí)現(xiàn)：

哈希可能很慢己莺，所以即使HashMap操作是常數(shù)時(shí)間奏甫，“常數(shù)”可能很大。
如果哈希函數(shù)將鍵均勻分配給子映射凌受，效果很好阵子。但設(shè)計(jì)良好的散列函數(shù)并不容易，如果太多的鍵在相同的子映射上胁艰，那么HashMap的性能可能會(huì)很差款筑。
哈希表中的鍵不以任何特定順序存儲(chǔ)智蝠；實(shí)際上腾么，當(dāng)表增長(zhǎng)并且鍵被重新排列時(shí)，順序可能會(huì)改變杈湾。對(duì)于某些應(yīng)用程序解虱，必須或至少保持鍵的順序，這很有用漆撞。

很難同時(shí)解決所有這些問題殴泰，但是 Java 提供了一個(gè)稱為TreeMap的實(shí)現(xiàn)：

• 它不使用哈希函數(shù)于宙，所以它避免了哈希的開銷和選擇哈希函數(shù)的困難。
• 在TreeMap之中悍汛，鍵被存儲(chǔ)在二叉搜索樹中捞魁，這使我們可以以線性時(shí)間順序遍歷鍵。
• 核心方法的運(yùn)行時(shí)間與log(n)成正比离咐，并不像常數(shù)時(shí)間那樣好谱俭，但仍然非常好。

在下一節(jié)中宵蛀，我將解釋二進(jìn)制搜索樹如何工作昆著，然后你將使用它來實(shí)現(xiàn)Map。另外术陶，使用樹實(shí)現(xiàn)時(shí)凑懂，我們將分析映射的核心方法的性能。

12.2 二叉搜索樹

二叉搜索樹（BST）是一個(gè)樹梧宫，其中每個(gè)node（節(jié)點(diǎn)）包含一個(gè)鍵接谨，并且每個(gè)都具有“BST 屬性”：

• 如果node有一個(gè)左子樹，左子樹中的所有鍵都必須小于node的鍵塘匣。
• 如果node有一個(gè)右子樹疤坝，右子樹中的所有鍵都必須大于node的鍵。

圖 12.1：二叉搜索樹示例

圖 12.1 展示了一個(gè)具有此屬性的整數(shù)的樹馆铁。這個(gè)圖片來自二叉搜索樹的維基百科頁(yè)面跑揉，位于 http://thinkdast.com/bst，當(dāng)你做這個(gè)練習(xí)時(shí)埠巨，你會(huì)發(fā)現(xiàn)它很實(shí)用历谍。

根節(jié)點(diǎn)中的鍵為8，你可以確認(rèn)根節(jié)點(diǎn)左邊的所有鍵小于8辣垒，右邊的所有鍵都更大望侈。你還可以檢查其他節(jié)點(diǎn)是否具有此屬性。

在二叉搜索樹中查找一個(gè)鍵是很快的勋桶，因?yàn)槲覀儾槐厮阉髡麄€(gè)樹脱衙。從根節(jié)點(diǎn)開始，我們可以使用以下算法：

• 將你要查找的鍵target例驹，與當(dāng)前節(jié)點(diǎn)的鍵進(jìn)行比較捐韩。如果他們相等，你就完成了鹃锈。
• 如果target小于當(dāng)前鍵荤胁，搜索左子樹。如果沒有屎债，target不在樹上仅政。
• 如果target大于當(dāng)前鍵垢油，搜索右子樹。如果沒有圆丹，target不在樹上滩愁。

在樹的每一層，你只需要搜索一個(gè)子樹辫封。例如惊楼，如果你在上圖中查找target = 4，則從根節(jié)點(diǎn)開始秸讹，它包含鍵8檀咙。因?yàn)?code>target小于8，你走了左邊璃诀。因?yàn)?code>target大于3弧可，你走了右邊。因?yàn)?code>target小于6劣欢，你走了左邊棕诵。然后你找到你要找的鍵。

在這個(gè)例子中凿将，即使樹包含九個(gè)鍵校套，它需要四次比較來找到目標(biāo)。一般來說牧抵，比較的數(shù)量與樹的高度成正比笛匙，而不是樹中的鍵的數(shù)量。

因此犀变，我們可以計(jì)算樹的高度h和節(jié)點(diǎn)個(gè)數(shù)n的關(guān)系妹孙。從小的數(shù)值開始，逐漸增加：

如果h=1获枝，樹只包含一個(gè)節(jié)點(diǎn)蠢正，那么n=1。
如果h=2省店，我們可以添加兩個(gè)節(jié)點(diǎn)嚣崭，總共n=3。
如果h=3懦傍，我們可以添加多達(dá)四個(gè)節(jié)點(diǎn)雹舀，總共n=7。
如果h=4谎脯，我們可以添加多達(dá)八個(gè)節(jié)點(diǎn)葱跋，總共n=15持寄。

現(xiàn)在你可能會(huì)看到這個(gè)規(guī)律源梭。如果我們將樹的層數(shù)從1數(shù)到n娱俺，第i層可以擁有多達(dá)2^(n-1)個(gè)節(jié)點(diǎn)。h層的樹共有2^h-1個(gè)節(jié)點(diǎn)废麻。如果我們有：

n = 2^h - 1

我們可以對(duì)兩邊取以2為底的對(duì)數(shù)：

log2(n) ≈ h

意思是樹的高度正比于logn荠卷，如果它是滿的。也就是說烛愧，如果每一層包含最大數(shù)量的節(jié)點(diǎn)油宜。

所以我們預(yù)計(jì)，我們可以以正比于logn的時(shí)間怜姿，在二叉搜索樹中查找節(jié)點(diǎn)慎冤。如果樹是慢的，即使是部分滿的沧卢，這是對(duì)的蚁堤。但是并不總是對(duì)的，我們將會(huì)看到但狭。

時(shí)間正比于logn的算法是對(duì)數(shù)時(shí)間的披诗，并且屬于O(logn)的增長(zhǎng)級(jí)別。

12.3 練習(xí) 10

對(duì)于這個(gè)練習(xí)立磁，你將要使用二叉搜索樹編寫Map接口的一個(gè)實(shí)現(xiàn)呈队。

這里是實(shí)現(xiàn)的開頭，叫做MyTreeMap：

public class MyTreeMap<K, V> implements Map<K, V> {

    private int size = 0;
    private Node root = null;

實(shí)例變量是size唱歧，它跟蹤了鍵的數(shù)量宪摧，以及root，它是樹中根節(jié)點(diǎn)的引用颅崩。樹為空的時(shí)候绍刮，root是null，size是0挨摸。

這里是Node的定義孩革，它在MyTreeMap之中定義。

    protected class Node {
        public K key;
        public V value;
        public Node left = null;
        public Node right = null;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

每個(gè)節(jié)點(diǎn)包含一個(gè)鍵值對(duì)得运，以及兩個(gè)子節(jié)點(diǎn)的引用膝蜈，left和right。任意子節(jié)點(diǎn)都可以為null熔掺。

一些Map方法易于實(shí)現(xiàn)饱搏，比如size和clear：

    public int size() {
        return size;
    }

    public void clear() {
        size = 0;
        root = null;
    }

size顯然是常數(shù)時(shí)間的。

clear也是常數(shù)時(shí)間的置逻，但是考慮這個(gè)：當(dāng)root賦為null時(shí)推沸，垃圾收集器回收了樹中的節(jié)點(diǎn)，這是線性時(shí)間的。這個(gè)工作是否應(yīng)該由垃圾收集器的計(jì)數(shù)來完成呢鬓催？我認(rèn)為是的肺素。

下一節(jié)中，你會(huì)填充一些其它方法宇驾，包括最重要的get和set倍靡。

12.4 實(shí)現(xiàn)TreeMap

這本書的倉(cāng)庫(kù)中，你將找到這些源文件：

• MyTreeMap.java包含上一節(jié)的代碼课舍，其中包含缺失方法的大綱塌西。
• MyTreeMapTest.java包含單元MyTreeMap的測(cè)試。

運(yùn)行ant build來編譯源文件筝尾。然后運(yùn)行ant MyTreeMapTest捡需。幾個(gè)測(cè)試應(yīng)該失敗，因?yàn)槟阌幸恍┕ぷ饕觯?/p>

我已經(jīng)提供了get和containsKey的大綱筹淫。他們都使用findNode栖忠，這是我定義的私有方法；它不是Map接口的一部分贸街。以下是它的起始：

    private Node findNode(Object target) {
        if (target == null) {
            throw new IllegalArgumentException();
        }

        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) target;

        // TODO: FILL THIS IN!
        return null;
    }

參數(shù)target是我們要查找的鍵庵寞。如果target是null，findNode拋出異常薛匪。一些Map實(shí)現(xiàn)可以將null處理為一個(gè)鍵捐川，但是在二叉搜索樹中，我們需要能夠比較鍵逸尖，所以處理null是有問題的古沥。為了保持簡(jiǎn)單，這個(gè)實(shí)現(xiàn)不將null視為鍵娇跟。

下一行顯示如何將target與樹中的鍵進(jìn)行比較岩齿。按照get和containsKey的簽名（名稱和參數(shù)），編譯器認(rèn)為target是一個(gè)Object苞俘。但是析珊，我們需要能夠?qū)︽I進(jìn)行比較港柜，所以我們將target強(qiáng)制轉(zhuǎn)換為Comparable<? super K>榛鼎，這意味著它可以與類型K（或任何超類）的示例比較鲫惶。如果你不熟悉“類型通配符”的用法，可以在 http://thinkdast.com/gentut 上閱讀更多內(nèi)容岗憋。

幸運(yùn)的是肃晚，Java 的類型系統(tǒng)的處理不是這個(gè)練習(xí)的重點(diǎn)。你的工作是填寫剩下的findNode仔戈。如果它發(fā)現(xiàn)一個(gè)包含target鍵的節(jié)點(diǎn)关串，它應(yīng)該返回該節(jié)點(diǎn)拧廊。否則應(yīng)該返回null。當(dāng)你使其工作晋修，get和containsKey的測(cè)試應(yīng)該通過吧碾。

請(qǐng)注意，你的解決方案應(yīng)該只搜索通過樹的一條路徑飞蚓，因此它應(yīng)該與樹的高度成正比滤港。你不應(yīng)該搜索整棵樹廊蜒！

你的下一個(gè)任務(wù)是填充containsValue趴拧。為了讓你起步，我提供了一個(gè)輔助方法equals山叮，比較target和給定的鍵著榴。請(qǐng)注意，樹中的值（與鍵相反）不一定是可比較的屁倔，所以我們不能使用compareTo脑又；我們必須在target上調(diào)用equals。

不像你以前的findNode解決方案锐借，你的containsValue解決方案應(yīng)該搜索整個(gè)樹问麸，所以它的運(yùn)行時(shí)間正比于鍵的數(shù)量n，而不是樹的高度h钞翔。

譯者注：這里你可能想使用之前講過的 DFS 迭代器严卖。

你應(yīng)該填充的下一個(gè)方法是put。我提供了處理簡(jiǎn)單情況的起始代碼：

    public V put(K key, V value) {
        if (key == null) {
            throw new IllegalArgumentException();
        }
        if (root == null) {
            root = new Node(key, value);
            size++;
            return null;
        }
        return putHelper(root, key, value);
    }

    private V putHelper(Node node, K key, V value) {
        // TODO: Fill this in.
    }

如果你嘗試將null作為關(guān)鍵字布轿，put則會(huì)拋出異常哮笆。

如果樹為空，則put創(chuàng)建一個(gè)新節(jié)點(diǎn)并初始化實(shí)例變量root汰扭。

否則稠肘，它調(diào)用putHelper，這是我定義的私有方法萝毛；它不是Map接口的一部分项阴。

填寫putHelper，讓它搜索樹笆包，以及：

• 如果key已經(jīng)在樹中鲁冯，它將使用新值替換舊值，并返回舊值色查。
• 如果key不在樹中薯演，它將創(chuàng)建一個(gè)新節(jié)點(diǎn)，找到正確的添加位置秧了，并返回null跨扮。

你的put實(shí)現(xiàn)的是時(shí)間應(yīng)該與樹的高度h成正比，而不是元素的數(shù)量n。理想情況下衡创，你只需搜索一次樹帝嗡，但如果你發(fā)現(xiàn)兩次更容易搜索，可以這樣做：它會(huì)慢一些璃氢，但不會(huì)改變?cè)鲩L(zhǎng)級(jí)別哟玷。

最后，你應(yīng)該填充keySet一也。根據(jù) http://thinkdast.com/mapkeyset 的文檔巢寡，該方法應(yīng)該返回一個(gè)Set，可以按順序迭代鍵椰苟；也就是說抑月，按照compareTo方法，升序迭代舆蝴。我們?cè)?8.3 節(jié)中使用的HashSet實(shí)現(xiàn)不會(huì)維護(hù)鍵的順序谦絮，但LinkedHashSet實(shí)現(xiàn)可以。你可以閱讀 http://thinkdast.com/linkedhashset洁仗。

我提供了一個(gè)keySet的大綱层皱，創(chuàng)建并返回LinkedHashSet：

    public Set<K> keySet() {
        Set<K> set = new LinkedHashSet<K>();
        return set;
    }

你應(yīng)該完成此方法，使其以升序向set添加樹中的鍵赠潦。提示：你可能想編寫一個(gè)輔助程序叫胖；你可能想讓它遞歸；你也可能想要閱讀 http://thinkdast.com/inorder 上的樹的中序遍歷祭椰。

當(dāng)你完成時(shí)臭家，所有測(cè)試都應(yīng)該通過。下一章中方淤，我會(huì)講解我的解法钉赁，并測(cè)試核心方法的性能。