基于二分搜索樹的集合實現(xiàn)

集合（Set）的基礎概念：

• 數(shù)據(jù)結構中的集合概念與數(shù)學中的集合概念是一樣的，集合中的元素是無序且不重復的，一個元素在集合中只會出現(xiàn)一次。集合在邏輯上是一個線性的結構，但在底層中可以采用多種實現(xiàn)，例如鏈表、二分搜索樹及哈希表等。所以集合總的來說是高層次的抽象數(shù)據(jù)結構，底層實現(xiàn)可以有多種。

本小節(jié)演示一下如何基于二分搜索樹實現(xiàn)一個集合，我們都知道二分搜索樹通常不存放重復元素，且不采用中序遍歷的情況下訪問元素是“無序”的（但通常基于樹實現(xiàn)的集合是有序集合），正好符合集合的特性，可以直接作為集合的底層實現(xiàn)。

首先，我們要實現(xiàn)一個簡單的二分搜索樹。具體代碼如下：

package tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二分搜索樹
 * 由于存儲的數(shù)據(jù)需具有可比較性，所以泛型需繼承Comparable接口
 *
 * @author 01
 **/
public class BinarySearchTree<E extends Comparable<E>> {

    /**
     * 節(jié)點結構
     */
    private class Node {
        E e;
        Node left;
        Node right;

        public Node() {
            this(null, null, null);
        }

        public Node(E e) {
            this(e, null, null);
        }

        public Node(E e, Node left, Node right) {
            this.e = e;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 根節(jié)點
     */
    private Node root;

    /**
     * 表示樹里存儲的元素個數(shù)
     */
    private int size;

    /**
     * 獲取樹里的元素個數(shù)
     *
     * @return 元素個數(shù)
     */
    public int size() {
        return size;
    }

    /**
     * 樹是否為空
     *
     * @return 為空返回true，否則返回false
     */
    public boolean isEmpty() {
        return size == 0;
    }
    
    /**
     * 向二分搜索樹中添加一個新元素e
     *
     * @param e 新元素
     */
    public void add(E e) {
        if (root == null) {
            // 根節(jié)點為空的處理
            root = new Node(e);
            size++;
        } else {
            add(root, e);
        }
    }

    /**
     * 向以node為根的二分搜索樹中插入元素e，遞歸實現(xiàn)
     */
    private void add(Node node, E e) {
        // 遞歸的終止條件
        if (e.equals(node.e)) {
            // 不存儲重復元素
            return;
        } else if (e.compareTo(node.e) < 0 && node.left == null) {
            // 元素e小于node節(jié)點的元素，并且node節(jié)點的左孩子為空，所以成為node節(jié)點的左孩子
            node.left = new Node(e);
            size++;
            return;
        } else if (e.compareTo(node.e) > 0 && node.right == null) {
            // 元素e大于node節(jié)點的元素，并且node節(jié)點的右孩子為空，所以成為node節(jié)點的右孩子
            node.right = new Node(e);
            size++;
            return;
        }

        if (e.compareTo(node.e) < 0) {
            // 元素e小于node節(jié)點的元素，往左子樹走
            add(node.left, e);
        } else {
            // 元素e大于node節(jié)點的元素，往右子樹走
            add(node.right, e);
        }
    }

    /**
     * 從二分搜索樹中刪除元素為e的節(jié)點
     */
    public void remove(E e) {
        root = remove(root, e);
    }

    /**
     * 刪除以node為根的二分搜索樹中值為e的節(jié)點，遞歸實現(xiàn)
     * 返回刪除節(jié)點后新的二分搜索樹的根
     */
    private Node remove(Node node, E e) {
        if (node == null) {
            return null;
        }

        if (e.compareTo(node.e) < 0) {
            // 要刪除的節(jié)點在左子樹中
            node.left = remove(node.left, e);
            return node;
        } else if (e.compareTo(node.e) > 0) {
            // 要刪除的節(jié)點在右子樹中
            node.right = remove(node.right, e);
            return node;
        }

        // 找到了要刪除的節(jié)點
        // 待刪除的節(jié)點左子樹為空的情況
        if (node.left == null) {
            // 如果有右子樹，需要將其掛到被刪除的節(jié)點上
            Node rightNode = node.right;
            node.right = null;
            size--;

            return rightNode;
        }

        // 待刪除的節(jié)點右子樹為空的情況
        if (node.right == null) {
            // 如果有左子樹，需要將其掛到被刪除的節(jié)點上
            Node leftNode = node.left;
            node.left = null;
            size--;

            return leftNode;
        }

        // 待刪除的節(jié)點左右子樹均不為空的情況
        // 找到比待刪除節(jié)點大的最小節(jié)點，即待刪除節(jié)點右子樹的最小節(jié)點
        Node successor = minimum(node.right);
        // 用這個節(jié)點替換待刪除節(jié)點的位置
        // 由于removeMin里已經(jīng)維護過一次size了，所以這里就不需要維護一次了
        successor.right = removeMin(node.right);
        successor.left = node.left;

        return successor;
    }

    /**
     * 查看二分搜索樹中是否包含元素e
     */
    public boolean contains(E e) {
        return contains(root, e);
    }

    /**
     * 查看以node為根節(jié)點的二分搜索樹中是否包含元素e，遞歸實現(xiàn)
     */
    private boolean contains(Node node, E e) {
        if (node == null) {
            return false;
        }

        if (e.compareTo(node.e) == 0) {
            return true;
        } else if (e.compareTo(node.e) < 0) {
            // 找左子樹
            return contains(node.left, e);
        }

        // 找右子樹
        return contains(node.right, e);
    }
}

有了二分搜索樹這個底層數(shù)據(jù)結構之后，實現(xiàn)集合就很簡單了，因為二分搜索樹基本可以覆蓋集合的特性。由于集合是一個相對上層的數(shù)據(jù)結構，所以在實現(xiàn)集合時需要定義一個接口，抽象出集合的操作。這樣底層無論使用什么數(shù)據(jù)結構實現(xiàn)，對于上層來說都是無感知的，這也是面向接口編程的好處。接口定義如下：

package set;

/**
 * 集合接口
 *
 * @author 01
 * @date 2021-01-18
 **/
public interface Set<E> {
    /**
     * 添加元素
     *
     * @param e e
     */
    void add(E e);

