前情提要——二叉树

二叉树之前已经提到过，二叉树这种数据结构只能有两个子数，一左一右。

叶子节点就是左右孩子都是空的，但是并不是每一颗树都像上图所示的那样这么规整，有些树树可以只有左孩子没有右孩子的。二叉树的节点一定会大于左节点的值小于右节点的值，每一个节点都要满足，所有每一个节点下面拿出来的树都可以作为一个二叉树。既然有大于等于了，那么这科树的元素一定要有可比较性才可以。

Create a BST

package Tree.BST;

public class BST<E extends Comparable<E>> {
    /**
     * Binary Search Tree
     */

    private class Node {
        public E e;
        public Node left, right;

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

    private Node root;
    private int size;

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

    public int size(){
        return size;
    }

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

和上面描述的基本一致的。

Insert an element

插入一个元素也很简单，查看当前元素是否是大于或者小于节点元素，如果是大于，那么就右边递归即可，二叉树的插入非递归写法和链表很像。

    public void add(E e) {
        root = add(root, e);
    }

    private Node add(Node node, E e) {
        if (node == null) {
            size++;
            return new Node(e);
        }
        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        } else {
            node.right = add(node.right, e);
        }
        return node;
    }

Select an element

判断一个元素和查找一个元素算法基本一致，小于左边找，大于右边找即可。
···
public boolean contains(E e) {
return contains(root, e);
}

public boolean contains(Node node, E e) {
    if (node == null) {
        return false;
    } else if (e.equals(node.e)) {
        return true;
    } else if (e.compareTo(node.e) < 0) {
        return contains(node.left, e);
    } else {
        return contains(node.right, e);
    }
}

···

Traversal

前中后序遍历都很简单，代码和前面C++都都是一样的。对于中序遍历的非递归遍历。非递归遍历可以对比递归来实现，数据结构里面有递归属性的只有栈了，所以可以用栈来实现。先把根元素压进栈，由于前序遍历直接输出第一个遍历到到元素，所以先出栈输出之后再把出栈的元素的子节点压进去，要注意的是右孩子先压，左孩子再压，因为遍历的顺序是先遍历左边再遍历右边，以此类推，只到空为止。
递归处理很简单，几行就好了，主要繁琐到就是非递归遍历到过程，前序遍历的非递归。这个算算比较简单到，因为先遍历到是一开始遍历到到点，再依次是左右子树，没有倒叙过程，都是有顺序性到，所以可以直接用栈处理，先把跟节点扔进去，如果栈不为空，那么就要出栈，直接输出当前元素，在放入左右子树即可，但是放入左右子树需要注意，应当先放入右子树再放入左子树，因为是先遍历左子树再遍历右子树，而栈是反过来的。

public void preOrderNonRecur() {
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            System.out.print(node.e + " ");
            if (node.right != null)
                stack.push(node.right);
            if (node.left != null)
                stack.push(node.left);
        }
        System.out.println();
    }

这就是前序遍历。中序的非递归遍历就有点复杂了，中序遍历是左中右，这个时候顺序就不是都往下了，没有办法一次性就遍历完，栈里面一开始存储都应该是遍历一开始要拿出来输出都元素，所以可以先把左边子树都遍历完存到栈里面，然后以这些存到栈里面的元素为起点遍历下去。每次出来一个元素都要看看这个元素的右子树是否存在，如果存在就要遍历，但其实不必要这样判断，因为算法前面的大循环已经判断了。

    public void inOrderNonRecur() {
        Stack<Node> stack = new Stack<>();
        Node node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()) {
                Node node1 = stack.pop();
                System.out.print(node1.e + " ");
                node = node1.right;
            }
        }
        System.out.println();

    

