Data Structure_二叉树_集合_堆_并查集_哈希表
Data Structure_二叉树_集合_堆_并查集_哈希表
前情提要——二叉树
二叉树之前已经提到过，二叉树这种数据结构只能有两个子数，一左一右。
叶子节点就是左右孩子都是空的，但是并不是每一颗树都像上图所示的那样这么规整，有些树树可以只有左孩子没有右孩子的。二叉树的节点一定会大于左节点的值小于右节点的值，每一个节点都要满足，所有每一个节点下面拿出来的树都可以作为一个二叉树。既然有大于等于了，那么这科树的元素一定要有可比较性才可以。
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