    /**
     * 刪除元素
     *
     * @param e e
     */
    void remove(E e);

    /**
     * 是否包含指定元素
     *
     * @param e e
     * @return boolean
     */
    boolean contains(E e);

    /**
     * 獲取集合中的元素個數(shù)
     *
     * @return int
     */
    int getSize();

    /**
     * 集合是否為空
     *
     * @return boolean
     */
    boolean isEmpty();
}

在集合接口的具體實現(xiàn)類中，基本只需要調用二分搜索樹的方法即可，這樣我們很簡單就實現(xiàn)了一個集合數(shù)據(jù)結構。代碼如下：

package set;

import tree.BinarySearchTree;

/**
 * 基于二分搜索樹實現(xiàn)的集合
 *
 * @author 01
 * @date 2021-01-18
 **/
public class TreeSet<E extends Comparable<E>> implements Set<E> {

    private final BinarySearchTree<E> bst;

    public TreeSet() {
        bst = new BinarySearchTree<>();
    }

    @Override
    public void add(E e) {
        bst.add(e);
    }

    @Override
    public void remove(E e) {
        bst.remove(e);
    }

    @Override
    public boolean contains(E e) {
        return bst.contains(e);
    }

    @Override
    public int getSize() {
        return bst.size();
    }

    @Override
    public boolean isEmpty() {
        return bst.isEmpty();
    }
}

基于鏈表的集合實現(xiàn)

使用其他數(shù)據(jù)結構，例如鏈表也能實現(xiàn)集合，同為線性結構的動態(tài)數(shù)組也可以。本小節(jié)簡單演示下，基于基于鏈表的集合實現(xiàn)。和之前一樣，首先實現(xiàn)一個簡單的鏈表數(shù)據(jù)結構，代碼如下：

package linkedlist;

/**
 * 單向鏈表數(shù)據(jù)結構
 *
 * @author 01
 * @date 2018-11-08
 **/
public class LinkedList<E> {
    /**
     * 鏈表中的節(jié)點
     */
    private class Node {
        E e;
        Node next;

