【戀上數(shù)據(jù)結(jié)構(gòu)與算法一】(十二)集合(Set)、映射(Map)

集合(Set)

? 集合的特點(diǎn)
不存放重復(fù)的元素
常用于去重
?存放新增 IP，統(tǒng)計(jì)新增 IP 量
? 存放詞匯，統(tǒng)計(jì)詞匯量
? ……

public interface Set<E> {
    int size();
    boolean isEmpty();
    void clear();
    boolean contains(E element);
    void add(E element);
    void remove(E element);
    void traversal(Visitor<E> visitor);// 遍歷
    
    public static abstract class Visitor<E> {
        boolean stop;
        public abstract boolean visit(E element);
    }
}

? 思考:集合的內(nèi)部實(shí)現(xiàn)能否直接利用以前學(xué)過的數(shù)據(jù)結(jié)構(gòu)?
動(dòng)態(tài)數(shù)組
鏈表
二叉搜索樹(AVL樹、紅黑樹)

鏈表實(shí)現(xiàn)集合
package alangeit.set;

// 鏈表實(shí)現(xiàn)集合

import alangeit.list.LinkedList;
import alangeit.list.List;

public class ListSet<E> implements Set<E> {
    private List<E> list = new LinkedList<>();
    
    @Override
    public int size() {
        return list.size();
    }

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

    @Override
    public void clear() {
        list.clear();
    }

    @Override
    public boolean contains(E element) {
        return list.contains(element);
    }

    @Override
    public void add(E element) {
        int index = list.indexOf(element);
        if (index != List.ELEMENT_NOT_FOUND) { // 存在就覆蓋
            list.set(index, element);
        } else { // 不存在就添加
            list.add(element);
        }
    }

    @Override
    public void remove(E element) {
        int index = list.indexOf(element);
        if (index != List.ELEMENT_NOT_FOUND) {
            list.remove(index);
        }
    }

    @Override
    public void traversal(Visitor<E> visitor) {
        if (visitor == null) return;
        
        int size = list.size();
        for (int i = 0; i < size; i++) {
            if (visitor.visit(list.get(i))) return;
        }
    }
}
紅黑樹實(shí)現(xiàn)集合
package alangeit.set;

// 紅黑樹實(shí)現(xiàn)集合

import java.util.Comparator;

import alangeit.tree.BinaryTree;
import alangeit.tree.RBTree;

public class TreeSet<E> implements Set<E> {
    private RBTree<E> tree;
    
    public TreeSet() {
        this(null);
    }
    
    public TreeSet(Comparator<E> comparator) {
        tree = new RBTree<>(comparator);
    }
    
    @Override
    public int size() {
        return tree.size();
    }

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

    @Override
    public void clear() {
        tree.clear();
    }

    @Override
    public boolean contains(E element) {
        return tree.contains(element);
    }

    @Override
    public void add(E element) {
        tree.add(element);
    }

    @Override
    public void remove(E element) {
        tree.remove(element);
    }

    @Override
    public void traversal(Visitor<E> visitor) {
        tree.inorder(new BinaryTree.Visitor<E>() {
            @Override
            public boolean visit(E element) {
                return visitor.visit(element);
            }
        });
    }

}

// 紅黑樹實(shí)現(xiàn)集合
static void test2() {
    System.out.println("--------------------------------------- 紅黑樹實(shí)現(xiàn)集合");
    Set<Integer> treeSet = new TreeSet<>();
    treeSet.add(12);
    treeSet.add(10);
    treeSet.add(7);
    treeSet.add(11);
    treeSet.add(10);
    treeSet.add(11);
    treeSet.add(9);
    
    treeSet.traversal(new Visitor<Integer>() {
        @Override
        public boolean visit(Integer element) {
            System.out.println(element);
            return false;
        }
    });
}

作業(yè)

? 兩個(gè)數(shù)組的交集:https://leetcode-cn.com/problems/intersection-of-two-arrays/

映射(Map)

?Map 在有些編程語言中也叫做字典(dictionary，比如 Python、Objective-C、Swift 等) key value

?Map 的每一個(gè) key 是唯一的

Map的接口設(shè)計(jì)

public interface Map<K, V> {
    int size();
    boolean isEmpty();
    void clear();
    V put(K key, V value);// 添加
    V get(K key);
    V remove(K key);
    boolean containsKey(K key);
    boolean containsValue(V value);
    void traversal(Visitor<K, V> visitor);// 遍歷
    