对于后序遍历就是最复杂的了，由于后序遍历和前序遍历都是逆的，所以一开始也要先把左子树放到栈里面，出的时候在看看有没有右子树。但是这里有个问题，这里的右子树是先输出再到当前节点的，首先要拿到当前节点，然后再看看右子树有没有，有就遍历，等右子树遍历完之后当前节点还在栈里面，这个时候再拿出来的还是当前节点，这个时候就不知道右子树有没有被遍历过了，这就进入到了一个死循环，所以这里要使用一个标记来看看有没有访问了右子树，如果访问了右子树，就可以放心输出了，因为while循环的时候已经到了最左边的了，这个时候不会再有左子树，只需要考虑右子树即可。

public void lastOrderNonRecur() {
        Stack<Node> stack = new Stack<>();
        Node node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()) {
                Node node1 = stack.peek();
                if (!node1.isright) {
                    node1.isright = true;
                    node = node1.right;
                } else {
                    node = stack.pop();
                    System.out.print(node.e + " ");
                    node = null;
                }
            }
        }
        System.out.println();
    }

中序遍历和后序遍历都从左边扩散到右边。
最后一个就是层序遍历，层序遍历就是广度优先遍历，实现用队列就好了，事实上大多数的广度优先遍历基本都是要使用队列的。之前的数据结构说过，直接给出代码即可：

levelOrder(){
        Queue<Node> nodes = new LinkedList<>();
        nodes.add(root);
        while (!nodes.isEmpty()){
            Node node = nodes.remove();
            System.out.print(node.e + " ");
            if (node.left != null){
                nodes.add(node.left);
            }
            if (node.right != null){
                nodes.add(node.right);
            }
        }
        System.out.println();
    }

remove an specific element

删除一个元素有点麻烦，如果只有一边有元素，那么就只需要把一边的移动上去替代即可，如果两边都有子树，那么就需要把右子树最小的一个移动上去，当然，其实也可以把左子树最大的移动上去，替代原来的即可。

    private Node remove(Node node, E e) {
        if (node == null) {
            return null;
        } else if (e.compareTo(node.e) < 0) {
            node.left = remove(node.left, e);
            return node;
        } else if (e.compareTo(node.e) > 0) {
            node.right = remove(node.right, e);
            return node;
        } else{
            if (node.left == null){
                Node node1 = node.right;
                node.right = null;
                size--;
                return node1;
            }else if (node.right == null){
                Node node1 = node.left;
                node.left = null;
                size--;
                return node1;
            }else {
                Node successor = new Node(minimum(node.right).e);
                successor.left = node.left;
                successor.right = removeMin(node.right);
                node.left = node.right = null;
                return successor;
            }
        }

    }

集合Set

集合这种数据结构有点像高中数学那种集合，集合有一个特点，就是每一个元素只能有一个，这个性质可以用来做去重工作。再上面实现的二分搜索树是不可以存放重复数据的，所以可以作为集合的一种底层实现方式。二叉树的实现是有要求的，要求一定要是二叉树的结构来实现，而集合只是要求有这么多功能就OK，所以集合属于一种高级数据结构，没有具体实现方法。

集合基本方法

Set创建一个集合，remove移除集合的一个元素，contains查看集合是否包含这个元素，getSize获得集合大小，isEmpty查看集合是否为空，add添加一个元素，不能添加重复的元素。
集合的应用很广，访问量的统计，词汇量的统计等等都可以用到集合去重。首先是基于BST的集合，上面实现的BST完全包含了集合的功能。直接包装一下即可。

Leecode804

Leecode804，摩斯码的判断：

这个题目非常简单，直接替换一下扔到集合里面就好了，这里使用的就是treeSet，是使用的红黑树实现方式：

class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String [] codes = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        TreeSet<String> set = new TreeSet<>();
        for (String word : words){
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < word.length(); i++) {
                stringBuilder.append(codes[word.charAt(i) - 'a']);
            }
            set.add(stringBuilder.toString());
        }
        return set.size();
    }
}

之前所实现的集合，二分搜索树，红黑树这些实现的集合都是有顺序性的，因为这些结构实现的集合是很容易可以排序（中序遍历），找到下一个上一个等等，是属于有序集合，而链表这些就属于无序性的了。

优先队列和堆

堆的基本结构， 这里的堆实现也和树有关系，二叉堆。二叉堆是一个完全二叉树。

