程序員常用的IDEA插件：https://github.com/silently9527/ToolsetIdeaPlugin

微信公眾號(hào)：貝塔學(xué)Java

前言

在上一篇中我們基于數(shù)組和鏈表實(shí)現(xiàn)了Map的相關(guān)操作，但是對(duì)于數(shù)據(jù)量稍大的情況下，這兩種實(shí)現(xiàn)方式效率都比較低，為了改進(jìn)這個(gè)問題，本篇我們將來學(xué)習(xí)二叉樹，并通過二叉樹來實(shí)現(xiàn)上一篇中定義的Map結(jié)構(gòu)

二叉樹簡(jiǎn)介

雖然大家都知道二叉樹是什么，但是為了保證文章的完整性，這里還是簡(jiǎn)單說說什么是二叉樹

二叉樹中每個(gè)節(jié)點(diǎn)都包含了兩個(gè)指針指向自己的左子樹和右子樹。

二叉樹的每個(gè)節(jié)點(diǎn)都包含了一個(gè)Key, 并且每個(gè)節(jié)點(diǎn)的Key都大于其左子樹中的任意節(jié)點(diǎn)，小于右子樹中的任意節(jié)點(diǎn)。

image

節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義：

class Node {
    private K key;
    private V value;
    private Node left;
    private Node right;
    private int size = 1; 

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

size 記錄當(dāng)前節(jié)點(diǎn)所在子樹的節(jié)點(diǎn)個(gè)數(shù)，計(jì)算方式：size=左子樹的個(gè)數(shù) + 1 + 右子樹的個(gè)數(shù)

基于二叉樹實(shí)現(xiàn)Map

在上一篇《基于數(shù)組或鏈表實(shí)現(xiàn)Map》中我們定義了Map的接口，本篇我們繼續(xù)使用該map接口

public interface Map<K, V> {
    void put(K key, V value);

    V get(K key);

    void delete(K key);

    int size();

    Iterable<K> keys();

    Iterable<TreeNode> nodes();

    default boolean contains(K key) {
        return get(key) != null;
    }

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

public interface SortedMap<K extends Comparable<K>, V> extends Map<K, V> {
    int rank(K key);

    void deleteMin();

    void deleteMax();
    
    K min();

    K max();
}

查詢

在二叉樹中查找一個(gè)鍵最簡(jiǎn)單直接的方式就是使用遞歸，把查找的key和節(jié)點(diǎn)的key進(jìn)行比較，如果較小就去左子樹中繼續(xù)遞歸查找，如果較大就在右子樹中查找，如果相等，表示已找到直接返回value，如果遞歸結(jié)束還未找到就返回null

代碼實(shí)現(xiàn)：

@Override
public V get(K key) {
    if (Objects.isNull(key)) {
        throw new IllegalArgumentException("key can not null");
    }

    Node node = get(root, key);
    return Objects.isNull(node) ? null : node.value;
}

private Node get(Node node, K key) {
    if (Objects.isNull(node)) {
        return null;
    }
    int compare = key.compareTo(node.key);
    if (compare > 0) {
        return get(node.right, key);
    } else if (compare < 0) {
        return get(node.left, key);
    } else {
        return node;
    }
}

查詢出最大值和最小值

在二叉樹中我們可能會(huì)經(jīng)常使用到查詢樹中的最大值和最小值，包括后面我們的刪除操作也會(huì)使用到，所以這里我們需要實(shí)現(xiàn)這兩個(gè)方法；

最大值的實(shí)現(xiàn)： 從根節(jié)點(diǎn)開始沿著右子樹遞歸，直到遇到右子樹為null的時(shí)候就結(jié)束，此時(shí)的節(jié)點(diǎn)就是最大值
最小值的實(shí)現(xiàn)： 從根節(jié)點(diǎn)開始沿著左子樹遞歸，知道遇到左子樹為null的時(shí)候就結(jié)束，此時(shí)的節(jié)點(diǎn)就是最小值

@Override
public K max() {
    Node max = max(root);
    return max.key;
}

protected Node min(Node node) {
    if (Objects.isNull(node.left)) {
        return node;
    }
    return min(node.left);
}

protected Node max(Node node) {
    if (Objects.isNull(node.right)) {
        return node;
    }
    return max(node.right);
}

插入

從上面的實(shí)現(xiàn)我們可以看出二叉樹的查詢方法和上篇中數(shù)組二分查找法實(shí)現(xiàn)的一樣簡(jiǎn)單高效，這是二叉樹的一個(gè)重要特性，而且二叉樹的插入與查詢操作一樣簡(jiǎn)單，理想情況下插入和查詢操作時(shí)間復(fù)雜度都是log(N)

插入操作的實(shí)現(xiàn)思路： 與查詢操作類似，依然是遞歸，如果put的key值比當(dāng)前節(jié)點(diǎn)大就需要去右子樹遞歸，如果較小就去左子樹遞歸，如果相等就直接更新節(jié)點(diǎn)的值。如果遞歸結(jié)束后還未找到值就新建一個(gè)節(jié)點(diǎn)并返回

image

private Node put(Node node, K key, V value) {
    if (Objects.isNull(node)) {
        return new Node(key, value);
    }

    int compare = key.compareTo(node.key);
    if (compare > 0) {
        node.right = put(node.right, key, value);
    } else if (compare < 0) {
        node.left = put(node.left, key, value);
    } else {
        node.value = value;
    }

    node.size = size(node.left) + 1 + size(node.right);
    return node;
}

private int size(Node node) {
    if (Objects.isNull(node)) {
        return 0;
    }
    return node.size;
}

其中size的計(jì)算在前面已經(jīng)說到，當(dāng)前節(jié)點(diǎn)的size = 左子樹.size + 1 + 右子樹.size

刪除最大值和最小值

二叉樹中相對(duì)比較麻煩的操作就是刪除操作，所以我們先來了解下刪除最大值和最小值應(yīng)該如何實(shí)現(xiàn)。

刪除最小值：和前面實(shí)現(xiàn)查找最小值有些相似，沿著左邊路徑一直深入，直到遇到一個(gè)節(jié)點(diǎn)的左子樹為null, 那么這個(gè)當(dāng)前節(jié)點(diǎn)就是最小值，在遞歸中把當(dāng)前節(jié)點(diǎn)的右子樹返回即可；

image

最大值實(shí)現(xiàn)思路類似

代碼如下：

@Override
public void deleteMin() {
    root = deleteMin(root);
}

public Node deleteMin(Node node) {
    if (Objects.isNull(node.left)) {
        return node.right;
    }
    node.left = deleteMin(node.left);
    node.size = size(node.left) + 1 + size(node.right);
    return node;
}

@Override
public void deleteMax() {
    root = deleteMax(root);
}

public Node deleteMax(Node node) {
    if (Objects.isNull(node.right)) {
        return node.left;
    }
    node.right = deleteMax(node.right);
    node.size = size(node.left) + 1 + size(node.right);
    return node;
}

刪除

我們可以通過類似的方式去刪除只有一個(gè)子節(jié)點(diǎn)或者是沒有子節(jié)點(diǎn)的節(jié)點(diǎn)；但是如果遇到需要?jiǎng)h除有兩個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)應(yīng)該怎么操作呢？