    public static abstract class Visitor<K, V> {
        boolean stop;
        public abstract boolean visit(K key, V value);
    }
}

?類似 Set，Map 可以直接利用之前學(xué)習(xí)的鏈表、二叉搜索樹(AVL樹、紅黑樹)等數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)

Map.java

package alangeit.map;

public interface Map<K, V> {
    int size();
    boolean isEmpty();
    void clear();
    V put(K key, V value);// 添加
    V get(K key);
    V remove(K key);
    boolean containsKey(K key);
    boolean containsValue(V value);
    void traversal(Visitor<K, V> visitor);// 遍歷
    
    public static abstract class Visitor<K, V> {
        boolean stop;
        public abstract boolean visit(K key, V value);
    }
}

TreeMap.java

package alangeit.map;

// 紅黑樹實(shí)現(xiàn)映射

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

@SuppressWarnings({"unchecked", "unused"})
public class TreeMap<K, V> implements Map<K, V> {
    private static final boolean RED = false;
    private static final boolean BLACK = true;
    private int size;
    private Node<K, V> root;
    private Comparator<K> comparator;
    
    public TreeMap() {
        this(null);
    }
    
    public TreeMap(Comparator<K> comparator) {
        this.comparator = comparator;
    }
    
    public int size() {
        return size;
    }

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

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

    @Override
    public V put(K key, V value) {
        keyNotNullCheck(key);
        
        // 添加第一個(gè)節(jié)點(diǎn)
        if (root == null) {
            root = new Node<>(key, value, null);
            size++;

            // 新添加節(jié)點(diǎn)之后的處理
            afterPut(root);
            return null;
        }
        
        // 添加的不是第一個(gè)節(jié)點(diǎn)
        // 找到父節(jié)點(diǎn)
        Node<K, V> parent = root;
        Node<K, V> node = root;
        int cmp = 0;
        do {
            cmp = compare(key, node.key);
            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else { // 相等
                node.key = key;
                V oldValue = node.value;
                node.value = value;
                return oldValue;
            }
        } while (node != null);

        // 看看插入到父節(jié)點(diǎn)的哪個(gè)位置
        Node<K, V> newNode = new Node<>(key, value, parent);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        size++;
        
        // 新添加節(jié)點(diǎn)之后的處理
        afterPut(newNode);
        return null;
    }

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

    @Override
    public V remove(K key) {
        return remove(node(key));
    }

    @Override
    public boolean containsKey(K key) {
        return node(key) != null;
    }

    @Override
    public boolean containsValue(V value) {
        if (root == null) return false;
        
        Queue<Node<K, V>> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            Node<K, V> node = queue.poll();
            if (valEquals(value, node.value)) return true;
            
            if (node.left != null) {
                queue.offer(node.left);
            }
            
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        
        return false;
    }

    @Override
    public void traversal(Visitor<K, V> visitor) {
        if (visitor == null) return;
        traversal(root, visitor);
    }
    
    private void traversal(Node<K, V> node, Visitor<K, V> visitor) {
        if (node == null || visitor.stop) return;
        
        traversal(node.left, visitor);
        if (visitor.stop) return;
        visitor.visit(node.key, node.value);
        traversal(node.right, visitor);
    }
    
    private boolean valEquals(V v1, V v2) {
        return v1 == null ? v2 == null : v1.equals(v2);
    }
    
    private V remove(Node<K, V> node) {
        if (node == null) return null;
        
        size--;
        
        V oldValue = node.value;
        
        if (node.hasTwoChildren()) { // 度為2的節(jié)點(diǎn)
            // 找到后繼節(jié)點(diǎn)
            Node<K, V> s = successor(node);
            // 用后繼節(jié)點(diǎn)的值覆蓋度為2的節(jié)點(diǎn)的值
            node.key = s.key;
            node.value = s.value;
            // 刪除后繼節(jié)點(diǎn)
            node = s;
        }
        
        // 刪除node節(jié)點(diǎn)（node的度必然是1或者0）
        Node<K, V> replacement = node.left != null ? node.left : node.right;
        
        if (replacement != null) { // node是度為1的節(jié)點(diǎn)
            // 更改parent
            replacement.parent = node.parent;
            // 更改parent的left、right的指向
            if (node.parent == null) { // node是度為1的節(jié)點(diǎn)并且是根節(jié)點(diǎn)
                root = replacement;
            } else if (node == node.parent.left) {
                node.parent.left = replacement;
            } else { // node == node.parent.right
                node.parent.right = replacement;
            }
            
            // 刪除節(jié)點(diǎn)之后的處理
            afterRemove(replacement);
        } else if (node.parent == null) { // node是葉子節(jié)點(diǎn)并且是根節(jié)點(diǎn)
            root = null;
        } else { // node是葉子節(jié)點(diǎn)，但不是根節(jié)點(diǎn)
            if (node == node.parent.left) {
                node.parent.left = null;
            } else { // node == node.parent.right
                node.parent.right = null;
            }
            
            // 刪除節(jié)點(diǎn)之后的處理
            afterRemove(node);
        }
        
        return oldValue;
    }
    
