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

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

二叉樹的遍歷

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

（1）前序遍歷，先遍歷我，再遍歷我的左子節點，最后遍歷我的右子節點；

（2）中序遍歷，先遍歷我的左子節點，再遍歷我，最后遍歷我的右子節點；

（3）后序遍歷，先遍歷我的左子節點，再遍歷我的右子節點，最后遍歷我；

這里的前中后都是以“我”的順序為準的，我在前就是前序遍歷，我在中就是中序遍歷，我在后就是后序遍歷。

下面讓我們看看經典的中序遍歷是怎么實現的：

public class TreeMapTest {

    public static void main(String[] args) {
        // 構建一顆10個元素的樹
        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);

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

/**
 * 樹節點，假設不存在重復元素
 * @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;
    }

    /**
     * 獲取根節點
     */
    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();
    }

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

        TreeNode<T> p;
        int dir;

        // 尋找元素應該插入的位置
        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的遍歷

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

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

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

讓我們來看看java中的實現：

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

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

是不是很簡單？！

（1）尋找第一個節點；

從根節點開始找最左邊的節點，即最小的元素。

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

（2）循環遍歷后繼節點；

尋找后繼節點這個方法我們在刪除元素的時候也用到過，當時的場景是有右子樹，則從其右子樹中尋找最小的節點。

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

讓我們一起來分析下這種方式的時間復雜度吧。

首先，尋找第一個元素，因為紅黑樹是接近平衡的二叉樹，所以找最小的節點，相當于是從頂到底了，時間復雜度為O(log n)；

其次，尋找后繼節點，因為紅黑樹插入元素的時候會自動平衡，最壞的情況就是尋找右子樹中最小的節點，時間復雜度為O(log k)，k為右子樹元素個數；

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

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

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

以上是“java集合之TreeMap源碼的示例分析”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！