package Heap;

import Array.Array;

public class MaxHeap<E extends Comparable<E>> {
    private Array<E> data;

    public MaxHeap(int capacity) {
        data = new Array<E>(capacity);
    }

    public MaxHeap() {
        data = new Array<E>();
    }

    public int size() {
        return data.getSize();
    }

    public boolean isEmpty() {
        return data.isEmpty();
    }

    private int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("No parents when index equal zero!");
        }
        return (index - 1) / 2;
    }

    private int leftChild(int index) {
        return index * 2 + 1;
    }

    private int rightChild(int index) {
        return index * 2 + 2;
    }

    
}

堆的实现之前的C++有写过，对于插入一个元素，插入在数组的最后面,然后再按照规则慢慢的shiftUp上去，如果这个元素是大于它的父母，那么就要浮上去，然后以父母为当前元素继续循环判断：

    private void shiftUp(int index) {
        while (index > 0 && data.get(index).compareTo(data.get(parent(index))) > 0) {
            data.swap(index, parent(index));
            index = parent(index);
        }
    }

输出最大值的元素就只需要把第一个元素输出，把最后一个元素补上，再把新的第一个元素进行shiftDown操作：

    private void shiftDown(int index){
        while (leftChild(index) < data.getSize()){
            int j = leftChild(index);
            if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0){
                j = rightChild(index);
            }
            if (data.get(index).compareTo(data.get(j)) >= 0){
                break;
            }
            data.swap(index, j);
            index = j;
        }
    }

堆还有一个replace操作，取出最大值，用另一个值替代，可以先输出最大值，然后再添加另一个值，但是这样这样复杂度就是。可以直接用新的元素替换最大值，然后做shiftDown操作即可。

    public E replace(E e) {
        E max = data.get(0);
        data.set(0, e);
        shiftDown(0);
        return max;
    }

如果存在一个数组，想要直接在数组上操作，使得这个数组直接变成一个堆，那就需要heapify操作了。从最后一个叶子节点开始不断做shiftdown操作即可：

        for (int i = parent(this.data.getSize() - 1); i >= 0; i --){
            shiftDown(i);
        }

基于堆的优先队列就很简单了，出队列的时候就直接extract最大值即可。

优先队列347

给定一个数组，数组元素可以重复，那么数字就会出现重复这个问题，在这种情况下，就需要求出前N个频率最高的元素，这就有点像优先队列了。先用Treemap把频率存储到树里面，然后放到优先队列里面输出即可：

package Queue.Leecode347;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.TreeMap;

class Solution {

    private class Freq implements Comparable<Freq>{

        int e, freq;

        public Freq(int e, int freq){
            this.e = e;
            this.freq = freq;
        }

        @Override
        public int compareTo(Freq another) {
            if (this.freq < another.freq){
                return -1;
            }
            else if (this.freq > another.freq){
                return 1;
            }else {
                return 0;
            }
        }

    }

    public List<Integer> topKFrequent(int[] nums, int k) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int n : nums) {
            if (map.containsKey(n)) {
                map.put(n, map.get(n) + 1);
            } else {
                map.put(n, 1);
            }
        }

        PriorityQueue<Freq> priorityQueue = new PriorityQueue<>();
        for(int key: map.keySet()){
            if(priorityQueue.size() < k)
                priorityQueue.add(new Freq(key, map.get(key)));
            else if(map.get(key) > priorityQueue.peek().freq){
                priorityQueue.remove();
                priorityQueue.add(new Freq(key, map.get(key)));
            }
        }
        List<Integer> linkedList = new LinkedList<>();
        while (!priorityQueue.isEmpty()){
            linkedList.add(priorityQueue.remove().e);
        }
        return linkedList;
    }

    public static void main(String[] args) {
        int[] nums = {1,1,1,2,2,3};
        Solution solution = new Solution();
        System.out.println(solution.topKFrequent(nums, 2));
    }

}

并查集