    private void afterRemove(Node<K, V> node) {
        // 如果刪除的節(jié)點(diǎn)是紅色
        // 或者 用以取代刪除節(jié)點(diǎn)的子節(jié)點(diǎn)是紅色
        if (isRed(node)) {
            black(node);
            return;
        }
        
        Node<K, V> parent = node.parent;
        if (parent == null) return;
        
        // 刪除的是黑色葉子節(jié)點(diǎn)【下溢】
        // 判斷被刪除的node是左還是右
        boolean left = parent.left == null || node.isLeftChild();
        Node<K, V> sibling = left ? parent.right : parent.left;
        if (left) { // 被刪除的節(jié)點(diǎn)在左邊，兄弟節(jié)點(diǎn)在右邊
            if (isRed(sibling)) { // 兄弟節(jié)點(diǎn)是紅色
                black(sibling);
                red(parent);
                rotateLeft(parent);
                // 更換兄弟
                sibling = parent.right;
            }
            
            // 兄弟節(jié)點(diǎn)必然是黑色
            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                // 兄弟節(jié)點(diǎn)沒有1個(gè)紅色子節(jié)點(diǎn)，父節(jié)點(diǎn)要向下跟兄弟節(jié)點(diǎn)合并
                boolean parentBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if (parentBlack) {
                    afterRemove(parent);
                }
            } else { // 兄弟節(jié)點(diǎn)至少有1個(gè)紅色子節(jié)點(diǎn)，向兄弟節(jié)點(diǎn)借元素
                // 兄弟節(jié)點(diǎn)的左邊是黑色，兄弟要先旋轉(zhuǎn)
                if (isBlack(sibling.right)) {
                    rotateRight(sibling);
                    sibling = parent.right;
                }
                
                color(sibling, colorOf(parent));
                black(sibling.right);
                black(parent);
                rotateLeft(parent);
            }
        } else { // 被刪除的節(jié)點(diǎn)在右邊，兄弟節(jié)點(diǎn)在左邊
            if (isRed(sibling)) { // 兄弟節(jié)點(diǎn)是紅色
                black(sibling);
                red(parent);
                rotateRight(parent);
                // 更換兄弟
                sibling = parent.left;
            }
            
            // 兄弟節(jié)點(diǎn)必然是黑色
            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                // 兄弟節(jié)點(diǎn)沒有1個(gè)紅色子節(jié)點(diǎn)，父節(jié)點(diǎn)要向下跟兄弟節(jié)點(diǎn)合并
                boolean parentBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if (parentBlack) {
                    afterRemove(parent);
                }
            } else { // 兄弟節(jié)點(diǎn)至少有1個(gè)紅色子節(jié)點(diǎn)，向兄弟節(jié)點(diǎn)借元素
                // 兄弟節(jié)點(diǎn)的左邊是黑色，兄弟要先旋轉(zhuǎn)
                if (isBlack(sibling.left)) {
                    rotateLeft(sibling);
                    sibling = parent.left;
                }
                
                color(sibling, colorOf(parent));
                black(sibling.left);
                black(parent);
                rotateRight(parent);
            }
        }
    }

    private Node<K, V> predecessor(Node<K, V> node) {
        if (node == null) return null;
        
        // 前驅(qū)節(jié)點(diǎn)在左子樹當(dāng)中（left.right.right.right....）
        Node<K, V> p = node.left;
        if (p != null) {
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }
        
        // 從父節(jié)點(diǎn)、祖父節(jié)點(diǎn)中尋找前驅(qū)節(jié)點(diǎn)
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }

        // node.parent == null
        // node == node.parent.right
        return node.parent;
    }
    
    private Node<K, V> successor(Node<K, V> node) {
        if (node == null) return null;
        
        // 前驅(qū)節(jié)點(diǎn)在左子樹當(dāng)中（right.left.left.left....）
        Node<K, V> p = node.right;
        if (p != null) {
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }
        
        // 從父節(jié)點(diǎn)、祖父節(jié)點(diǎn)中尋找前驅(qū)節(jié)點(diǎn)
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }

        return node.parent;
    }
    
    private Node<K, V> node(K key) {
        Node<K, V> node = root;
        while (node != null) {
            int cmp = compare(key, node.key);
            if (cmp == 0) return node;
            if (cmp > 0) {
                node = node.right;
            } else { // cmp < 0
                node = node.left;
            }
        }
        return null;
    }
    
    private void afterPut(Node<K, V> node) {
        Node<K, V> parent = node.parent;
        
        // 添加的是根節(jié)點(diǎn) 或者 上溢到達(dá)了根節(jié)點(diǎn)
        if (parent == null) {
            black(node);
            return;
        }
        
        // 如果父節(jié)點(diǎn)是黑色，直接返回
        if (isBlack(parent)) return;
        
        // 叔父節(jié)點(diǎn)
        Node<K, V> uncle = parent.sibling();
        // 祖父節(jié)點(diǎn)
        Node<K, V> grand = red(parent.parent);
        if (isRed(uncle)) { // 叔父節(jié)點(diǎn)是紅色【B樹節(jié)點(diǎn)上溢】
            black(parent);
            black(uncle);
            // 把祖父節(jié)點(diǎn)當(dāng)做是新添加的節(jié)點(diǎn)
            afterPut(grand);
            return;
        }
        
        // 叔父節(jié)點(diǎn)不是紅色
        if (parent.isLeftChild()) { // L
            if (node.isLeftChild()) { // LL
                black(parent);
            } else { // LR
                black(node);
                rotateLeft(parent);
            }
            rotateRight(grand);
        } else { // R
            if (node.isLeftChild()) { // RL
                black(node);
                rotateRight(parent);
            } else { // RR
                black(parent);
            }
            rotateLeft(grand);
        }
    }
    
    private void rotateLeft(Node<K, V> grand) {
        Node<K, V> parent = grand.right;
        Node<K, V> child = parent.left;
        grand.right = child;
        parent.left = grand;
        afterRotate(grand, parent, child);
    }
    
    private void rotateRight(Node<K, V> grand) {
        Node<K, V> parent = grand.left;
        Node<K, V> child = parent.right;
        grand.left = child;
        parent.right = grand;
        afterRotate(grand, parent, child);
    }
    
    private void afterRotate(Node<K, V> grand, Node<K, V> parent, Node<K, V> child) {
        // 讓parent稱為子樹的根節(jié)點(diǎn)
        parent.parent = grand.parent;
        if (grand.isLeftChild()) {
            grand.parent.left = parent;
        } else if (grand.isRightChild()) {
            grand.parent.right = parent;
        } else { // grand是root節(jié)點(diǎn)
            root = parent;
        }
        
        // 更新child的parent
        if (child != null) {
            child.parent = grand;
        }
        
        // 更新grand的parent
        grand.parent = parent;
    }

    private Node<K, V> color(Node<K, V> node, boolean color) {
        if (node == null) return node;
        node.color = color;
        return node;
    }
    
    private Node<K, V> red(Node<K, V> node) {
        return color(node, RED);
    }
    
    private Node<K, V> black(Node<K, V> node) {
        return color(node, BLACK);
    }
    
    private boolean colorOf(Node<K, V> node) {
        return node == null ? BLACK : node.color;
    }
    
    private boolean isBlack(Node<K, V> node) {
        return colorOf(node) == BLACK;
    }
    
    private boolean isRed(Node<K, V> node) {
        return colorOf(node) == RED;
    }
    
    private int compare(K e1, K e2) {
        if (comparator != null) {
            return comparator.compare(e1, e2);
        }
        return ((Comparable<K>)e1).compareTo(e2);
    }
    
    private void keyNotNullCheck(K key) {
        if (key == null) {
            throw new IllegalArgumentException("key must not be null");
        }
    }

    private static class Node<K, V> {
        K key;
        V value;
        boolean color = RED;
        Node<K, V> left;
        Node<K, V> right;
        Node<K, V> parent;
        public Node(K key, V value, Node<K, V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
        
        public boolean isLeaf() {
            return left == null && right == null;
        }
        
        public boolean hasTwoChildren() {
            return left != null && right != null;
        }
        
        public boolean isLeftChild() {
            return parent != null && this == parent.left;
        }
        
        public boolean isRightChild() {
            return parent != null && this == parent.right;
        }
        
        public Node<K, V> sibling() {
            if (isLeftChild()) {
                return parent.right;
            }
            
            if (isRightChild()) {
                return parent.left;
            }
            
            return null;
        }
    }
}