兩種思路：用左子樹的最大值替換待刪除節(jié)點(diǎn)，然后刪除掉左子樹的最大值；或者是用右子樹中的最小值替換待刪除節(jié)點(diǎn)，然后刪除右子樹中的最小值

步驟：

1. 從該節(jié)點(diǎn)的左子樹中取出最大值或者是從右子樹中取出最小值
2. 用最大值或者最小值替換當(dāng)前的節(jié)點(diǎn)
3. 調(diào)用刪除最大值或者刪除最小值

image

代碼實(shí)現(xiàn)

@Override
public void delete(K key) {
    root = delete(root, key);
}

private Node delete(Node node, K key) {
    if (Objects.isNull(node)) {
        return null;
    }
    int compare = key.compareTo(node.key);
    if (compare > 0) {
        node.right = delete(node.right, key);
    } else if (compare < 0) {
        node.left = delete(node.left, key);
    } else {
        if (Objects.isNull(node.left)) {
            return node.right;
        }
        if (Objects.isNull(node.right)) {
            return node.left;
        }

        Node max = max(node.left);
        node.key = max.key;
        node.value = max.value;

        node.left = deleteMax(node.left);
    }
    node.size = size(node.left) + 1 + size(node.right);
    return node;
}

分析

使用二叉樹實(shí)現(xiàn)的Map運(yùn)行的效率取決于樹的形狀，而樹的形狀取決于數(shù)據(jù)輸入的順序；最好的情況下二叉樹是平衡的，那么get、put的時(shí)間復(fù)雜度都是log(N); 但是如果插入的數(shù)據(jù)是有序的，那么二叉樹就會(huì)演變成鏈表，那么get、put的性能將會(huì)大大減低；

基于這個(gè)問題，我們會(huì)繼續(xù)改進(jìn)我們實(shí)現(xiàn)的Map，下一篇我們將會(huì)學(xué)習(xí)使用紅黑樹來實(shí)現(xiàn)我們的Map操作，無論數(shù)據(jù)插入的順序如何都能保證二叉樹近似平衡

文中所有源碼已放入到了github倉庫https://github.com/silently9527/JavaCore

最后（點(diǎn)關(guān)注，不迷路）

文中或許會(huì)存在或多或少的不足、錯(cuò)誤之處，有建議或者意見也非常歡迎大家在評(píng)論交流。

最后，寫作不易，請(qǐng)不要白嫖我喲，希望朋友們可以點(diǎn)贊評(píng)論關(guān)注三連，因?yàn)檫@些就是我分享的全部動(dòng)力來源??