之前包括前面博客所讨论的树问题都是树问题，这些树问题都是由父亲指向孩子，而这个并查集是孩子指向树，可以由孩子找到跟节点。并查集可以用来回答连接问题。给出两个点，看看这两个点是否是连接的。前面博客提到的就是找到根然后比较两个根是不是一样的即可。这里的并查集主要实现两个操作，Union和isConnected，连接两个节点和查看两个节点是否是连接的。

并查集Quick Find

每个元素的下标都会有一个标记，如果标记相同那么就是同一个类别，也就是连接在了一起。一开始每一个数字就是一个类别，所以一开始下标都是不一样的。

    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p is out of range!");
        }
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

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

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot){
            return;
        }
        parent[pRoot] = qRoot;
    }

这种情况下的的查找复杂度是很快的，但是合并就很慢了，需要的复杂度。

基于树的Quick union

每一个节点都指向上一个节点，最后指向的就是根，根的parent就是他自己，如果根相同，那么这两个节点就是相同的。

    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p is out of range!");
        }
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

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

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot){
            return;
        }
        parent[pRoot] = qRoot;
    }

合并的时候直接把根节点合并就好了。但是这种合并有个弊端，如果合并的时候恰好把大的哪一组数据合并到了小的哪一组数据上，就容易出现类似链表那样长长的数据段，这个时候就可以先做判断，看看哪一边的数据量大就把小数据的合并到大的一边去即可。所以就需要一个记录数量的数组。

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        if (sz[pRoot] < sz[qRoot]) {
            parent[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }else {
            parent[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
    }

其他都是一样的。这样其实不太严谨，如果数据都是分散开的，那么就应该反着过来，所以应该以高度作为对比的条件:

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        if (rank[pRoot] < rank[qRoot]){
            parent[pRoot] = qRoot;
        }else if (rank[pRoot] > rank[qRoot]){
            parent[qRoot] = pRoot;
        }else {
            parent[qRoot] = pRoot;
            rank[pRoot] += 1;
        }

路径压缩 Path Compression

如果这个并查集已经被压缩成了长条型，就需要使用路径压缩来优化了：

这种情况下就只需要指向父亲的父亲即可，只要加上一行代码就可以。

    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p is out of range!");
        }
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

哈希表HashTable

首先看一个简单的问题：

返回第一个不重复的字符。最简单的处理方式就是使用一个映射，先计算一遍所有字符的频率是多少，然后再遍历一遍所有的字符，看看第一个字符出现次数为一是索引下标是多少即可。
但是这样比较麻烦，我们可以使用一个数组包含了二十六个字母。

class Solution {
    public int firstUniqChar(String s) {
        int[] freq = new int[26];
        for (int i = 0; i < s.length(); i++) {
            freq[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            if (freq[s.charAt(i) - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }
}

在这个问题就隐藏着哈希表这种数据结构。上面的frequency数组就是一个哈希表，每一个字符都和一个索引对应。数组的查找是支持下表操作的，所有复杂度可以是的复杂度。哈希其实就是使用一个下标来指示一个数值或者是字符，然后解决哈希冲突。简单的来说，哈希就体现了用空间换时间的思想。
键通过哈希函数得到的索引分布越均匀越好。对于一些特殊的领域，有特殊领域的哈希函数设计方式甚至有专门的论文。
首先是整型哈希函数的设计，小范围整数直接使用，负整数就要进行偏移。对于大整数，就需要对这个大整数进行处理，使得变成一个计算机可以处理的数据。常用的方法就是取模了。但是有时候取模使得分布不会有均匀的分布，所以可以使用素数作为取模数值。
对于字符串的处理，就需要转成整型处理

在Java里面的HashCode是以整型为基准的，他只是给出了hashcode，索引下标还是需要其他的计算。

hash冲突——链地址法

如果没有冲突，那么就按照下标直接存放，如果产生了冲突，也就是一个索引下有两个相同的哈希值，那么就用链表把他们都串起来，如果还是有相同的那么继续接上，所以每一个空间等于是存上了一个链表，也就是一个查找表，既然是查找表那么久不一定是链表了，可以是树结构，红黑树二叉树都可以。在Java8之前，一直都是一个位置对应一个链表，Java8开始如果冲突达到了一定程度，也就是链表里面元素过多了，那么就会把每一个位置自动转成红黑树。因为如果在数据量少的情况下，使用链表查找是更加快的，因为没有红黑树的维护过程，而数据量多的时候就需要使用红黑树了。

public class Hash_Table<K, V> {
    private TreeMap<K, V>[] hashtable;
    private int M;
    private int size;

    public Hash_Table(int M) {
        this.M = M;
        size = 0;
        hashtable = new TreeMap[M];
        for (int i = 0; i < hashtable.length; i++) {
            hashtable[i] = new TreeMap<>();
        }
    }

    public Hash_Table() {
        this(97);
    }

    private int hash(K key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    public int getSize() {
        return size;
    }

    public void add(K key, V value) {
        if (hashtable[hash(key)].containsKey(key)) {
            hashtable[hash(key)].put(key, value);
        } else {
            hashtable[hash(key)].put(key, value);
            size++;
        }
    }

    public V remove(K key){
        TreeMap<K, V> treeMap = hashtable[hash(key)];
        V ret = null;
        if (treeMap.containsKey(key)){
            ret = treeMap.remove(key);
            size--;
        }
        return ret;
    }

    public void set(K key, V value){
        TreeMap<K, V> treeMap = hashtable[hash(key)];
        if (!treeMap.containsKey(key)){
            throw new IllegalArgumentException("no element!");
        }else {
            treeMap.put(key, value);
        }
    }

    public boolean contains(K key){
        return hashtable[hash(key)].containsKey(key);
    }

    public V get(K key){
        return hashtable[hash(key)].get(key);
    }
}

每一个位置都使用红黑树，插入的数据带键值和数据，根据键值取哈希值然后求余。过程很简单。如果插入的数据是N个，哈希表大小是M，如果每一个位置是链表的话，那么平均复杂度就是，如果是平衡树就是。可以看到这个复杂度并没有如期望的那样，因为这是一个静态数组，当N大于M的时候那么就会趋向N了，复杂度就会回到链表的查找。所以可以考虑使用动态数组的方法进行扩展。也就是让M产生变化，当N/M大于一定元素的时候就需要进行扩容，改变M了，当插入数据过少那么久可以缩荣。
首先就是要实现一个resize方法了：

    private void resize(int capacity){
        TreeMap<K, V>[] newHashTable = new TreeMap[capacity];
        for (int i = 0; i < capacity; i++) {
            newHashTable[i] = new TreeMap<>();
        }
        int oldM = this.M;
        this.M = capacity;
        for (int i = 0; i < oldM; i++) {
            TreeMap<K, V> treeMap = hashtable[i];
            for (K key : treeMap.keySet()){
                newHashTable[hash(key)].put(key, treeMap.get(key));
            }
        }

        this.hashtable = newHashTable;
    }

注意到M和新的M之间有一个陷阱，hash中用的是原来的M，而遍历的时候要遍历的是原来的M，所以应该要保存一份。之后就只需要在添加和移除两个操作修改容量即可。
由于均摊复杂度是由决定的，所以复杂度是在。但事实上这样扩容还有一个问题，乘上两倍之后M就不是素数了，所以动态扩容的时候还需要选取素数的问题。
哈希表的均摊复杂度那么久接近于，很快，但是得到了什么就会失去了什么，这里哈希表久牺牲了顺序性，树结构都是有顺序性的，所以稍微慢一点。哈希表其实也是一个集合，有序集合可以用树结构作为底层数据结构来实现，无序集合可以用哈希表来实现。

hash冲突——开放地址法

如果遇到了冲突，那么就用线性探测的方法，加一看看有没有空的，没有继续加一。但是这样效率有时候是很低的，这里就可以采用类似计算机网络里面的碰撞检测方法，平方探测，一开始是1，又冲突了就4，9，16这样既可。另外还可以使用二次哈希的方法。

最后附上所有GitHub代码：https://github.com/GreenArrow2017/DataStructure_Java