static void test1() {
    System.out.println("--------------------------------------- 映射 -- 紅黑樹實(shí)現(xiàn)");
    Map<String, Integer> map = new TreeMap<>();
    map.put("c", 2);
    map.put("a", 5);
    map.put("b", 6);
    map.put("a", 8);
    
    map.traversal(new Visitor<String, Integer>() {
        public boolean visit(String key, Integer value) {
            System.out.println(key + "_" + value);
            return false;
        }
    });
}

// 單詞量統(tǒng)計(jì)
static void test2() {

    System.out.println("--------------------------------------- 單詞量統(tǒng)計(jì)");
    
    FileInfo fileInfo = Files.read("/Users/alange/eclipse-workspace/08-紅黑樹/src/alangeit",
            new String[]{"java"});
    
    System.out.println("文件數(shù)量：" + fileInfo.getFiles());
    System.out.println("代碼行數(shù)：" + fileInfo.getLines());
    String[] words = fileInfo.words();
    System.out.println("單詞數(shù)量：" + words.length);
    
    Map<String, Integer> map = new TreeMap<>();
    for (int i = 0; i < words.length; i++) {
        Integer count = map.get(words[i]);
        count = (count == null) ? 1 : (count + 1);
        map.put(words[i], count);
    }
    
    map.traversal(new Visitor<String, Integer>() {
        public boolean visit(String key, Integer value) {
            System.out.println(key + "_" + value);
            return false;
        }
    });
}