        public Node() {
            this(null, null);
        }

        public Node(E e) {
            this(e, null);
        }

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    /**
     * 虛擬頭節(jié)點
     */
    private Node dummyHead;

    /**
     * 鏈表中元素的個數(shù)
     */
    private int size;

    public LinkedList() {
        this.dummyHead = new Node(null, null);
        this.size = 0;
    }

    /**
     * 獲取鏈表中的元素個數(shù)
     *
     * @return 元素個數(shù)
     */
    public int getSize() {
        return size;
    }

    /**
     * 鏈表是否為空
     *
     * @return 為空返回true，否則返回false
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 在鏈表的index(0-based)位置添加新的元素e
     *
     * @param index 元素添加的位置
     * @param e     新的元素
     */
    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }

        Node prev = dummyHead;
        // 移動prev到index前一個節(jié)點的位置
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        Node node = new Node(e);
        node.next = prev.next;
        prev.next = node;

        // 同樣，以上三句代碼可以一句代碼完成
        // prev.next = new Node(e, prev.next);

        size++;
    }

    /**
     * 在鏈表頭添加新的元素e
     *
     * @param e 新的元素
     */
    public void addFirst(E e) {
        add(0, e);
    }
    
    /**
     * 查找鏈表中是否包含元素e
     */
    public boolean contains(E e) {
        Node cur = dummyHead.next;
        // 第一種遍歷鏈表的方式
        while (cur != null) {
            if (cur.e.equals(e)) {
                return true;
            }
            cur = cur.next;
        }

        return false;
    }

    /**
     * 從鏈表中刪除元素e
     */
    public void removeElement(E e) {
        Node prev = dummyHead;
        while (prev.next != null) {
            if (prev.next.e.equals(e)) {
                break;
            }
            prev = prev.next;
        }

        if (prev.next != null) {
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size--;
        }
    }
}

然后基于這個鏈表結構就可以輕易實現(xiàn)集合了。代碼如下：

package set;

import linkedlist.LinkedList;

/**
 * 基于鏈表實現(xiàn)的集合
 *
 * @author 01
 * @date 2021-01-18
 **/
public class LinkedListSet<E> implements Set<E> {

    private final LinkedList<E> linkedList;

    public LinkedListSet() {
        linkedList = new LinkedList<>();
    }

    @Override
    public void add(E e) {
        // 不存儲重復元素
        if (!linkedList.contains(e)) {
            linkedList.addFirst(e);
        }
    }

    @Override
    public void remove(E e) {
        linkedList.removeElement(e);
    }

    @Override
    public boolean contains(E e) {
        return linkedList.contains(e);
    }

    @Override
    public int getSize() {
        return linkedList.getSize();
    }

