【每日算法Day 53】特殊数据结构1

已经来到七月下旬，按照Cspiration的分类已经基本完成一遍算法题，相较开始之前在LeetCode上又增加了一百多道。这个过程中确实有不少算法和数据结构给我留下了深刻的印象，不过他们都说要刷200道以上才能有感觉，现在我可能是只有一丢丢感觉吧，继续加油~今天就来整理下一些如果掌握得好能很加分的数据结构。

红黑树

一般的二叉查找树在遇到一些极端的情况会退化成线性解构，插入和查找的时间消耗都会变为O(n)。为了解决这个问题，出现了一些自平衡的BST，例如AVL树就是一种高度平衡的BST，其所有节点的两个子树高度之差不会超过1。而红黑树是一种局部平衡的BST，其要求没有那么严格，允许最高子树的高度最多达到最低子树高度的两倍。两者的平均查找和插入时间复杂度都为O(logn)，AVL树的查找性能理论上略高于红黑树，红黑树在插入节点时由于不需要做太多的旋转理论插入性能更好并且逻辑更易于实现。JDK1.8中HashMap、TreeSet底层就用到了红黑树。

红黑树的特点：

1. 节点非黑即红，叶子节点（NIL）为黑色，根节点为黑色
2. 红色节点的孩子节点一定得是黑色的
3. 从任意节点开始到其所有叶子节点的路径上包含相同数量的黑色节点（计算时不包括节点本身，包括NIL节点）【这也保证了最长路径不超过最短路径的2倍，最短全为黑，最长红黑相间】

在构建树插入节点时，利用BST性质找到插入位置，默认新插入的节点是红色。在插入时有时就会对上面的特性造成冲突，那么插入时就需要检查冲突并作出相应调整。

0. 如果插入点本身就是根节点则颜色变为黑色。
1. 如果插入点的父亲节点为黑色节点则什么都不用做。
2. 如果插入点的父亲节点为红色节点则产生冲突，这是需要根据插入点的uncle节点作出调整：
   1. 如果uncle节点为红色节点，则改变父亲节点、叔叔节点、祖父节点的颜色，并针对祖父节点继续向上检查冲突。
   2. 如果uncle节点为黑色节点，且祖父节点、父亲节点、插入节点构成一个直角，则需要对父亲节点进行旋转。这时如果插入节点为父亲节点的左孩子则进行右旋，反之则进行左旋。旋转后针对父亲节点继续向上检查冲突。
   3. 如果uncle节点为黑色节点，且祖父节点、父亲节点、插入节点构成一条直线，则需要对祖父节点进行旋转。这时如果插入节点时父亲节点的左孩子则进行右旋，反之则进行左旋。还需要改变祖父节点、父亲节点的颜色并从祖父节点开始继续向上检查错误。

BST左旋伪代码：

红黑树的插入与冲突矫正：

LRU缓存

设计LRU缓存（最近最少被使用），为实现O(1)时间内的访问需要使用哈希表，为保存记录插入或者访问的顺序需要使用双向链表。JDK中提供了LinkedHashMap，其默认使用插入顺序组织节点。我们要自定义一个LRU缓存，可以继承该类并通过重写。

import java.util.LinkedHashMap;
import java.util.Map;

public class No146_LRUCache extends LinkedHashMap<String, String> {
    private int capacity;

    public No146_LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    public String get(String key) {
        return super.get(key);
    }

    public String put(String key, String value) {
        return super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > capacity;
    }
}

不过我们可以自己设计双向链表中的Node节点，节点包含key,value,prev,next，并以节点的key为key，节点对象为value插入到哈希表中。

public class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 添加进哈希表
            cache.put(key, newNode);
            // 添加至双向链表的头部
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode tail = removeTail();
                // 删除哈希表中对应的项
                cache.remove(tail.key);
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

并查集

并查集的核心是使用数组来表示森林，主要用来表示连通性关系。核心在于find方法中寻找根节点时的路径压缩和union方法中合并两棵树时按照根节点的秩（树的高度）来合并。

class UF {
    // 连通分量个数
    private int count;
    // 存储一棵树
    private int[] parent;
    // 记录树的“重量”
    private int[] size;

    public UF(int n) {
        this.count = n;
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;

        // 小树接到大树下面，按秩合并
        if (size[rootP] > size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        } else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        count--;
    }

    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    private int find(int x) {
        while (parent[x] != x) {
            // 进行路径压缩
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    public int count() {
        return count;
    }
}