Map 與 Set

?Map 的所有 key 組合在一起，其實(shí)就是一個(gè) Set

?因此，Set 可以間接利用 Map 來作內(nèi)部實(shí)現(xiàn)

Set.java

package alangeit.set;

public interface Set<E> {
    int size();
    boolean isEmpty();
    void clear();
    boolean contains(E element);
    void add(E element);
    void remove(E element);
    void traversal(Visitor<E> visitor);
    
    public static abstract class Visitor<E> {
        boolean stop;
        public abstract boolean visit(E element);
    }
}

TreeSet.java

package alangeit.set;

import alangeit.map.Map;
import alangeit.map.TreeMap;

public class TreeSet<E> implements Set<E> {
    Map<E, Object> map = new TreeMap<>(); 

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

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

    @Override
    public void clear() {
        map.clear();
    }

    @Override
    public boolean contains(E element) {
        return map.containsKey(element);
    }

    @Override
    public void add(E element) {
        map.put(element, null);
    }

    @Override
    public void remove(E element) {
        map.remove(element);
    }

    @Override
    public void traversal(Visitor<E> visitor) {
        map.traversal(new Map.Visitor<E, Object>() {
            public boolean visit(E key, Object value) {
                return visitor.visit(key);
            }
        });
    }

}

static void test() {
    
    Set<String> set = new TreeSet<>();
    set.add("c");
    set.add("b");
    set.add("c");
    set.add("c");
    set.add("a");
    
    set.traversal(new Set.Visitor<String>() {
        public boolean visit(String element) {
            System.out.println(element);
            return false;
        }
    });
}

TreeMap分析

? 時(shí)間復(fù)雜度(平均)
添加、刪除、搜索:O(logn)

?特點(diǎn)
Key 必須具備可比較性
元素的分布是有順序的

? 在實(shí)際應(yīng)用中，很多時(shí)候的需求
Map 中存儲(chǔ)的元素不需要講究順序
Map 中的 Key 不需要具備可比較性

?不考慮順序、不考慮 Key 的可比較性，Map 有更好的實(shí)現(xiàn)方案，平均時(shí)間復(fù)雜度可以達(dá)到 O(1)
那就是采取哈希表來實(shí)現(xiàn) Map

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容