    @Override
    public boolean isEmpty() {
        return linkedList.isEmpty();
    }
}

映射基礎

映射（Map）在數(shù)據(jù)結構中是指一種key-value的數(shù)據(jù)結構，key與value是有具有一對一關系的，所以稱之為映射。這與數(shù)學中的映射概念一樣，定義域與值域具有一對一的映射關系，描述這個映射關系的是函數(shù)：

image.png

映射這個詞相對來說有些晦澀，我們也可以將其類比成字典，這也是為什么一些編程語言中將其稱為字典（通常縮寫為dict）的原因。因為字典就是一種典型的映射關系，一個詞對應著一個釋義，也是key-value的結構，通過key我們就能快速找到value。

其實映射在我們的日常生活中無處不在，例如，身份證 -> 人、車牌號 -> 車以及工牌 -> 員工等。所以Map在很多領域都有著很重要的作用，最典型的就是大數(shù)據(jù)領域中的核心思想：Map-Reduce，典型的應用就是詞頻統(tǒng)計：單詞 -> 頻率。

與集合一樣，映射也是一個相對上層的數(shù)據(jù)結構，底層也可以由多種不同的數(shù)據(jù)結構來實現(xiàn)，常見的底層實現(xiàn)有：鏈表、二分搜索樹、紅黑樹以及哈希表等。所以我們需要定義一個Map接口作為上層抽像：

package map;

/**
 * 映射接口
 *
 * @author 01
 * @date 2021-01-18
 **/
public interface Map<K, V> {
    /**
     * 添加元素
     *
     * @param key   鍵
     * @param value 值
     */
    void add(K key, V value);

    /**
     * 根據(jù)key刪除元素
     *
     * @param key 鍵
     * @return 被刪除的value
     */
    V remove(K key);

    /**
     * 根據(jù)key查詢元素是否存在
     *
     * @param key key
     * @return boolean
     */
    boolean contains(K key);

    /**
     * 根據(jù)key獲取value
     *
     * @param key key
     * @return value
     */
    V get(K key);

    /**
     * 改變key的value
     *
     * @param key   key
     * @param value value
     */
    void set(K key, V value);

    /**
     * 獲取Map中的元素個數(shù)
     *
     * @return 元素個數(shù)
     */
    int getSize();

    /**
     * 判斷Map是否為空
     *
     * @return boolean
     */
    boolean isEmpty();
}

基于鏈表的映射實現(xiàn)

使用鏈表來實現(xiàn)映射，與實現(xiàn)普通的鏈表差別不大，唯一不同的就是鏈表中的節(jié)點不再是簡單地存儲單個元素，而是需要有兩個成員變量分別存儲key和value。具體的實現(xiàn)代碼如下：

package map;

/**
 * 基于鏈表實現(xiàn)的Map
 *
 * @author 01
 * @date 2021-01-18
 */
public class LinkedListMap<K, V> implements Map<K, V> {

    /**
     * 鏈表的節(jié)點結構，節(jié)點中會存儲鍵值對，而不是單個元素
     */
    private class Node {
        public K key;
        public V value;
        public Node next;

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

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

        public Node() {
            this(null, null, null);
        }

        @Override
        public String toString() {
            return key.toString() + " : " + value.toString();
        }
    }

    /**
     * 虛擬頭節(jié)點
     */
    private final Node dummyHead;
    private int size;

    public LinkedListMap() {
        dummyHead = new Node();
        size = 0;
    }

    /**
     * 根據(jù)傳入的key獲取鏈表中的節(jié)點
     */
    private Node getNode(K key) {
        Node cur = dummyHead.next;
        while (cur != null) {
            if (cur.key.equals(key)) {
                return cur;
            }
            cur = cur.next;
        }

        return null;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(K key) {
        return getNode(key) != null;
    }

    @Override
    public V get(K key) {
        Node node = getNode(key);
        return node == null ? null : node.value;
    }

    @Override
    public void add(K key, V value) {
        Node node = getNode(key);
        if (node == null) {
            // key不存在，往鏈表的頭部插入新元素
            dummyHead.next = new Node(key, value, dummyHead.next);
            size++;
        } else {
            // 否則，改變value
            node.value = value;
        }
    }

    @Override
    public void set(K key, V newValue) {
        Node node = getNode(key);
        if (node == null) {
            throw new IllegalArgumentException(key + " doesn't exist!");
        }

        node.value = newValue;
    }

    @Override
    public V remove(K key) {
        Node prev = dummyHead;
        // 根據(jù)key找到待刪除節(jié)點的前一個節(jié)點
        while (prev.next != null) {
            if (prev.next.key.equals(key)) {
                break;
            }
            prev = prev.next;
        }

        if (prev.next != null) {
            // 刪除目標節(jié)點
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size--;

            return delNode.value;
        }

        return null;
    }
}

基于二分搜索樹的映射實現(xiàn)

最后，我們來看一下基于二分搜索樹的映射實現(xiàn)。看了之前基于鏈表的實現(xiàn)案例后，對本小節(jié)的內容就很容易理解了，因為基于二分搜索樹的映射實現(xiàn)也是一樣的，除了樹的節(jié)點結構不一樣外，其余的邏輯與普通的二分搜索樹沒啥太大區(qū)別。具體實現(xiàn)代碼如下：

package map;

/**
 * 基于二分搜索樹實現(xiàn)的Map
 *
 * @author 01
 * @date 2021-01-18
 */
public class TreeMap<K extends Comparable<K>, V> implements Map<K, V> {

    /**
     * 二分搜索樹的節(jié)點結構，節(jié)點中會存儲鍵值對，而不是單個元素
     */
    private class Node {
        public K key;
        public V value;
        public Node left, right;

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

    private Node root;
    private int size;

    public TreeMap() {
        root = null;
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }


    @Override
    public void add(K key, V value) {
        // 向二分搜索樹中添加新的元素(key, value)
        root = add(root, key, value);
    }

    /**
     * 向以node為根的二分搜索樹中插入元素(key, value)，遞歸實現(xiàn)
     *
     * @return 返回插入新節(jié)點后二分搜索樹的根
     */
    private Node add(Node node, K key, V value) {
        if (node == null) {
            size++;
            return new Node(key, value);
        }

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

        return node;
    }

    /**
     * 返回以node為根節(jié)點的二分搜索樹中，key所在的節(jié)點
     */
    private Node getNode(Node node, K key) {
        if (node == null) {
            return null;
        }

        if (key.equals(node.key)) {
            return node;
        } else if (key.compareTo(node.key) < 0) {
            return getNode(node.left, key);
        } else {
            return getNode(node.right, key);
        }
    }

    @Override
    public boolean contains(K key) {
        return getNode(root, key) != null;
    }

    @Override
    public V get(K key) {

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

    @Override
    public void set(K key, V newValue) {
        Node node = getNode(root, key);
        if (node == null) {
            throw new IllegalArgumentException(key + " doesn't exist!");
        }

        node.value = newValue;
    }

    /**
     * 返回以node為根的二分搜索樹的最小值所在的節(jié)點
     */
    private Node minimum(Node node) {
        if (node.left == null) {
            return node;
        }

        return minimum(node.left);
    }

    /**
     * 刪除掉以node為根的二分搜索樹中的最小節(jié)點
     * 返回刪除節(jié)點后新的二分搜索樹的根
     */
    private Node removeMin(Node node) {
        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }

        node.left = removeMin(node.left);
        return node;
    }

    @Override
    public V remove(K key) {
        Node node = getNode(root, key);
        if (node != null) {
            // 從二分搜索樹中刪除鍵為key的節(jié)點
            root = remove(root, key);
            return node.value;
        }
        return null;
    }

    private Node remove(Node node, K key) {
        if (node == null) {
            return null;
        }

        if (key.compareTo(node.key) < 0) {
            node.left = remove(node.left, key);
            return node;
        } else if (key.compareTo(node.key) > 0) {
            node.right = remove(node.right, key);
            return node;
        } else {
            // 待刪除節(jié)點左子樹為空的情況
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }

            // 待刪除節(jié)點右子樹為空的情況
            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }

            // 待刪除節(jié)點左右子樹均不為空的情況
            // 找到比待刪除節(jié)點大的最小節(jié)點，即待刪除節(jié)點右子樹的最小節(jié)點
            Node successor = minimum(node.right);
            // 用這個節(jié)點頂替待刪除節(jié)點的位置
            successor.right = removeMin(node.right);
            successor.left = node.left;

            return successor;
        }
    }
}