- 数组封装
接口
public interface Array<T> { T[] getData(); int getSize(); int getCapacity(); boolean isEmpty(); void addLast(T t); void addFirst(T t); void add(int index, T t); T get(int index); T getLast(); T getFirst(); void set(int index, T t); boolean contains(T t); int find(T t); void removeElement(T t); T remove(int index); T removeFirst(); T removeLast(); /** * 交换两个索引的元素的位置 * @param i * @param j */ void swap(int i,int j); }
实现类
public class DefaultArray<T> implements Array<T> { private static final int factor = 2; private T[] data; private int size; @SuppressWarnings("unchecked") public DefaultArray(int capacity) { data = (T[]) new Object[capacity]; size = 0; } public DefaultArray() { this(20); } @SuppressWarnings("unchecked") public DefaultArray(T[] data) { this.data = (T[]) new Object[data.length + 1]; for (int i = 0;i < data.length;i++) { this.data[i] = data[i]; } this.size = data.length; } @Override public T[] getData() { return data; } @Override public int getSize() { return size; } @Override public int getCapacity() { return data.length; } @Override public boolean isEmpty() { return size == 0; } @Override public void addLast(T value) { add(size,value); } @Override public void addFirst(T value) { add(0,value); } @Override public void add(int index,T value) { if (index < 0 || index > size) { throw new IllegalArgumentException("添加失败，要求index >=0且index<=size"); } for (int i = size;i > index;i--) { data[i] = data[i - 1]; } data[index] = value; size++; if (size == data.length) { resize(getCapacity() * factor); } } @Override public T get(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("获取失败，index参数错误"); } return data[index]; } @Override public T getLast() { return get(size - 1); } @Override public T getFirst() { return get(0); } @Override public void set(int index,T value) { if (index < 0 || index >= size) { throw new IllegalArgumentException("设置失败，index参数错误"); } data[index] = value; } @Override public boolean contains(T value) { for (int i = 0;i < size;i++) { if (data[i].equals(value)) { return true; } } return false; } @Override public int find(T value) { for (int i = 0;i < size;i++) { if (data[i].equals(value)) { return i; } } return -1; } @Override public void removeElement(T value) { int index = find(value); if (index != -1) { remove(index); } } @Override public T remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("移除失败，index参数错误"); } T ret = data[index]; for (int i = index;i < size;i++) { data[i] = data[i + 1]; } size--; if (size <= getCapacity() / 4 && getCapacity() / 2 != 0) { resize(getCapacity() / factor); } return ret; } @Override public T removeFirst() { return remove(0); } @Override public T removeLast() { return remove(size - 1); } @Override public void swap(int i, int j) { if (i < 0 || i >= size || j < 0 || j >= size) { throw new IllegalArgumentException("索引非法"); } T temp = data[i]; data[i] = data[j]; data[j] = temp; } @SuppressWarnings("unchecked") private void resize(int capacity) { if (capacity == size) { capacity++; } T[] newData = (T[]) new Object[capacity]; for (int i = 0;i < size;i++) { newData[i] = data[i]; } data = newData; } @Override public String toString() { StringBuilder builder = new StringBuilder(); builder.append("DefaultArray(data=["); for (int i = 0;i < size - 1;i++) { builder.append(data[i] + ","); } builder.append(data[size -1] + "], size=" + size); return builder.toString(); } }
调用
public class ArrayMain { public static void main(String[] args) { Array<Integer> array = new DefaultArray<>(3); array.addLast(66); array.addLast(99); array.addLast(88); System.out.println(array); array.add(1,77); array.addFirst(100); array.set(4,11); array.remove(2); System.out.println(array); System.out.println(array.get(3)); array.remove(1); array.removeFirst(); array.removeFirst(); System.out.println(array); } }
运行结果
DefaultArray(data=[66,99,88], size=3
DefaultArray(data=[100,66,99,11], size=4
11
DefaultArray(data=[11], size=1
- 时间复杂度的简单示例
O(n) 线性关系计算
计算整形数组的和
@FunctionalInterface public interface On { int compute(Integer[] nums); }
public class SumOn { public int sum(Array<Integer> array,On on) { return on.compute(array.getData()); } }
public class Main { public static void main(String[] args) { Array<Integer> array = new DefaultArray<>(new Integer[]{1,2,3,4,5,6,7}); SumOn sumOn = new SumOn(); int sum = sumOn.sum(array, nums -> Stream.of(nums).reduce((x, y) -> x + y).get()); System.out.println(sum); } }
运行结果
28
线性方程: T = c1*n + c2,而O(n)指的是忽略常数c1,c2。如以下关系，无论计算中有具体多少步执行
T = 2*n + 2 O(n)
T = 2000*n + 10000 O(n) 渐进时间复杂度
T = 1*n*n +0 O(n^2) 虽然这里的常数很小，描述n趋近于无穷的情况
T = 2*n*n + 300*n + 10 O(n^2) 低阶项300*n会被忽略
对于Array各操作的时间复杂度
添加操作
addLast(value) O(1)
addFirst(value) O(n)
add(index,value) 严格计算需要概率论，平均来说 O(n/2) = O(n)
从整体上看，添加操作是一个O(n)级别的时间复杂度
扩容
resize O(n)
删除操作
removeLast() O(1)
removeFirst() O(n)
remove(index) O(n/2) = O(n)
从整体上看，删除操作是一个O(n)级别的时间复杂度
缩容
resize O(n)
修改操作
set(index,value) O(1)
swap(i,j) O(1)
查找操作
get(index) O(1)
contains(value) O(n)
find(value) O(n)
- 数组栈封装
栈是数组的子集，是一种后进先出的数据结构
接口
public interface Stack<T> { /** * 入栈 * @param t */ void push(T t); /** * 出栈 * @return */ T pop(); /** * 获取栈顶元素 * @return */ T peek(); int getSize(); boolean isEmpty(); }
实现类
@ToString public class ArrayStack<T> implements Stack<T> { private Array<T> array; public ArrayStack(int capacity) { array = new DefaultArray<>(capacity); } public ArrayStack() { array = new DefaultArray<>(); } @Override public void push(T value) { array.addLast(value); } @Override public T pop() { return array.removeLast(); } @Override public T peek() { return array.getLast(); } @Override public int getSize() { return array.getSize(); } @Override public boolean isEmpty() { return array.isEmpty(); } public int getCapacity() { return array.getCapacity(); } }
调用
public class StackMain { public static void main(String[] args) { Stack<Integer> stack = new ArrayStack<>(5); for (int i = 0;i < 5;i++) { stack.push(i); System.out.println(stack); } stack.pop(); System.out.println(stack); } }
运行结果
ArrayStack(array=DefaultArray(data=[0], size=1)
ArrayStack(array=DefaultArray(data=[0,1], size=2)
ArrayStack(array=DefaultArray(data=[0,1,2], size=3)
ArrayStack(array=DefaultArray(data=[0,1,2,3], size=4)
ArrayStack(array=DefaultArray(data=[0,1,2,3,4], size=5)
ArrayStack(array=DefaultArray(data=[0,1,2,3], size=4)
对于Stack各操作的时间复杂度
- push(value) O(1) 均摊
- Pop() O(1) 均摊
- peek() O(1)
- getSize() O(1)
- isEmpty() O(1)
LeetCode算法题 https://leetcode-cn.com/problems/valid-parentheses/
这是LeetCode的第20题——有效的括号
我们先用JDK的栈来完成，这里的Stack为java.util.Stack，该类继承于Vector
public class JavaSolution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); for (int i = 0;i < s.length();i++) { char c = s.charAt(i); if (c == '(' || c == '[' || c == '{') { stack.push(c); }else { if (stack.isEmpty()) { return false; } char topChar = stack.pop(); if (c == ')' && topChar != '(') { return false; } if (c == ']' && topChar != '[') { return false; } if (c == '}' && topChar != '{') { return false; } } } return stack.isEmpty(); } public static void main(String[] args) { JavaSolution solution = new JavaSolution(); String patten = "{}[()]"; System.out.println(solution.isValid(patten)); } }
运行结果
true
提交给LeetCode
当然我们也可以使用我们自己封装的栈对象来处理
public class Solution { public boolean isValid(String s) { Stack<Character> stack = new ArrayStack<>(); for (int i = 0;i < s.length();i++) { char c = s.charAt(i); if (c == '(' || c == '[' || c == '{') { stack.push(c); }else { if (stack.isEmpty()) { return false; } char topChar = stack.pop(); if (c == ')' && topChar != '(') { return false; } if (c == ']' && topChar != '[') { return false; } if (c == '}' && topChar != '{') { return false; } } } return stack.isEmpty(); } public static void main(String[] args) { Solution solution = new Solution(); String patten = "{[()]}"; boolean valid = solution.isValid(patten); System.out.println(valid); } }
运行结果
true
- 数组队列封装
队列的操作是数组的子集，只能从一端添加元素(队尾)，从另一端取出元素(队首)，是一种先进先出的数据结构
接口
public interface Queue<T> { /** * 入队 * @param t */ void enqueue(T t); /** * 出队 * @return */ T dequeue(); /** * 获取队首元素 * @return */ T getFront(); int getSize(); boolean isEmpty(); }
实现类
@ToString public class ArrayQueue<T> implements Queue<T> { private Array<T> array; public ArrayQueue(int capacity) { array = new DefaultArray<>(capacity); } public ArrayQueue() { array = new DefaultArray<>(); } @Override public void enqueue(T value) { array.addLast(value); } @Override public T dequeue() { return array.removeFirst(); } @Override public T getFront() { return array.getFirst(); } @Override public int getSize() { return array.getSize(); } @Override public boolean isEmpty() { return array.isEmpty(); } public int getCapaticy() { return array.getCapacity(); } }
调用
public class QueueMain { public static void main(String[] args) { Queue<Integer> queue = new ArrayQueue<>(10); for (int i = 0;i < 10;i++) { queue.enqueue(i); System.out.println(queue); if (i % 3 == 2) { queue.dequeue(); System.out.println(queue); } } } }
运行结果
ArrayQueue(array=DefaultArray(data=[0], size=1)
ArrayQueue(array=DefaultArray(data=[0,1], size=2)
ArrayQueue(array=DefaultArray(data=[0,1,2], size=3)
ArrayQueue(array=DefaultArray(data=[1,2], size=2)
ArrayQueue(array=DefaultArray(data=[1,2,3], size=3)
ArrayQueue(array=DefaultArray(data=[1,2,3,4], size=4)
ArrayQueue(array=DefaultArray(data=[1,2,3,4,5], size=5)
ArrayQueue(array=DefaultArray(data=[2,3,4,5], size=4)
ArrayQueue(array=DefaultArray(data=[2,3,4,5,6], size=5)
ArrayQueue(array=DefaultArray(data=[2,3,4,5,6,7], size=6)
ArrayQueue(array=DefaultArray(data=[2,3,4,5,6,7,8], size=7)
ArrayQueue(array=DefaultArray(data=[3,4,5,6,7,8], size=6)
ArrayQueue(array=DefaultArray(data=[3,4,5,6,7,8,9], size=7)
ArrayQueue(array=DefaultArray(data=[3,4,5,6,7,8,9,10], size=8)
对于ArrayQueue操作的时间复杂度
enqueue(value) O(1) 均摊
dequeue() O(n)
getFront() O(1)
getSize() O(1)
isEmpty() O(1)
鉴于数组队列每一次出队都会将队列中的所有元素前移，时间复杂度为O(n)，所以为了克制这种情况，我们需要构建一个循环队列，把数组看成首尾相接的一个环，出队时无需移动队列中的元素。此时将不再复用Array的实现。
- 循环队列封装
实现类
public class LoopQueue<T> implements Queue<T> { private T[] data; /** * 循环队列队首 */ private int front; /** * 循环队列队尾 */ private int tail; /** * 循环队列成员数量 */ private int size; /** * 扩容因子 */ private static final int factor = 2; @SuppressWarnings("unchecked") public LoopQueue(int capacity) { data = (T[]) new Object[capacity + 1]; front = tail = 0; size = 0; } public LoopQueue() { this(20); } public int getCapacity() { return data.length - 1; } @Override public void enqueue(T value) { //判断队列是否已满 if ((tail + 1) % data.length == front) { resize(getCapacity() * factor); } data[tail] = value; tail = (tail + 1) % data.length; size++; } @Override public T dequeue() { if (isEmpty()) { throw new IllegalArgumentException("无法从空队列出队"); } T ret = data[front]; data[front] = null; front = (front + 1) % data.length; size--; if (size <= getCapacity() / 4 && getCapacity() / 2 != 0) { resize(getCapacity() / factor); } return ret; } @Override public T getFront() { if (isEmpty()) { throw new IllegalArgumentException("队列为空"); } return data[front]; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return front == tail; } @SuppressWarnings("unchecked") private void resize(int capacity) { T[] newData = (T[]) new Object[capacity + 1]; for (int i = 0;i < size;i++) { //将老数组的元素放入新数组时，将重新将0定位新数组的front newData[i] = data[(front + i) % data.length]; } data = newData; front = 0; tail = size; } @Override public String toString() { StringBuilder builder = new StringBuilder(); builder.append("LoopQueue{data=["); for (int i = 0;i < size - 1;i++) { builder.append(data[(front + i) % data.length] + ","); } builder.append(data[(tail - 1) % data.length] + "], size=" + size); return builder.toString(); } }
调用
public class QueueMain { public static void main(String[] args) { Queue<Integer> queue = new LoopQueue<>(7); for (int i = 0;i <= 10;i++) { queue.enqueue(i); System.out.println(queue); if (i % 3 == 2) { queue.dequeue(); System.out.println(queue); } } } }
运行结果
LoopQueue{data=[0], size=1
LoopQueue{data=[0,1], size=2
LoopQueue{data=[0,1,2], size=3
LoopQueue{data=[1,2], size=2
LoopQueue{data=[1,2,3], size=3
LoopQueue{data=[1,2,3,4], size=4
LoopQueue{data=[1,2,3,4,5], size=5
LoopQueue{data=[2,3,4,5], size=4
LoopQueue{data=[2,3,4,5,6], size=5
LoopQueue{data=[2,3,4,5,6,7], size=6
LoopQueue{data=[2,3,4,5,6,7,8], size=7
LoopQueue{data=[3,4,5,6,7,8], size=6
LoopQueue{data=[3,4,5,6,7,8,9], size=7
LoopQueue{data=[3,4,5,6,7,8,9,10], size=8
对于LoopQueue操作的时间复杂度
enqueue(value) O(1) 均摊
dequeue() O(1) 均摊
getFront() O(1)
getSize() O(1)
isEmpty() O(1)
两种队列的性能测试
public class TestQueueMain { private static double testQueue(Queue<Integer> q,int opCount) { long startTime = System.nanoTime(); Random random = new Random(); for (int i = 0;i < opCount;i++) { q.enqueue(random.nextInt(Integer.MAX_VALUE)); } for (int i = 0;i < opCount;i++) { q.dequeue(); } long endTime = System.nanoTime(); return (endTime - startTime) / 1000000000.0; } public static void main(String[] args) { int opCount = 100000; Queue<Integer> arrayQueue = new ArrayQueue<>(); double time1 = testQueue(arrayQueue,opCount); System.out.println("ArrayQueue,time: " + time1 + " s"); Queue<Integer> loopQueue = new LoopQueue<>(); double time2 = testQueue(loopQueue,opCount); System.out.println("LoopQueue,time: " + time2 + " s"); } }
测试结果
ArrayQueue,time: 2.737708686 s
LoopQueue,time: 0.011393786 s
- 单向链表封装
之前的动态数组，栈，队列都是底层依托静态数组，靠resize()解决固定容量问题，而链表是真正的动态数据结构，不需要处理固定容量的问题。但缺点也很明显，丧失了随机访问的能力。不适合用于索引有语义的情况。
接口
public interface List<T> { int getSize(); boolean isEmpty(); void addFirst(T t); void add(int index,T t); void addLast(T t); T get(int index); T getFirst(); T getLast(); void set(int index,T t); boolean contains(T t); T remove(int index); T removeFirst(); T removeLast(); void removeElement(T t); }
实现类
public class LinkedList<T> implements List<T> { @AllArgsConstructor @Data private class Node { private T element; private Node next; public Node(T element) { this(element,null); } public Node() { this(null,null); } @Override public String toString() { return element.toString(); } } /** * 链表虚拟头节点 */ private Node dummyHead; private int size; public LinkedList() { dummyHead = new Node(); size = 0; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public void add(int index,T value) { if (index < 0 || index > size) { throw new IllegalArgumentException("添加错误，非法索引"); } Node prev = dummyHead; for (int i = 0; i < index; i++) { prev = prev.getNext(); } prev.setNext(new Node(value, prev.getNext())); size++; } @Override public void addFirst(T value) { add(0,value); } @Override public void addLast(T value) { add(size,value); } @Override public T get(int index) { if (index < 0 || index > size) { throw new IllegalArgumentException("获取错误，非法索引"); } Node cur = dummyHead.getNext(); for (int i = 0;i < index;i++) { cur = cur.getNext(); } return cur.getElement(); } @Override public T getFirst() { return get(0); } @Override public T getLast() { return get(size - 1); } @Override public void set(int index, T value) { if (index < 0 || index > size) { throw new IllegalArgumentException("设置错误，非法索引"); } Node cur = dummyHead.getNext(); for (int i = 0;i < index;i++) { cur = cur.getNext(); } cur.setElement(value); } @Override public boolean contains(T value) { Node cur = dummyHead.getNext(); while (cur != null) { if (cur.getElement().equals(value)) { return true; } cur = cur.getNext(); } return false; } @Override public T remove(int index) { if (index < 0 || index > size) { throw new IllegalArgumentException("删除错误，非法索引"); } Node prev = dummyHead; for (int i = 0;i < index;i++) { prev = prev.getNext(); } Node retNode = prev.getNext(); prev.setNext(retNode.getNext()); retNode.setNext(null); size--; return retNode.getElement(); } @Override public T removeFirst() { return remove(0); } @Override public T removeLast() { return remove(size - 1); } @Override public void removeElement(T value) { Node pre = dummyHead; while (pre.getNext() != null) { if (value.equals(pre.getNext().getElement())) { Node delNode = pre.getNext(); pre.setNext(delNode.getNext()); delNode.setNext(null); size--; break; } pre = pre.getNext(); } } @Override public String toString() { StringBuilder builder = new StringBuilder(); Node cur = dummyHead.getNext(); while (cur != null) { builder.append(cur + "->"); cur = cur.getNext(); } builder.append("NULL"); return builder.toString(); } }
调用
public class ListMain { public static void main(String[] args) { List<Integer> linkedList = new LinkedList<>(); for (int i = 0;i < 5;i++) { linkedList.add(i,i); System.out.println(linkedList); } linkedList.add(3,666); System.out.println(linkedList); linkedList.addLast(777); System.out.println(linkedList); linkedList.set(4,888); System.out.println(linkedList); System.out.println(linkedList.get(5)); System.out.println(linkedList.getFirst()); System.out.println(linkedList.getLast()); System.out.println(linkedList.contains(3)); linkedList.removeLast(); System.out.println(linkedList); linkedList.remove(4); System.out.println(linkedList); linkedList.removeFirst(); System.out.println(linkedList); linkedList.removeLast(); System.out.println(linkedList); linkedList.removeElement(2); System.out.println(linkedList); System.out.println(linkedList.getLast()); } }
运行结果
0->NULL
0->1->NULL
0->1->2->NULL
0->1->2->3->NULL
0->1->2->3->4->NULL
0->1->2->666->3->4->NULL
0->1->2->666->3->4->777->NULL
0->1->2->666->888->4->777->NULL
4
0
777
false
0->1->2->666->888->4->NULL
0->1->2->666->4->NULL
1->2->666->4->NULL
1->2->666->NULL
1->666->NULL
666
LinkedList各操作的时间复杂度
添加操作 O(n)
addLast(value) O(n)
addFirst(value) O(1)
add(index,value) O(n/2) = O(n)
删除操作 O(n)
removeLast() O(n)
removeFirst() O(1)
remove(index) O(n/2) = O(n)
removeElement(value) O(n)
修改操作
set(index,value) O(n)
查找操作 O(n)
get(index) O(n)
contains(value) O(n)
由于链表中对链表头的各操作都是O(1)的，对应于栈这种数据结构，是非常方便的，而且也无需扩容这一概念。
- 链表栈封装
实现类
@ToString public class LinkedListStack<T> implements Stack<T> { private List<T> list; public LinkedListStack() { list = new LinkedList<>(); } @Override public void push(T value) { list.addFirst(value); } @Override public T pop() { return list.removeFirst(); } @Override public T peek() { return list.getFirst(); } @Override public int getSize() { return list.getSize(); } @Override public boolean isEmpty() { return list.isEmpty(); } }
调用
public class StackMain { public static void main(String[] args) { Stack<Integer> stack = new LinkedListStack<>(); for (int i = 0;i < 5;i++) { stack.push(i); System.out.println(stack); } stack.pop(); System.out.println(stack); } }
运行结果
LinkedListStack(list=0->NULL)
LinkedListStack(list=1->0->NULL)
LinkedListStack(list=2->1->0->NULL)
LinkedListStack(list=3->2->1->0->NULL)
LinkedListStack(list=4->3->2->1->0->NULL)
LinkedListStack(list=3->2->1->0->NULL)
两种栈的性能测试
public class TestStackMain { private static double testStack(Stack<Integer> stack,int opCount) { long startTime = System.nanoTime(); Random random = new Random(); for (int i = 0;i < opCount;i++) { stack.push(random.nextInt(Integer.MAX_VALUE)); } for (int i = 0;i < opCount;i++) { stack.pop(); } long endTime = System.nanoTime(); return (endTime - startTime) / 1000000000.0; } public static void main(String[] args) { int opCount = 10000000; Stack<Integer> arrayStack = new ArrayStack<>(); double time1 = testStack(arrayStack,opCount); System.out.println("ArrayStack,time: " + time1 + " s"); Stack<Integer> linkedListStack = new LinkedListStack<>(); double time2 = testStack(linkedListStack,opCount); System.out.println("LinkedListStack,time: " + time2 + " s"); } }
测试结果
ArrayStack,time: 0.891863504 s
LinkedListStack,time: 3.731664658 s
对于这个测试结果来说，LinkedListStack要明显高于ArrayStack，这主要是Java的分配内存的特性决定，因为LinkedListStack有更多的new操作，要不断的分配内存空间给新的对象node。但这里要说明的是，其实它们两个在算法层面的时间复杂度是一致的。
- 链表队列封装
由于队列的特性，一端进，一端出，所以我们要添加一个尾节点，所以LinkedList无法复用。
实现类
public class LinkedListQueue<T> implements Queue<T> { @AllArgsConstructor @Data private class Node { private T element; private Node next; public Node(T element) { this(element,null); } public Node() { this(null,null); } @Override public String toString() { return element.toString(); } } /** * 队列头节点 */ private Node head; /** * 队列尾节点 */ private Node tail; /** * 队列元素个数 */ private int size; public LinkedListQueue() { head = null; tail = null; size = 0; } @Override public void enqueue(T value) { //当整个队列为空的时候 if (tail == null) { tail = new Node(value); head = tail; }else { //从尾部入队 tail.setNext(new Node(value)); tail = tail.getNext(); } size++; } @Override public T dequeue() { if (isEmpty()) { throw new IllegalArgumentException("无法从空队列出队"); } //从头部出队 Node retNode = head; head = head.getNext(); retNode.setNext(null); if (head == null) { tail = null; } size--; return retNode.getElement(); } @Override public T getFront() { if (isEmpty()) { throw new IllegalArgumentException("队列为空"); } return head.getElement(); } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public String toString() { StringBuilder builder = new StringBuilder(); builder.append("Queue: front "); Node cur = head; while (cur != null) { builder.append(cur + "->"); cur = cur.getNext(); } builder.append("NULL tail"); return builder.toString(); } }
调用
public class QueueMain { public static void main(String[] args) { Queue<Integer> queue = new LinkedListQueue<>(); for (int i = 0;i <= 10;i++) { queue.enqueue(i); System.out.println(queue); if (i % 3 == 2) { queue.dequeue(); System.out.println(queue); } } } }
运行结果
Queue: front 0->NULL tail
Queue: front 0->1->NULL tail
Queue: front 0->1->2->NULL tail
Queue: front 1->2->NULL tail
Queue: front 1->2->3->NULL tail
Queue: front 1->2->3->4->NULL tail
Queue: front 1->2->3->4->5->NULL tail
Queue: front 2->3->4->5->NULL tail
Queue: front 2->3->4->5->6->NULL tail
Queue: front 2->3->4->5->6->7->NULL tail
Queue: front 2->3->4->5->6->7->8->NULL tail
Queue: front 3->4->5->6->7->8->NULL tail
Queue: front 3->4->5->6->7->8->9->NULL tail
Queue: front 3->4->5->6->7->8->9->10->NULL tail
对三种队列进行性能测试
public class TestQueueMain { private static double testQueue(Queue<Integer> q,int opCount) { long startTime = System.nanoTime(); Random random = new Random(); for (int i = 0;i < opCount;i++) { q.enqueue(random.nextInt(Integer.MAX_VALUE)); } for (int i = 0;i < opCount;i++) { q.dequeue(); } long endTime = System.nanoTime(); return (endTime - startTime) / 1000000000.0; } public static void main(String[] args) { int opCount = 100000; Queue<Integer> arrayQueue = new ArrayQueue<>(); double time1 = testQueue(arrayQueue,opCount); System.out.println("ArrayQueue,time: " + time1 + " s"); Queue<Integer> loopQueue = new LoopQueue<>(); double time2 = testQueue(loopQueue,opCount); System.out.println("LoopQueue,time: " + time2 + " s"); Queue<Integer> linkedListQueue = new LinkedListQueue<>(); double time3 = testQueue(linkedListQueue,opCount); System.out.println("LinkedListQueue,time: " + time3 + " s"); } }
测试结果
ArrayQueue,time: 2.727521755 s
LoopQueue,time: 0.011994964 s
LinkedListQueue,time: 0.008463007 s
但是如果我们将opCount设为1千万，arrayQueue不参与，因为arrayQueue是O(n)级别的，时间过长，无法完成运算
public class TestQueueMain { private static double testQueue(Queue<Integer> q,int opCount) { long startTime = System.nanoTime(); Random random = new Random(); for (int i = 0;i < opCount;i++) { q.enqueue(random.nextInt(Integer.MAX_VALUE)); } for (int i = 0;i < opCount;i++) { q.dequeue(); } long endTime = System.nanoTime(); return (endTime - startTime) / 1000000000.0; } public static void main(String[] args) { int opCount = 10000000; // Queue<Integer> arrayQueue = new ArrayQueue<>(); // double time1 = testQueue(arrayQueue,opCount); // System.out.println("ArrayQueue,time: " + time1 + " s"); Queue<Integer> loopQueue = new LoopQueue<>(); double time2 = testQueue(loopQueue,opCount); System.out.println("LoopQueue,time: " + time2 + " s"); Queue<Integer> linkedListQueue = new LinkedListQueue<>(); double time3 = testQueue(linkedListQueue,opCount); System.out.println("LinkedListQueue,time: " + time3 + " s"); } }
测试结果
LoopQueue,time: 1.198824936 s
LinkedListQueue,time: 3.531655449 s
则此处LinkedListQueue比LoopQueue高的原因在之前的栈测试中已经说过了。通过查看GC日志-XX:+PrintGCDetails，我们可以看到
[GC (Allocation Failure) [PSYoungGen: 65536K->10720K(76288K)] 65536K->47444K(251392K), 0.0399149 secs] [Times: user=0.47 sys=0.03, real=0.04 secs]
[GC (Allocation Failure) [PSYoungGen: 76256K->10736K(141824K)] 112980K->102884K(316928K), 0.0615931 secs] [Times: user=0.74 sys=0.03, real=0.06 secs]
[GC (Allocation Failure) [PSYoungGen: 128805K->10720K(141824K)] 220954K->185957K(317440K), 0.1094546 secs] [Times: user=1.09 sys=0.07, real=0.11 secs]
[Full GC (Ergonomics) [PSYoungGen: 10720K->0K(141824K)] [ParOldGen: 175237K->83146K(279552K)] 185957K->83146K(421376K), [Metaspace: 3396K->3396K(1056768K)], 0.6877482 secs] [Times: user=4.42 sys=0.04, real=0.68 secs]
LoopQueue,time: 1.213829799 s
[GC (Allocation Failure) [PSYoungGen: 131072K->10752K(196608K)] 214218K->168218K(476160K), 0.4136930 secs] [Times: user=5.33 sys=0.01, real=0.42 secs]
[GC (Allocation Failure) [PSYoungGen: 196608K->10752K(272896K)] 354074K->354714K(616960K), 0.9071643 secs] [Times: user=11.66 sys=0.08, real=0.91 secs]
[Full GC (Ergonomics) [PSYoungGen: 10752K->0K(272896K)] [ParOldGen: 343962K->271533K(605696K)] 354714K->271533K(878592K), [Metaspace: 3479K->3479K(1056768K)], 1.8924275 secs] [Times: user=24.48 sys=0.03, real=1.89 secs]
LinkedListQueue,time: 3.412228277 s
Heap
PSYoungGen total 272896K, used 131467K [0x000000076ab00000, 0x0000000792600000, 0x00000007c0000000)
eden space 262144K, 50% used [0x000000076ab00000,0x0000000772b62e80,0x000000077ab00000)
from space 10752K, 0% used [0x000000077ab00000,0x000000077ab00000,0x000000077b580000)
to space 185344K, 0% used [0x0000000787100000,0x0000000787100000,0x0000000792600000)
ParOldGen total 605696K, used 271533K [0x00000006c0000000, 0x00000006e4f80000, 0x000000076ab00000)
object space 605696K, 44% used [0x00000006c0000000,0x00000006d092b670,0x00000006e4f80000)
Metaspace used 3486K, capacity 4566K, committed 4864K, reserved 1056768K
class space used 376K, capacity 390K, committed 512K, reserved 1048576K
通过GC日志，我们可以看到有大量的对象进入了老年代，并没有在年轻代被回收，以至于发生了全GC。我们调整JVM内存来看一下-Xmx1G -Xms1G
[GC (Allocation Failure) [PSYoungGen: 260301K->43511K(305664K)] 260301K->83257K(1005056K), 0.0813630 secs] [Times: user=0.99 sys=0.04, real=0.08 secs]
LoopQueue,time: 0.443129398 s
[GC (Allocation Failure) [PSYoungGen: 305655K->43495K(305664K)] 345401K->254481K(1005056K), 1.0359483 secs] [Times: user=12.20 sys=0.14, real=1.04 secs]
LinkedListQueue,time: 1.261171544 s
Heap
PSYoungGen total 305664K, used 223003K [0x00000007aab00000, 0x00000007c0000000, 0x00000007c0000000)
eden space 262144K, 68% used [0x00000007aab00000,0x00000007b5a4d0e8,0x00000007bab00000)
from space 43520K, 99% used [0x00000007bd580000,0x00000007bfff9dc8,0x00000007c0000000)
to space 43520K, 0% used [0x00000007bab00000,0x00000007bab00000,0x00000007bd580000)
ParOldGen total 699392K, used 210985K [0x0000000780000000, 0x00000007aab00000, 0x00000007aab00000)
object space 699392K, 30% used [0x0000000780000000,0x000000078ce0a708,0x00000007aab00000)
Metaspace used 3488K, capacity 4566K, committed 4864K, reserved 1056768K
class space used 376K, capacity 390K, committed 512K, reserved 1048576K
通过调整JVM内存，我们可以看到全GC消失了，所使用的时间大幅度减少。但是我们可以看到eden区的使用空间过小，只有68%，所以我们要调整新生代的内存分配比例
-XX:+PrintGCDetails -Xmx1G -Xms1G -XX:+UseParallelGC -XX:+UseCompressedOops -XX:SurvivorRatio=4 -XX:ParallelGCThreads=8
[GC (Allocation Failure) [PSYoungGen: 233472K->57831K(291328K)] 233472K->174728K(990720K), 0.1696696 secs] [Times: user=1.25 sys=0.09, real=0.17 secs]
LoopQueue,time: 0.521021115 s
[GC (Allocation Failure) [PSYoungGen: 291303K->57831K(291328K)] 408200K->279688K(990720K), 0.6708571 secs] [Times: user=5.25 sys=0.10, real=0.67 secs]
LinkedListQueue,time: 0.866029237 s
Heap
PSYoungGen total 291328K, used 290384K [0x00000007aab00000, 0x00000007c0000000, 0x00000007c0000000)
eden space 233472K, 99% used [0x00000007aab00000,0x00000007b8e1a330,0x00000007b8f00000)
from space 57856K, 99% used [0x00000007bc780000,0x00000007bfff9dc8,0x00000007c0000000)
to space 57856K, 0% used [0x00000007b8f00000,0x00000007b8f00000,0x00000007bc780000)
ParOldGen total 699392K, used 221857K [0x0000000780000000, 0x00000007aab00000, 0x00000007aab00000)
object space 699392K, 31% used [0x0000000780000000,0x000000078d8a84f8,0x00000007aab00000)
Metaspace used 3488K, capacity 4566K, committed 4864K, reserved 1056768K
class space used 376K, capacity 390K, committed 512K, reserved 1048576K
通过调整eden区和survivor区(包括from和to)的比例，我们可以看到eden区的使用效率提升到了99%，而LinkedListQueue的运行时间也由1.261171544 s降到了0.866029237 s。
LeetCode算法题https://leetcode-cn.com/problems/remove-linked-list-elements/submissions/
这是LeetCode的第203题，移除链表元素
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6 输出: 1->2->3->4->5
我们先定义一个ListNode
public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; } }
public class Solution { public ListNode removeElements(ListNode head, int val) { //移除所有可能值为val的头部节点 while (head != null && head.val == val) { ListNode delNode = head; head = head.next; delNode.next = null; } if (head == null) { return null; } //移除所有可能值为val的中间节点 ListNode prev = head; while (prev.next != null) { if (prev.next.val == val) { ListNode delNode = prev.next; prev.next = delNode.next; delNode.next = null; }else { prev = prev.next; } } return head; } }
提交后，结果如下
当然除了特殊处理头节点以外，我们还可以建立虚拟头节点
public class Solution { public ListNode removeElements(ListNode head, int val) { //建立虚拟头节点 ListNode dummyHead = new ListNode(-1); dummyHead.next = head; //移除所有可能值为val的中间节点 ListNode prev = dummyHead; while (prev.next != null) { if (prev.next.val == val) { ListNode delNode = prev.next; prev.next = delNode.next; delNode.next = null; }else { prev = prev.next; } } return dummyHead.next; } }
提交给LeetCode
自己实现一个测试用例
改写ListNode
public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; } /** * 通过一个数组转化成一个链表 * @param arr */ public ListNode(int[] arr) { if (arr == null || arr.length == 0) { throw new IllegalArgumentException("数组不能为空"); } this.val = arr[0]; ListNode cur = this; for (int i = 1;i < arr.length;i++) { cur.next = new ListNode(arr[i]); cur = cur.next; } } @Override public String toString() { StringBuilder builder = new StringBuilder(); ListNode cur = this; while (cur != null) { builder.append(cur.val + "->"); cur = cur.next; } builder.append("NULL"); return builder.toString(); } }
public class Solution { public ListNode removeElements(ListNode head, int val) { //建立虚拟头节点 ListNode dummyHead = new ListNode(-1); dummyHead.next = head; //移除所有可能值为val的中间节点 ListNode prev = dummyHead; while (prev.next != null) { if (prev.next.val == val) { ListNode delNode = prev.next; prev.next = delNode.next; delNode.next = null; }else { prev = prev.next; } } return dummyHead.next; } public static void main(String[] args) { int[] values = {1,2,6,3,4,5,6}; ListNode node = new ListNode(values); System.out.println(node); Solution solution = new Solution(); ListNode listNode = solution.removeElements(node, 6); System.out.println(listNode); } }
测试结果
1->2->6->3->4->5->6->NULL
1->2->3->4->5->NULL
- 递归
我们先来看一个求和的递归
public class Sum { private static int sum(int[] arr) { return sum(arr,0); } private static int sum(int[] arr,int l) { //求解最基本的问题 if (l == arr.length) { return 0; } //把原问题转化成更小的问题 return arr[l] + sum(arr,l + 1); } public static void main(String[] args) { int[] arr = {1,2,3,4,5,6,7,8,9}; System.out.println(sum(arr)); } }
运行结果
45
- 链表的递归性
链表具有天然的递归性，它可以表示为头节点+少了头节点的链表。
使用递归来求解LeetCode的第203题
public class Solution { public ListNode removeElements(ListNode head, int val) { //求解最基本的问题 if (head == null) { return null; } //把原问题转化成更小的问题 //此时把链表拆分成头节点+一个不包含头节点的链表 ListNode node = removeElements(head.next, val); //拼接头节点 if (head.val == val) { return node; }else { head.next = node; return head; } } public static void main(String[] args) { int[] values = {1,2,6,3,4,5,6}; ListNode node = new ListNode(values); System.out.println(node); Solution solution = new Solution(); ListNode listNode = solution.removeElements(node, 6); System.out.println(listNode); } }
运行结果
1->2->6->3->4->5->6->NULL
1->2->3->4->5->NULL
在LeetCode上提交
最后改写成一个简洁的表述
public class Solution { public ListNode removeElements(ListNode head, int val) { //求解最基本的问题 if (head == null) { return null; } //把原问题转化成更小的问题 //此时把链表拆分成头节点+一个不包含头节点的链表 head.next = removeElements(head.next, val); //是否拼接头节点 return head.val == val?head.next : head; } public static void main(String[] args) { int[] values = {1,2,6,3,4,5,6}; ListNode node = new ListNode(values); System.out.println(node); Solution solution = new Solution(); ListNode listNode = solution.removeElements(node, 6); System.out.println(listNode); } }
运行结果
1->2->6->3->4->5->6->NULL
1->2->3->4->5->NULL
调试链表的递归性
public class Solution { public ListNode removeElements(ListNode head, int val,int depth) { String depthString = generateDepthString(depth); System.out.print(depthString); System.out.println("调用: 删除 " + val + "在 " + head + "中"); //求解最基本的问题 if (head == null) { System.out.print(depthString); System.out.println("返回:" + head); return null; } //把原问题转化成更小的问题 //此时把链表拆分成头节点+一个不包含头节点的链表 ListNode node = removeElements(head.next, val,depth + 1); System.out.print(depthString); System.out.println("删除 " + val + "之后: " + node); //是否拼接头节点 ListNode ret; if (head.val == val) { ret = node; }else { head.next = node; ret = head; } System.out.print(depthString); System.out.println("返回: " + ret); return ret; } private String generateDepthString(int depth) { StringBuilder builder = new StringBuilder(); for (int i = 0;i < depth;i++) { builder.append("--"); } return builder.toString(); } public static void main(String[] args) { int[] values = {1,2,6,3,4,5,6}; ListNode node = new ListNode(values); System.out.println(node); Solution solution = new Solution(); ListNode listNode = solution.removeElements(node, 6,0); System.out.println(listNode); } }
运行结果
1->2->6->3->4->5->6->NULL
调用: 删除 6在 1->2->6->3->4->5->6->NULL中
--调用: 删除 6在 2->6->3->4->5->6->NULL中
----调用: 删除 6在 6->3->4->5->6->NULL中
------调用: 删除 6在 3->4->5->6->NULL中
--------调用: 删除 6在 4->5->6->NULL中
----------调用: 删除 6在 5->6->NULL中
------------调用: 删除 6在 6->NULL中
--------------调用: 删除 6在 null中
--------------返回:null
------------删除 6之后: null
------------返回: null
----------删除 6之后: null
----------返回: 5->NULL
--------删除 6之后: 5->NULL
--------返回: 4->5->NULL
------删除 6之后: 4->5->NULL
------返回: 3->4->5->NULL
----删除 6之后: 3->4->5->NULL
----返回: 3->4->5->NULL
--删除 6之后: 3->4->5->NULL
--返回: 2->3->4->5->NULL
删除 6之后: 2->3->4->5->NULL
返回: 1->2->3->4->5->NULL
1->2->3->4->5->NULL
- 单向链表的递归改写
实现类
public class RecursiveLinkedList<T> implements List<T> { @AllArgsConstructor @Data private class Node { private T element; private Node next; public Node(T element) { this(element,null); } public Node() { this(null,null); } @Override public String toString() { return element.toString(); } } /** * 链表虚拟头节点 */ private Node dummyHead; private int size; public RecursiveLinkedList() { dummyHead = new Node(); size = 0; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public void addFirst(T value) { add(0,value); } @Override public void add(int index, T value) { if (index < 0 || index > size) { throw new IllegalArgumentException("添加错误，非法索引"); } dummyHead = add(-1,index,dummyHead,value); } private Node add(int i,int index,Node node,T value) { if (i == index - 1) { size++; node.setNext(new Node(value,node.getNext())); return node; } node.setNext(add(i + 1,index,node.getNext(),value)); return node; } @Override public void addLast(T value) { add(size,value); } @Override public T get(int index) { if (index < 0 || index > size) { throw new IllegalArgumentException("查找错误，非法索引"); } return get(0,index,dummyHead.getNext()); } private T get(int i,int index,Node node) { if (i == index) { return node.getElement(); } return get(i + 1,index,node.getNext()); } @Override public T getFirst() { return get(0); } @Override public T getLast() { return get(size - 1); } @Override public void set(int index, T value) { if (index < 0 || index > size) { throw new IllegalArgumentException("更新错误，非法索引"); } set(0,index,dummyHead.getNext(),value); } private void set(int i,int index,Node node,T value) { if (i == index) { node.setElement(value); return; } set(i + 1,index,node.getNext(),value); } @Override public boolean contains(T value) { return contains(dummyHead.getNext(),value); } private boolean contains(Node node,T value) { if (node == null) { return false; } if (node.getElement().equals(value)) { return true; } return contains(node.getNext(),value); } @Override public T remove(int index) { if (index < 0 || index > size) { throw new IllegalArgumentException("删除错误，非法索引"); } return remove(-1,index,dummyHead).getElement(); } private Node remove(int i,int index,Node node) { if (i == index - 1) { Node ret = node.getNext(); node.setNext(ret.getNext()); ret.setNext(null); size--; return ret; } return remove(i + 1,index,node.getNext()); } @Override public T removeFirst() { return remove(0); } @Override public T removeLast() { return remove(size - 1); } @Override public void removeElement(T value) { dummyHead = removeElement(dummyHead,value); } private Node removeElement(Node node,T value) { if (node.getNext() == null) { return null; } else { if (value.equals(node.getNext().getElement())) { Node delNode = node.getNext(); node.setNext(delNode.getNext()); delNode.setNext(null); size--; return node; } } node.setNext(removeElement(node.getNext(),value)); return node; } @Override public String toString() { StringBuilder builder = new StringBuilder(); Node cur = dummyHead.getNext(); while (cur != null) { builder.append(cur + "->"); cur = cur.getNext(); } builder.append("NULL"); return builder.toString(); } }
调用
public class ListMain { public static void main(String[] args) { List<Integer> linkedList = new RecursiveLinkedList<>(); for (int i = 0;i < 5;i++) { linkedList.add(i,i); System.out.println(linkedList); } linkedList.add(3,666); System.out.println(linkedList); linkedList.addLast(777); System.out.println(linkedList); linkedList.set(4,888); System.out.println(linkedList); System.out.println(linkedList.get(5)); System.out.println(linkedList.getFirst()); System.out.println(linkedList.getLast()); System.out.println(linkedList.contains(3)); linkedList.removeLast(); System.out.println(linkedList); linkedList.remove(4); System.out.println(linkedList); linkedList.removeFirst(); System.out.println(linkedList); linkedList.removeLast(); System.out.println(linkedList); linkedList.removeElement(2); System.out.println(linkedList); System.out.println(linkedList.getLast()); } }
运行结果
0->NULL
0->1->NULL
0->1->2->NULL
0->1->2->3->NULL
0->1->2->3->4->NULL
0->1->2->666->3->4->NULL
0->1->2->666->3->4->777->NULL
0->1->2->666->888->4->777->NULL
4
0
777
false
0->1->2->666->888->4->NULL
0->1->2->666->4->NULL
1->2->666->4->NULL
1->2->666->NULL
1->666->NULL
666
- 双向链表的封装
实现类
public class MutualLinkedList<T> implements List<T> { @AllArgsConstructor @NoArgsConstructor @Data private class Node { private T element; private Node prev; private Node next; public Node(T element) { this(element,null,null); } @Override public String toString() { return element.toString(); } } private Node dummyHead; private Node tail; private int size; public MutualLinkedList() { dummyHead = new Node(); tail = null; size = 0; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public void addFirst(T value) { add(0,value); } @Override public void add(int index, T value) { if (index < 0 || index > size) { throw new IllegalArgumentException("添加错误，非法索引"); } if (index <= size / 2 + 1) { Node prev = dummyHead; for (int i = 0; i < index; i++) { prev = prev.getNext(); } Node node = new Node(value,prev,prev.getNext()); if (prev.getNext() != null) { prev.getNext().setPrev(node); }else { tail = node; } prev.setNext(node); }else { if (index == size) { addLast(value); return; } else { Node cur = tail; for (int i = size; i > index + 1; i--) { cur = cur.getPrev(); } Node node = new Node(value, cur.getPrev(), cur); cur.getPrev().setNext(node); cur.setPrev(node); } } size++; } @Override public void addLast(T value) { Node node = new Node(value,tail,tail.getNext()); tail.setNext(node); tail = node; size++; } @Override public T get(int index) { if (index < 0 || index > size) { throw new IllegalArgumentException("获取错误，非法索引"); } if (index <= size / 2) { Node cur = dummyHead.getNext(); for (int i = 0;i < index;i++) { cur = cur.getNext(); } return cur.getElement(); }else { Node cur = tail; for (int i = size;i > index + 1;i--) { cur = cur.getPrev(); } return cur.getElement(); } } @Override public T getFirst() { return get(0); } @Override public T getLast() { return tail.getElement(); } @Override public void set(int index, T value) { if (index < 0 || index > size) { throw new IllegalArgumentException("设置错误，非法索引"); } if (index <= size / 2) { Node cur = dummyHead.getNext(); for (int i = 0;i < index;i++) { cur = cur.getNext(); } cur.setElement(value); }else { Node cur = tail; for (int i = size;i > index + 1;i--) { cur = cur.getPrev(); } cur.setElement(value); } } @Override public boolean contains(T value) { Node cur = dummyHead.getNext(); while (cur != null) { if (cur.getElement().equals(value)) { return true; } cur = cur.getNext(); } return false; } @Override public T remove(int index) { if (index < 0 || index > size) { throw new IllegalArgumentException("删除错误，非法索引"); } if (index <= size / 2) { Node prev = dummyHead; for (int i = 0;i < index;i++) { prev = prev.getNext(); } Node ret = prev.getNext(); prev.setNext(ret.getNext()); ret.getNext().setPrev(prev); ret.setNext(null); ret.setPrev(null); size--; return ret.getElement(); }else { Node cur = tail; for (int i = size;i > index + 1;i--) { cur = cur.getPrev(); } cur.getPrev().setNext(cur.getNext()); if (cur.getNext() != null) { cur.getNext().setPrev(cur.getPrev()); }else { tail = cur.getPrev(); } cur.setPrev(null); cur.setNext(null); size--; return cur.getElement(); } } @Override public T removeFirst() { return remove(0); } @Override public T removeLast() { Node node = tail; tail = tail.getPrev(); tail.setNext(null); node.setPrev(null); size--; return node.getElement(); } @Override public void removeElement(T value) { Node pre = dummyHead; while (pre.getNext() != null) { if (value.equals(pre.getNext().getElement())) { Node delNode = pre.getNext(); pre.setNext(delNode.getNext()); delNode.setNext(null); size--; break; } pre = pre.getNext(); } } @Override public String toString() { StringBuilder builder = new StringBuilder(); Node cur = dummyHead.getNext(); while (cur != null) { builder.append(cur + "->"); cur = cur.getNext(); } builder.append("NULL"); return builder.toString(); } }
调用
public class ListMain { public static void main(String[] args) { List<Integer> linkedList = new MutualLinkedList<>(); for (int i = 0;i < 5;i++) { linkedList.add(i,i); System.out.println(linkedList); } linkedList.add(3,666); System.out.println(linkedList); linkedList.addLast(777); System.out.println(linkedList); linkedList.set(4,888); System.out.println(linkedList); System.out.println(linkedList.get(5)); System.out.println(linkedList.getFirst()); System.out.println(linkedList.getLast()); System.out.println(linkedList.contains(3)); linkedList.removeLast(); System.out.println(linkedList); linkedList.remove(4); System.out.println(linkedList); linkedList.removeFirst(); System.out.println(linkedList); linkedList.removeLast(); System.out.println(linkedList); linkedList.removeElement(2); System.out.println(linkedList); System.out.println(linkedList.getLast()); } }
运行结果
0->NULL
0->1->NULL
0->1->2->NULL
0->1->2->3->NULL
0->1->2->3->4->NULL
0->1->2->666->3->4->NULL
0->1->2->666->3->4->777->NULL
0->1->2->666->888->4->777->NULL
4
0
777
false
0->1->2->666->888->4->NULL
0->1->2->666->4->NULL
1->2->666->4->NULL
1->2->666->NULL
1->666->NULL
666
MutualLinkedList各操作的时间复杂度
添加操作 O(n/2) = O(n)
addLast(value) O(1)
addFirst(value) O(1)
add(index,value) O(n/2) = O(n)
删除操作 O(n)
removeLast() O(1)
removeFirst() O(1)
remove(index) O(n/2) = O(n)
修改操作
set(index,value) O(n/2) = O(n)
查找操作 O(n)
get(index) O(n/2) = O(n)
contains(value) O(n)
根据addLast(value),addFirst(value) ,removeLast() ,removeFirst() 都是O(1)的复杂度，所以用双向链表来实现队列也是很简单的。
- 二分搜索树的封装
二分搜索树是一种可比较大小的二叉树，它可以饱和，也可以非饱和。
接口
public interface Tree<T> { int getSize(); boolean isEmpty(); void add(T t); boolean contains(T t); /** * 前序遍历 */ void preOrder(); /** * 中序遍历 */ void inOrder(); /** * 后序遍历 */ void postOrder(); /** * 层序遍历，又称广度遍历 * 而前、中、后序遍历又称深度遍历 */ void levelOrder(); /** * 查找最小元素 * @return */ T minimum(); /** * 查找最大元素 * @return */ T maximum(); /** * 删除最小元素 * @return */ T removeMin(); /** * 删除最大元素 * @return */ T removeMax(); /** * 删除任意节点 * @return */ void remove(T t); /** * 找出比t小的最大值 * @param t * @return */ T floor(T t); /** * 找出比t大的最小值 * @param t * @return */ T ceil(T t); }
实现类
public class BST<T extends Comparable<T>> implements Tree<T> { @AllArgsConstructor @Data private class Node{ private T element; private Node left; private Node right; public Node(T element) { this(element,null,null); } } private Node root; private int size; public BST() { root = null; size = 0; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public void add(T value) { root = add(root,value); } private Node add(Node node,T value) { //递归终止条件 if (node == null) { size++; return new Node(value); } //递归 if (value.compareTo(node.getElement()) < 0) { node.setLeft(add(node.getLeft(),value)); }else if (value.compareTo(node.getElement()) > 0) { node.setRight(add(node.getRight(),value)); } return node; } @Override public boolean contains(T value) { return contains(root,value); } private boolean contains(Node node,T value) { if (node == null) { return false; } if (value.compareTo(node.getElement()) == 0) { return true; }else if (value.compareTo(node.getElement()) < 0) { return contains(node.getLeft(),value); }else { return contains(node.getRight(),value); } } @Override public void preOrder() { preOrder(root); } private void preOrder(Node node) { if (node == null) { return; } System.out.println(node.getElement()); preOrder(node.getLeft()); preOrder(node.getRight()); } /** * 非递归前序遍历 */ public void preOrderNR() { Stack<Node> stack = new ArrayStack<>(); stack.push(root); while (!stack.isEmpty()) { Node cur = stack.pop(); System.out.println(cur.getElement()); if (cur.getRight() != null) { stack.push(cur.getRight()); } if (cur.getLeft() != null) { stack.push(cur.getLeft()); } } } @Override public void inOrder() { inOrder(root); } private void inOrder(Node node) { if (node == null) { return; } inOrder(node.getLeft()); System.out.println(node.getElement()); inOrder(node.getRight()); } @Override public void postOrder() { postOrder(root); } private void postOrder(Node node) { if (node == null) { return; } postOrder(node.getLeft()); postOrder(node.getRight()); System.out.println(node.getElement()); } @Override public void levelOrder() { Queue<Node> queue = new LoopQueue<>(); queue.enqueue(root); while (!queue.isEmpty()) { Node cur = queue.dequeue(); System.out.println(cur.getElement()); if (cur.getLeft() != null) { queue.enqueue(cur.getLeft()); } if (cur.getRight() != null) { queue.enqueue(cur.getRight()); } } } @Override public T minimum() { if (size == 0) { throw new IllegalArgumentException("二分搜索树为空"); } return minimum(root).getElement(); } private Node minimum(Node node) { if (node.getLeft() == null) { return node; } return minimum(node.getLeft()); } @Override public T maximum() { if (size == 0) { throw new IllegalArgumentException("二分搜索树为空"); } return maximum(root).getElement(); } private Node maximum(Node node) { if (node.getRight() == null) { return node; } return maximum(node.getRight()); } @Override public T removeMin() { T ret = minimum(); root = removeMin(root); return ret; } private Node removeMin(Node node) { //递归的终止条件，当节点的左子树为空时，递归达到最大深度 if (node.getLeft() == null) { //保存最终节点的右子树 Node rightNode = node.getRight(); //将最终节点分离 node.setRight(null); size--; //将保存的右子树拼接回最终节点的父节点 return rightNode; } //从根节点开始不断向左子树递归，并逐层返回删除后的子节点重新 //设为上层节点的左节点 node.setLeft(removeMin(node.getLeft())); return node; } @Override public T removeMax() { T ret = maximum(); root = removeMax(root); return ret; } private Node removeMax(Node node) { if (node.getRight() == null) { Node leftNode = node.getLeft(); node.setLeft(null); size--; return leftNode; } node.setRight(removeMax(node.getRight())); return node; } @Override public void remove(T value) { root = remove(root,value); } private Node remove(Node node,T value) { if (node == null) { return null; } if (value.compareTo(node.getElement()) < 0) { node.setLeft(remove(node.getLeft(),value)); return node; }else if (value.compareTo(node.getElement()) > 0) { node.setRight(remove(node.getRight(),value)); return node; }else { //待删除节点左子树为空的情况 if (node.getLeft() == null) { Node rightNode = node.getRight(); node.setRight(null); size--; return rightNode; } //待删除节点右子树为空的情况 if (node.getRight() == null) { Node leftNode = node.getLeft(); node.setLeft(null); size--; return leftNode; } //待删除节点左右子树均不为空的情况 //找到比待删除节点大的最小节点，即待删除节点右子树的最小节点 //用这个节点顶替待删除节点的位置 Node successor = minimum(node.getRight()); successor.setRight(removeMin(node.getRight())); successor.setLeft(node.getLeft()); node.setLeft(null); node.setRight(null); return successor; //找到比待删除节点小的最大节点，即待删除节点左子树的最大节点 //用这个节点顶替待删除节点的位置,此二种方法取其一即可 // Node predecessor = maximum(node.getLeft()); // predecessor.setLeft(removeMax(node.getLeft())); // predecessor.setRight(node.getRight()); // node.setLeft(null); // node.setRight(null); // return predecessor; } } @Override public T floor(T value) { Node node = floor(root,value); if (node != null) { return node.getElement(); } return null; } private Node floor(Node node,T value) { if (node == null) { return null; } if (value.compareTo(node.getElement()) <= 0) { return floor(node.getLeft(),value); }else { if (node.getRight() == null) { return node; }else if (node.getRight().getLeft() == null && value.compareTo(node.getRight().getElement()) <= 0) { return node; }else if (node.getRight().getRight() == null && value.compareTo(node.getRight().getElement()) > 0) { return node.getRight(); } return floor(node.getRight(),value); } } @Override public T ceil(T value) { Node node = ceil(root,value); if (node != null) { return node.getElement(); } return null; } private Node ceil(Node node,T value) { if (node == null) { return null; } if (value.compareTo(node.getElement()) >= 0) { return ceil(node.getRight(),value); }else { if (node.getLeft() == null) { return node; }else if (value.compareTo(maximum(node.getLeft()).getElement()) >= 0) { return node; }else if (node.getLeft().getRight() == null && value.compareTo(node.getLeft().getElement()) >= 0) { return node; }else if (node.getLeft().getLeft() == null && value.compareTo(node.getLeft().getElement()) < 0) { return node.getLeft(); } return ceil(node.getLeft(),value); } } @Override public String toString() { StringBuilder builder = new StringBuilder(); generateBSTString(root,0,builder); return builder.toString(); } private void generateBSTString(Node node,int depth,StringBuilder builder) { if (node == null) { builder.append(generateDepthString(depth) + "null\n"); return; } builder.append(generateDepthString(depth) + node.getElement() + "\n"); generateBSTString(node.getLeft(),depth + 1,builder); generateBSTString(node.getRight(),depth + 1,builder); } private String generateDepthString(int depth) { StringBuilder builder = new StringBuilder(); for (int i = 0;i < depth;i++) { builder.append("--"); } return builder.toString(); } }
调用
public class TreeMain { public static void main(String[] args) { Tree<Integer> bst = new BST<>(); Integer[] nums = {50,30,60,80,40,20}; Stream.of(nums).forEach(bst::add); System.out.println("递归前序遍历"); bst.preOrder(); System.out.println("非递归前序遍历"); ((BST)bst).preOrderNR(); /////////////////////////////// // 50 // // / \ // // 30 60 // // / \ \ // // 20 40 80 // /////////////////////////////// System.out.println("中序遍历"); bst.inOrder(); System.out.println("后续遍历"); bst.postOrder(); System.out.println("层序遍历"); bst.levelOrder(); System.out.println(); System.out.println(bst); System.out.println(bst.floor(35)); System.out.println(bst.ceil(45)); System.out.println(); bst.remove(30); System.out.println(bst); } }
运行结果
递归前序遍历
50
30
20
40
60
80
非递归前序遍历
50
30
20
40
60
80
中序遍历
20
30
40
50
60
80
后续遍历
20
40
30
80
60
50
层序遍历
50
30
60
20
40
80
50
--30
----20
------null
------null
----40
------null
------null
--60
----null
----80
------null
------null
30
50
50
--40
----20
------null
------null
----null
--60
----null
----80
------null
------null
对删除最小,最大元素进行测试
public class TreeMain1 { public static void main(String[] args) { Tree<Integer> bst = new BST<>(); Random random = new Random(); for (int i = 0;i < 1000;i++) { bst.add(random.nextInt(10000)); } Array<Integer> numsMin = new DefaultArray<>(); while (!bst.isEmpty()) { numsMin.addLast(bst.removeMin()); } System.out.println(numsMin); for (int i = 1;i < numsMin.getSize();i++) { if (numsMin.get(i - 1) > numsMin.get(i)) { throw new IllegalArgumentException("错误"); } } System.out.println("removeMin测试成功"); for (int i = 0;i < 1000;i++) { bst.add(random.nextInt(10000)); } Array<Integer> numsMax = new DefaultArray<>(); while (!bst.isEmpty()) { numsMax.addLast(bst.removeMax()); } System.out.println(numsMax); for (int i = 1;i < numsMax.getSize();i++) { if (numsMax.get(i - 1) < numsMax.get(i)) { throw new IllegalArgumentException("错误"); } } System.out.println("removeMax测试成功"); } }
运行结果
DefaultArray(data=[1,8,9,21,25,36,69,77,88,89,109,116,121,132,135,146,168,211,220,238,242,249,254,296,304,314,316,320,353,364,380,391,395,399,402,409,416,421,425,426,450,457,463,473,478,491,519,534,543,545,563,573,579,581,590,591,600,644,648,655,661,670,697,710,712,713,717,724,734,739,744,750,754,787,803,812,813,824,835,838,841,843,844,867,869,882,907,912,933,937,940,943,952,959,970,972,974,988,991,996,1000,1004,1019,1031,1032,1040,1064,1069,1085,1117,1120,1122,1131,1148,1151,1154,1174,1226,1232,1233,1234,1235,1243,1246,1283,1291,1301,1327,1338,1340,1389,1395,1403,1411,1416,1420,1424,1434,1440,1447,1450,1459,1461,1471,1474,1493,1495,1497,1499,1510,1521,1528,1533,1537,1549,1564,1569,1585,1586,1608,1613,1621,1644,1670,1672,1674,1677,1699,1713,1717,1739,1754,1756,1763,1783,1786,1795,1797,1814,1819,1828,1843,1850,1855,1866,1875,1894,1897,1902,1913,1918,1925,1952,1995,1998,2014,2025,2027,2041,2045,2046,2059,2071,2074,2079,2102,2118,2120,2132,2139,2155,2156,2163,2165,2170,2193,2194,2205,2209,2234,2238,2266,2267,2272,2273,2277,2282,2302,2313,2331,2353,2360,2370,2380,2390,2416,2435,2439,2449,2454,2475,2478,2502,2514,2521,2522,2543,2568,2578,2590,2612,2617,2646,2662,2663,2665,2667,2677,2683,2687,2688,2691,2708,2711,2716,2751,2783,2794,2813,2817,2826,2853,2866,2879,2883,2885,2899,2914,2921,2926,2933,3003,3007,3020,3048,3059,3080,3083,3105,3108,3142,3150,3162,3218,3226,3230,3249,3258,3268,3285,3287,3293,3305,3322,3323,3340,3356,3372,3379,3386,3394,3412,3417,3433,3441,3451,3460,3483,3509,3511,3518,3534,3542,3561,3567,3584,3593,3599,3609,3618,3627,3632,3647,3659,3668,3670,3675,3676,3695,3697,3706,3712,3738,3754,3756,3765,3771,3801,3812,3820,3823,3834,3841,3846,3848,3853,3857,3866,3896,3906,3910,3915,3943,3949,3960,3971,3984,3990,4010,4024,4027,4030,4033,4059,4079,4080,4090,4104,4111,4122,4135,4138,4146,4150,4151,4169,4176,4193,4194,4202,4206,4207,4211,4216,4226,4243,4244,4251,4264,4269,4272,4292,4301,4305,4315,4322,4342,4352,4362,4383,4397,4398,4412,4414,4417,4430,4458,4474,4487,4490,4506,4564,4583,4587,4608,4622,4632,4642,4643,4652,4654,4665,4673,4674,4676,4699,4706,4707,4714,4722,4730,4732,4758,4759,4765,4788,4842,4850,4851,4856,4880,4887,4891,4892,4893,4897,4903,4905,4926,4949,4969,4972,4978,4979,4984,5037,5050,5059,5060,5079,5087,5122,5141,5145,5154,5183,5184,5193,5201,5215,5227,5229,5231,5241,5252,5259,5267,5315,5323,5331,5339,5343,5344,5357,5359,5397,5403,5405,5410,5412,5416,5417,5419,5444,5446,5465,5489,5490,5493,5504,5506,5510,5524,5536,5545,5552,5557,5563,5577,5586,5587,5590,5607,5615,5632,5674,5684,5698,5699,5719,5721,5726,5727,5739,5747,5749,5753,5762,5774,5776,5796,5815,5822,5836,5840,5848,5856,5861,5882,5896,5899,5911,5913,5916,5932,5945,5965,5968,5972,5982,5994,6014,6023,6032,6050,6076,6084,6116,6119,6120,6130,6131,6140,6145,6150,6154,6162,6169,6173,6187,6191,6195,6253,6260,6277,6295,6300,6304,6306,6318,6325,6336,6337,6343,6356,6362,6378,6383,6392,6404,6416,6428,6460,6492,6534,6555,6560,6571,6574,6580,6582,6590,6593,6597,6605,6608,6611,6615,6626,6636,6641,6649,6652,6659,6662,6672,6676,6686,6691,6712,6753,6773,6779,6781,6782,6789,6790,6807,6808,6817,6842,6849,6852,6863,6869,6885,6886,6892,6896,6899,6906,6925,6937,6950,6957,6960,6970,6994,7019,7027,7043,7045,7054,7064,7083,7096,7098,7100,7125,7136,7160,7163,7190,7193,7228,7229,7236,7239,7248,7249,7253,7254,7265,7280,7281,7291,7330,7335,7344,7346,7348,7386,7391,7394,7395,7407,7418,7423,7428,7443,7448,7450,7454,7457,7465,7475,7479,7484,7488,7491,7492,7496,7501,7515,7520,7538,7579,7581,7588,7592,7595,7611,7619,7634,7641,7682,7703,7704,7720,7733,7737,7765,7773,7778,7789,7794,7800,7814,7827,7835,7898,7909,7916,7934,7940,7952,7957,7963,7966,7970,7978,7981,7989,8008,8025,8030,8033,8034,8039,8049,8059,8070,8077,8078,8080,8081,8090,8092,8127,8130,8132,8156,8162,8165,8177,8183,8190,8193,8212,8216,8219,8229,8246,8250,8258,8261,8279,8303,8321,8337,8339,8347,8378,8388,8419,8427,8428,8433,8456,8458,8462,8463,8481,8483,8485,8493,8494,8503,8511,8513,8533,8557,8560,8571,8585,8588,8626,8627,8628,8633,8661,8671,8675,8679,8686,8692,8716,8721,8722,8723,8730,8745,8777,8815,8833,8834,8837,8855,8863,8881,8890,8914,8915,8925,8935,8962,8988,9005,9031,9040,9060,9066,9077,9078,9113,9118,9130,9131,9133,9135,9154,9160,9165,9166,9167,9170,9175,9185,9190,9203,9218,9219,9227,9231,9232,9233,9253,9261,9265,9273,9279,9286,9292,9299,9303,9306,9335,9345,9352,9362,9392,9397,9410,9411,9413,9436,9461,9470,9477,9486,9515,9520,9526,9533,9554,9560,9574,9581,9584,9596,9606,9608,9609,9614,9619,9631,9640,9652,9653,9663,9664,9717,9742,9756,9760,9771,9776,9790,9793,9835,9852,9853,9861,9880,9883,9889,9909,9918,9919,9937,9941,9945,9947,9960,9975,9978,9982,9996], size=948
removeMin测试成功
DefaultArray(data=[9985,9960,9946,9943,9940,9933,9931,9919,9911,9906,9905,9903,9896,9882,9867,9866,9849,9840,9824,9823,9820,9817,9814,9813,9774,9770,9764,9763,9734,9698,9692,9688,9677,9675,9670,9662,9653,9645,9612,9591,9582,9581,9554,9548,9542,9520,9515,9492,9468,9439,9420,9419,9415,9400,9385,9383,9372,9345,9330,9318,9295,9278,9268,9267,9263,9256,9210,9208,9206,9197,9192,9191,9164,9154,9151,9147,9145,9124,9117,9098,9084,9074,9068,9064,9034,9028,9024,9021,8967,8950,8946,8907,8903,8884,8880,8876,8872,8869,8865,8852,8850,8839,8838,8827,8825,8821,8807,8806,8804,8803,8796,8791,8782,8776,8756,8753,8744,8728,8727,8726,8709,8704,8702,8693,8685,8684,8673,8668,8653,8604,8600,8580,8579,8562,8552,8548,8547,8532,8531,8523,8522,8518,8509,8488,8453,8427,8424,8409,8400,8384,8369,8356,8350,8341,8322,8317,8290,8284,8280,8266,8260,8255,8250,8231,8202,8196,8191,8190,8173,8143,8129,8117,8096,8094,8092,8066,8052,8046,8037,8036,8024,8021,8012,8006,7994,7991,7982,7981,7967,7956,7951,7946,7921,7916,7876,7869,7864,7862,7852,7838,7837,7835,7833,7825,7824,7821,7807,7790,7736,7717,7715,7706,7691,7686,7676,7675,7663,7641,7637,7635,7615,7606,7596,7591,7587,7569,7540,7529,7513,7509,7508,7507,7491,7485,7480,7475,7470,7460,7429,7426,7425,7401,7400,7379,7372,7363,7344,7343,7339,7307,7306,7295,7290,7287,7283,7276,7256,7224,7223,7220,7203,7199,7192,7172,7168,7167,7164,7155,7144,7143,7137,7124,7086,7082,7072,7058,7044,7025,7023,7022,7018,7003,6998,6996,6989,6985,6971,6965,6958,6937,6932,6926,6913,6910,6909,6906,6894,6892,6862,6848,6839,6837,6836,6832,6824,6823,6821,6812,6787,6776,6771,6763,6749,6748,6745,6736,6725,6723,6717,6714,6711,6688,6672,6653,6649,6640,6635,6625,6623,6617,6612,6611,6600,6594,6546,6544,6537,6522,6520,6500,6490,6473,6451,6444,6441,6437,6436,6417,6405,6370,6366,6361,6359,6358,6355,6333,6326,6309,6302,6285,6265,6248,6235,6234,6224,6219,6216,6209,6196,6182,6174,6169,6168,6165,6153,6147,6141,6139,6131,6121,6095,6071,6047,6038,6027,6025,6018,6012,5975,5970,5965,5964,5959,5957,5930,5926,5920,5914,5911,5907,5902,5900,5891,5868,5848,5807,5774,5768,5758,5748,5736,5684,5682,5669,5665,5660,5644,5640,5639,5637,5636,5634,5616,5606,5586,5585,5566,5553,5535,5527,5524,5514,5496,5488,5480,5455,5450,5446,5442,5420,5369,5367,5363,5356,5320,5317,5293,5279,5247,5237,5231,5216,5208,5206,5184,5180,5168,5159,5144,5137,5123,5091,5088,5085,5084,5081,5067,5061,5026,5015,5007,5002,4992,4986,4980,4976,4975,4946,4945,4935,4934,4932,4926,4922,4912,4895,4890,4886,4872,4870,4844,4831,4795,4790,4786,4766,4756,4753,4738,4737,4721,4717,4711,4709,4693,4682,4674,4669,4668,4619,4615,4591,4590,4587,4586,4583,4581,4553,4547,4544,4541,4540,4526,4515,4501,4475,4468,4453,4411,4402,4391,4384,4361,4355,4354,4338,4331,4323,4321,4318,4315,4311,4307,4274,4270,4268,4264,4263,4253,4248,4232,4226,4225,4223,4203,4192,4166,4158,4152,4148,4127,4091,4080,4079,4076,4038,4037,4026,4013,3996,3985,3969,3956,3950,3939,3938,3936,3930,3906,3897,3876,3868,3851,3844,3843,3816,3802,3801,3799,3782,3781,3780,3774,3767,3765,3764,3753,3750,3749,3741,3731,3729,3722,3715,3706,3697,3665,3664,3657,3647,3625,3624,3623,3609,3599,3594,3574,3571,3554,3552,3548,3542,3531,3519,3508,3479,3472,3464,3451,3449,3444,3436,3427,3420,3417,3416,3366,3358,3329,3321,3318,3316,3289,3257,3246,3243,3221,3210,3206,3201,3192,3161,3149,3132,3121,3115,3106,3093,3090,3077,3075,3064,3063,3050,3041,3021,3019,3017,3014,3008,2999,2964,2953,2942,2904,2903,2894,2871,2862,2854,2853,2836,2826,2795,2788,2773,2765,2763,2748,2730,2714,2703,2695,2652,2650,2637,2636,2622,2621,2603,2591,2581,2579,2576,2575,2571,2563,2551,2543,2535,2524,2513,2500,2491,2490,2482,2467,2464,2462,2455,2454,2448,2431,2427,2424,2383,2370,2356,2352,2329,2311,2303,2283,2273,2271,2269,2251,2249,2203,2201,2195,2177,2175,2161,2151,2142,2135,2120,2110,2100,2094,2087,2082,2078,2077,2070,2063,2055,2050,2032,2027,2026,2009,2001,1955,1944,1941,1938,1923,1912,1890,1878,1877,1871,1865,1859,1844,1830,1827,1824,1799,1798,1795,1779,1769,1762,1728,1709,1706,1703,1700,1687,1660,1622,1616,1610,1593,1559,1540,1533,1532,1524,1513,1506,1492,1486,1467,1457,1433,1423,1413,1387,1384,1375,1366,1360,1358,1357,1342,1331,1320,1309,1307,1304,1296,1295,1259,1227,1222,1205,1193,1182,1165,1141,1130,1125,1123,1118,1107,1103,1098,1088,1080,1065,1063,1059,1027,1019,998,978,959,958,946,941,938,931,927,908,907,901,898,895,890,883,869,859,858,848,843,836,831,810,802,775,758,751,737,735,729,728,721,706,702,683,670,640,629,620,584,554,548,542,538,537,521,503,501,487,484,478,477,476,449,441,427,424,416,400,393,377,367,358,346,323,310,293,292,280,274,263,251,244,235,224,219,205,190,176,175,154,149,138,134,125,118,109,105,102,99,96,93,85,77,74,64,41,37,10,2], size=949
removeMax测试成功
二分搜索树前、中、后序遍历的说明
在下面这张图中，每个节点左边的点，代表第一次访问该节点；中间的点代表第二次访问该节点，右边的点代表第三次访问该节点。而它们的访问顺序都是从根节点开始从左子树，访问到右子树。
这是一颗二分搜索树，我们先来看一下前序遍历——28、16、13、22、30、29、42
而前序遍历就是在第一次访问中发现的节点全部记录下来，而其他次访问的时候全部无视。
中序遍历——13、16、22、28、29、30、42
中序遍历跟前序遍历的顺序是一样，不同的是它是第二次发现节点的时候才记录下来。这里需要注意的时候当访问到叶节点的时候，左边的紫色点代表第一次访问，随后马上就会第二次访问同一个节点，代表中间的蓝色点。
后序遍历——13、22、16、29、42、30、28
后序遍历跟前序遍历的顺序是一样，不同的是它是第三次发现节点的时候才记录下来。
- 二分搜索树集合的封装
集合是一种不包含重复元素的数据结构
接口
public interface Set<T> { void add(T t); void remove(T t); boolean contains(T t); int getSize(); boolean isEmpty(); }
实现类
public class BSTSet<T extends Comparable<T>> implements Set<T> { private Tree<T> bst; public BSTSet() { bst = new BST<>(); } @Override public void add(T value) { bst.add(value); } @Override public void remove(T value) { bst.remove(value); } @Override public boolean contains(T value) { return bst.contains(value); } @Override public int getSize() { return bst.getSize(); } @Override public boolean isEmpty() { return bst.isEmpty(); } }
调用
我们会先从一本《傲慢与偏见》的英文电子书中读出多少个单词，然后放入集合中，查看有多少不重复的单词。
文件读取
public class FileOperation { /** * 读取文件名称为filename中的内容，并将其中包含的所有词语放进words中 * @param filename * @param words * @return */ public static boolean readFile(String filename, Array<String> words) { if (filename == null || words == null) { System.out.println("filename为空或words为空"); return false; } Scanner scanner; try { File file = new File(filename); if (file.exists()) { FileInputStream fis = new FileInputStream(file); scanner = new Scanner(new BufferedInputStream(fis),"UTF-8"); scanner.useLocale(Locale.ENGLISH); }else { return false; } } catch (FileNotFoundException e) { System.out.println("无法打开" + filename); return false; } //简单分词 if (scanner.hasNextLine()) { String contents = scanner.useDelimiter("\\A").next(); int start = firstCharacterIndex(contents,0); for (int i = start + 1;i <= contents.length();) { if (i == contents.length() || !Character.isLetter(contents.charAt(i))) { String word = contents.substring(start,i).toLowerCase(); words.addLast(word); start = firstCharacterIndex(contents,i); i = start + 1; }else { i++; } } } return true; } private static int firstCharacterIndex(String s,int start) { for (int i = start;i < s.length();i++) { if (Character.isLetter(s.charAt(i))) { return i; } } return s.length(); } }
测试
public class SetMain { public static void main(String[] args) { System.out.println("傲慢与偏见"); Array<String> words = new DefaultArray<>(); FileOperation.readFile("/Users/admin/Downloads/pride-and-prejudice.txt",words); System.out.println("共有单词: " + words.getSize()); Set<String> set = new BSTSet<>(); Stream.of(words.getData()).filter(word -> word != null) .forEach(set::add); System.out.println("共有不同的单词: " + set.getSize()); } }
运行结果
傲慢与偏见
共有单词: 125901
共有不同的单词: 6530
- 链表集合的封装
实现类(以下的List和LinkedList皆为之前自主实现的链表封装而非JDK的List接口和LinkedList的实现类)
public class LinkedListSet<T> implements Set<T> { private List<T> list; public LinkedListSet() { list = new LinkedList<>(); } @Override public void add(T value) { if (!list.contains(value)) { list.addFirst(value); } } @Override public void remove(T value) { list.removeElement(value); } @Override public boolean contains(T value) { return list.contains(value); } @Override public int getSize() { return list.getSize(); } @Override public boolean isEmpty() { return list.isEmpty(); } }
调用
public class SetMain { public static void main(String[] args) { System.out.println("傲慢与偏见"); Array<String> words = new DefaultArray<>(); FileOperation.readFile("/Users/admin/Downloads/pride-and-prejudice.txt",words); System.out.println("共有单词: " + words.getSize()); Set<String> set = new LinkedListSet<>(); Stream.of(words.getData()).filter(word -> word != null) .forEach(set::add); System.out.println("共有不同的单词: " + set.getSize()); } }
运行结果
傲慢与偏见
共有单词: 125901
共有不同的单词: 6530
虽然运行结果相同，但我们能明显感觉到在获取不同的单词的时候，运行时间明显偏长。
两种集合的性能测试
public class TestSetMain { private static double testSet(Set<String> set,String filename) { long startTime = System.nanoTime(); System.out.println(filename); Array<String> words = new DefaultArray<>(); if (FileOperation.readFile(filename,words)) { System.out.println("共有单词: " + words.getSize()); Stream.of(words.getData()).filter(data -> data != null) .forEach(set::add); System.out.println("共有不同单词: " + set.getSize()); } long endTime = System.nanoTime(); return (endTime - startTime) / 1000000000.0; } public static void main(String[] args) { String filename = "/Users/admin/Downloads/pride-and-prejudice.txt"; Set<String> bstSet = new BSTSet<>(); double time1 = testSet(bstSet,filename); System.out.println("BST Set: " + time1 + " s"); System.out.println(); Set<String> linkedListSet = new LinkedListSet<>(); double time2 = testSet(linkedListSet,filename); System.out.println("LinkedList Set: " + time2 + " s"); } }
测试结果
/Users/admin/Downloads/pride-and-prejudice.txt
共有单词: 125901
共有不同单词: 6530
BST Set: 0.140089974 s
/Users/admin/Downloads/pride-and-prejudice.txt
共有单词: 125901
共有不同单词: 6530
LinkedList Set: 2.184659522 s
对于LinkedListSet操作的时间复杂度
add(value) O(n)
contains(value) O(n)
remove(value) O(n)
对于BSTSet操作的时间复杂度
add(value) O(h)
contains(value) O(h)
remove(value) O(h)
以上h为二分搜索树的高度。现在我们来看一下h与n的关系是什么。假设一颗二分搜索树是饱和的，如下图所示
假设该二分搜索树共h层
则0层的节点数为 1
1层的节点数为 2
2层的节点数为 4
3层的节点数为 8
4层的节点数为 16
h-1层的节点数为 2^(h-1)
则总节点数 = 2^0 + 2^1 + 2^2 + 2^3 + 2^4+ …… + 2^(h-1),我们可以看到这是一个等比数列，它的公比为2。根据等比数列的求和公式
可得(q为底数，此时q为2;a1为常数，此时a1为1;n为层数，此时为h)，关于该公式的推导可以参考https://www.iqiyi.com/w_19rr8796p1.html ,最后可得
最后可得总节点数n = 2^h - 1,则h = log2(n + 1)，其中红色2为底数。
省略掉常数和底数，最后得到二分搜索树的时间复杂度为O(log n)
对于BSTSet操作的时间复杂度可以改为
add(value) O(log n)
contains(value) O(log n)
remove(value) O(log n)
我们来直观的看一下log n和线性复杂度n的增长情况
log n n
n = 16 4 16 相差4倍
n = 1024 10 1024 相差100倍
n = 100万 20 100万 相差5万倍
以上我们是根据满二分搜索树来推断的，但二分搜索树也有一种最坏的情况，就是它的高度等于它的节点数(h == n)，这样它就退化成了一个链表，这样它的时间复杂度就是O(n)而不是O(log n)了。
LeetCode算法题 https://leetcode-cn.com/problems/unique-morse-code-words/
这是LeetCode的804题——唯一摩尔斯密码词
我们先用JDK的TreeSet来完成。该类是实现了红黑树为底层的集合。(此处的Set为java.util.Set，TreeSet为java.util.TreeSet)
public class Solution { public int uniqueMorseRepresentations(String[] words) { String[] codes = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."}; Set<String> set = new TreeSet<>(); Stream.of(words).forEach(word -> { StringBuilder builder = new StringBuilder(); for (int i = 0;i < word.length();i++) { builder.append(codes[word.charAt(i) - 'a']); } set.add(builder.toString()); }); return set.size(); } }
提交给LeetCode
- 链表映射封装
映射是一种表示key,value键值对的数据结构
接口
public interface Map<K,V> { void add(K key,V value); V remove(K key); boolean contains(K key); V get(K key); void set(K key,V value); int getSize(); boolean isEmpty(); }
实现类
由于映射有两个泛型，所以之前实现的LinkedList将不再复用。
public class LinkedListMap<K,V> implements Map<K,V> { @AllArgsConstructor @Data @NoArgsConstructor private class Node { private K key; private V value; private Node next; public Node(K key) { this(key,null,null); } public Node(K key,V value) { this(key,value,null); } @Override public String toString() { return key.toString() + " : " + value.toString(); } } private Node dummyHead; private int size; public LinkedListMap() { dummyHead = new Node(); size = 0; } @Override public void add(K key, V value) { Node node = getNode(key); if (node == null) { dummyHead.setNext(new Node(key,value,dummyHead.getNext())); size++; }else { node.setValue(value); } } @Override public V remove(K key) { Node pre = dummyHead; while (pre.getNext() != null) { if (key.equals(pre.getNext().getKey())) { Node delNode = pre.getNext(); pre.setNext(delNode.getNext()); delNode.setNext(null); size--; return delNode.getValue(); } pre = pre.getNext(); } return null; } @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.getValue(); } @Override public void set(K key, V value) { Node node = getNode(key); if (node == null) { throw new IllegalArgumentException(key + "不存在"); } node.setValue(value); } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } private Node getNode(K key) { Node cur = dummyHead.getNext(); while (cur != null) { if (key.equals(cur.getKey())) { return cur; } cur = cur.getNext(); } return null; } }
调用
public class MapMain { public static void main(String[] args) { System.out.println("傲慢与偏见"); Array<String> words = new DefaultArray<>(); FileOperation.readFile("/Users/admin/Downloads/pride-and-prejudice.txt",words); System.out.println("共有单词: " + words.getSize()); Map<String,Integer> map = new LinkedListMap<>(); Stream.of(words.getData()).filter(word -> word != null) .forEach(word -> { if (map.contains(word)) { map.set(word,map.get(word) + 1); }else { map.add(word,1); } }); System.out.println("共有不同的单词: " + map.getSize()); System.out.println("pride出现的次数: " + map.get("pride")); System.out.println("prejudice出现的次数: " + map.get("prejudice")); } }
运行结果(时间较慢)
傲慢与偏见
共有单词: 125901
共有不同的单词: 6530
pride出现的次数: 53
prejudice出现的次数: 11
- 二分搜索树映射封装
由于映射有两个泛型，所以之前实现的BST将不再复用
实现类
public class BSTMap<K extends Comparable<K>,V> implements Map<K,V> { @Data @AllArgsConstructor private class Node{ private K key; private V value; private Node left; private Node right; public Node(K key) { this(key,null,null,null); } public Node(K key,V value) { this(key,value,null,null); } } private Node root; private int size; public BSTMap() { root = null; size = 0; } @Override public void add(K key, V value) { root = add(root,key,value); } private Node add(Node node, K key,V value) { //递归终止条件 if (node == null) { size++; return new Node(key,value); } //递归 if (key.compareTo(node.getKey()) < 0) { node.setLeft(add(node.getLeft(),key,value)); }else if (key.compareTo(node.getKey()) > 0) { node.setRight(add(node.getRight(),key,value)); }else { node.setValue(value); } return node; } @Override public V remove(K key) { Node node = getNode(root,key); if (node != null) { root = remove(root,key); return node.getValue(); } return null; } private Node remove(Node node,K key) { if (node == null) { return null; } if (key.compareTo(node.getKey()) < 0) { node.setLeft(remove(node.getLeft(),key)); return node; }else if (key.compareTo(node.getKey()) > 0) { node.setRight(remove(node.getRight(),key)); return node; }else { //待删除节点左子树为空的情况 if (node.getLeft() == null) { Node rightNode = node.getRight(); node.setRight(null); size--; return rightNode; } //待删除节点右子树为空的情况 if (node.getRight() == null) { Node leftNode = node.getLeft(); node.setLeft(null); size--; return leftNode; } //待删除节点左右子树均不为空的情况 //找到比待删除节点大的最小节点，即待删除节点右子树的最小节点 //用这个节点顶替待删除节点的位置 Node successor = minimum(node.getRight()); successor.setRight(removeMin(node.getRight())); successor.setLeft(node.getLeft()); node.setLeft(null); node.setRight(null); return successor; } } private Node minimum(Node node) { if (node.getLeft() == null) { return node; } return minimum(node.getLeft()); } private Node removeMin(Node node) { if (node.getLeft() == null) { Node rightNode = node.getRight(); node.setRight(null); size--; return rightNode; } node.setLeft(removeMin(node.getLeft())); return node; } @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.getValue(); } @Override public void set(K key, V value) { Node node = getNode(root,key); if (node == null) { throw new IllegalArgumentException(key + "不存在"); } node.setValue(value); } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } private Node getNode(Node node,K key) { if (node == null) { return null; } if (key.compareTo(node.getKey()) == 0) { return node; }else if (key.compareTo(node.getKey()) < 0) { return getNode(node.getLeft(),key); }else { return getNode(node.getRight(),key); } } }
调用
public class MapMain { public static void main(String[] args) { System.out.println("傲慢与偏见"); Array<String> words = new DefaultArray<>(); FileOperation.readFile("/Users/admin/Downloads/pride-and-prejudice.txt",words); System.out.println("共有单词: " + words.getSize()); Map<String,Integer> map = new BSTMap<>(); Stream.of(words.getData()).filter(word -> word != null) .forEach(word -> { if (map.contains(word)) { map.set(word,map.get(word) + 1); }else { map.add(word,1); } }); System.out.println("共有不同的单词: " + map.getSize()); System.out.println("pride出现的次数: " + map.get("pride")); System.out.println("prejudice出现的次数: " + map.get("prejudice")); } }
运行结果(时间较快)
傲慢与偏见
共有单词: 125901
共有不同的单词: 6530
pride出现的次数: 53
prejudice出现的次数: 11
两种映射的性能测试
public class TestMapMain { private static double testMap(Map<String,Integer> map,String filename) { long startTime = System.nanoTime(); System.out.println(filename); Array<String> words = new DefaultArray<>(); FileOperation.readFile(filename,words); System.out.println("共有单词: " + words.getSize()); Stream.of(words.getData()).filter(word -> word != null) .forEach(word -> { if (map.contains(word)) { map.set(word,map.get(word) + 1); }else { map.add(word,1); } }); System.out.println("共有不同的单词: " + map.getSize()); System.out.println("pride出现的次数: " + map.get("pride")); System.out.println("prejudice出现的次数: " + map.get("prejudice")); long endTime = System.nanoTime(); return (endTime - startTime) / 1000000000.0; } public static void main(String[] args) { String filename = "/Users/admin/Downloads/pride-and-prejudice.txt"; Map<String,Integer> bstMap = new BSTMap<>(); double time1 = testMap(bstMap,filename); System.out.println("BST Map: " + time1 + " s"); Map<String,Integer> linkedListMap = new LinkedListMap<>(); double time2 = testMap(linkedListMap,filename); System.out.println("LinkedList Map: " + time2 + " s"); } }
测试结果
/Users/admin/Downloads/pride-and-prejudice.txt
共有单词: 125901
共有不同的单词: 6530
pride出现的次数: 53
prejudice出现的次数: 11
BST Map: 0.178329962 s
/Users/admin/Downloads/pride-and-prejudice.txt
共有单词: 125901
共有不同的单词: 6530
pride出现的次数: 53
prejudice出现的次数: 11
LinkedList Map: 9.18811603 s
对于LinkedListMap各操作的时间复杂度
add(key,value) O(n)
remove(key) O(n)
contains(key) O(n)
get(key) O(n)
set(key,value) O(n)
对于BSTMap各操作的时间复杂度
add(key,value) O(log n) 平均 O(n) 最差
remove(key) O(log n) 平均 O(n) 最差
contains(key) O(log n) 平均 O(n) 最差
get(key) O(log n) 平均 O(n) 最差
set(key,value) O(log n) 平均 O(n) 最差
LeetCode算法题 https://leetcode-cn.com/problems/intersection-of-two-arrays/
这是LeetCode的第349题——两个数组的交集
我们先用JDK的TreeSet来完成。该类是实现了红黑树为底层的集合。(此处的Set为java.util.Set，TreeSet为java.util.TreeSet,List为java.util.List，ArrayList为java.util.ArrayList)
class Solution { public int[] intersection(int[] nums1, int[] nums2) { Set<Integer> set = new TreeSet<>(); for (int num : nums1) { set.add(num); } List<Integer> list = new ArrayList<>(); for (int num : nums2) { if (set.contains(num)) { list.add(num); set.remove(num); } } int[] res = new int[list.size()]; for (int i = 0;i < list.size();i++) { res[i] = list.get(i); } return res; } }
提交给LeetCode
LeetCode算法题 https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/
这是LeetCode的350题——两个数组的交集II
我们先用JDK的TreeMap来完成，该类是实现了红黑树为底层的映射。(此处的Map为java.util.Map，TreeMap为java.util.TreeMap，List为java.util.List，ArrayList为java.util.ArrayList)
class Solution { public int[] intersect(int[] nums1, int[] nums2) { Map<Integer,Integer> map = new TreeMap<>(); for (int num : nums1) { if (map.putIfAbsent(num,1) != null) { map.put(num,map.get(num) + 1); } } List<Integer> list = new ArrayList<>(); for (int num : nums2) { if (map.containsKey(num)) { list.add(num); map.put(num,map.get(num) - 1); if (map.get(num) == 0) { map.remove(num); } } } int[] ret = new int[list.size()]; for (int i = 0;i < list.size();i++) { ret[i] = list.get(i); } return ret; } }
提交到LeetCode
- 最大堆封装
堆是一种完全二叉树，完全二叉树就是从根节点依次向下层，每一层从左到右依次填充元素的二叉树。完全二叉树可以不是满二叉树。而最大堆的特性是某个节点的值总是不大于其父节点的值。
类似于上图这种就是一个最大堆，它同时满足了完全二叉树的特性。在最大堆中，并不是说上层的节点值一定比下层的节点值要大，而是每一个节点值不比其父节点大。由于其依次填充性，我们也可以用数组来看待这个最大堆。所以我们可以用数组来做最大堆的底层实现，二叉树中父节点，左右子节点的索引关系可以表示为：已知一个节点的索引i(无论它是左节点还是右节点)，它的父节点的索引为 (根节点的索引为0)
parent(i) = (i - 1) / 2
已知一个父节点的索引i，其左右子节点的索引为
left child = 2 * i + 1
right child = 2 * i + 2
接口
public interface Heap<T> { int getSize(); boolean isEmpty(); void add(T t); /** * 取出最大元素(最大堆)或最小元素(最小堆) * @return */ T extract(); /** * 查看最大元素(最大堆)或最小元素(最小堆) * @return */ T findHeap(); /** * 取出堆中最大元素(最大堆)或最小元素(最小堆) * 并且替换成元素t * @param t * @return */ T replace(T t); }
实现类
public class MaxHeap<T extends Comparable<T>> implements Heap<T> { private Array<T> data; public MaxHeap(int capacity) { data = new DefaultArray<>(capacity); } public MaxHeap() { data = new DefaultArray<>(); } /** * 将任意一个数组转化成最大堆,此种方式称为Heapify * 过程为先找到非叶节点的最后一个节点，依次向根节点遍历， * 将每一个节点浮动下沉，即可完成任意数组向最大堆的转化 * 找最后一个非叶节点的方法即为找到最后一个叶节点(数组的最后一个索引size-1) * 的父节点 * 将n个元素逐一插入到一个空堆中，时间复杂度为O(nlog n) * heapify的过程，时间复杂度为O(n) * @param arr */ public MaxHeap(T[] arr) { data = new DefaultArray<>(arr); for (int i = parent(getSize() - 1);i >= 0;i--) { siftDown(i); } } @Override public int getSize() { return data.getSize(); } @Override public boolean isEmpty() { return data.isEmpty(); } @Override public void add(T value) { data.addLast(value); siftUp(data.getSize() - 1); } /** * 堆节点浮动上移 * @param index */ private void siftUp(int index) { while (index > 0 && data.get(parent(index)).compareTo(data.get(index)) < 0) { data.swap(index,parent(index)); index = parent(index); } } @Override public T extract() { T ret = findHeap(); data.swap(0,data.getSize() - 1); data.removeLast(); siftDown(0); return ret; } /** * 堆节点浮动下沉 * @param index */ private void siftDown(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 = rightChile(index); } //data[j]是左右孩子的最大值 if (data.get(index).compareTo(data.get(j)) >= 0) { break; } data.swap(index,j); index = j; } } @Override public T findHeap() { if (isEmpty()) { throw new IllegalArgumentException("堆为空，不能做此操作"); } return data.get(0); } @Override public T replace(T value) { T ret = findHeap(); data.set(0,value); siftDown(0); return ret; } /** * 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引 * @param index * @return */ private int parent(int index) { if (index == 0) { throw new IllegalArgumentException("索引0没有父节点"); } return (index - 1) / 2; } /** * 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引 * @param index * @return */ private int leftChild(int index) { return index * 2 + 1; } /** * 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引 * @param index * @return */ private int rightChile(int index) { return index * 2 + 2; } }
调用
public class HeapMain { public static void main(String[] args) { int n = 1000000; Heap<Integer> maxHeap = new MaxHeap<>(); Random random = new Random(); for (int i = 0;i < n;i++) { maxHeap.add(random.nextInt(Integer.MAX_VALUE)); } int[] arr = new int[n]; for (int i = 0;i < n;i++) { arr[i] = maxHeap.extract(); } for (int i = 1;i < n;i++) { if (arr[i - 1] < arr[i]) { throw new IllegalArgumentException("出错"); } } System.out.println("测试最大堆完成"); } }
运行结果
测试最大堆完成
对Heapify和非Heapify两种数组转化最大堆的测试
public class TestHeapMain { private static double testHeap(Integer[] testData,boolean isHeapify) { long startTime = System.nanoTime(); Heap<Integer> maxHeap; if (isHeapify) { maxHeap = new MaxHeap<>(testData); }else { maxHeap = new MaxHeap<>(); Stream.of(testData).forEach(maxHeap::add); } int[] arr = new int[testData.length]; for (int i = 0;i < testData.length;i++) { arr[i] = maxHeap.extract(); } for (int i = 1;i < testData.length;i++) { if (arr[i - 1] < arr[i]) { throw new IllegalArgumentException("错误"); } } System.out.println("测试最大堆成功"); long endTime = System.nanoTime(); return (endTime - startTime) / 1000000000.0; } public static void main(String[] args) { int n = 1000000; Random random = new Random(); Integer[] testData = new Integer[n]; for (int i = 0;i < n;i++) { testData[i] = random.nextInt(Integer.MAX_VALUE); } double time1 = testHeap(testData,false); System.out.println("不使用heapify: " + time1 + " s"); System.out.println(); double time2 = testHeap(testData,true); System.out.println("使用heapify: " + time2 + " s"); } }
测试结果
测试最大堆成功
不使用heapify: 0.876574063 s
测试最大堆成功
使用heapify: 0.496209799 s
- 优先队列封装
实现类
public class PriorityQueue<T extends Comparable<T>> implements Queue<T> { private Heap<T> heap; public PriorityQueue() { heap = new MaxHeap<>(); } @Override public void enqueue(T value) { heap.add(value); } @Override public T dequeue() { return heap.extract(); } @Override public T getFront() { return heap.findHeap(); } @Override public int getSize() { return heap.getSize(); } @Override public boolean isEmpty() { return heap.isEmpty(); } }
LeetCode算法题 https://leetcode-cn.com/problems/top-k-frequent-elements/
这是LeetCode的第347题——前K个高频元素
我们先用JDK的优先队列来完成，该优先队列使用的是平衡二叉最小堆来完成的。这里的所有类型皆为JDK自带类型，均为java.util包中。
class Solution { /** * 频次 */ private class Freq implements Comparable<Freq> { private int e; private int freq; public Freq(int e, int freq) { this.e = e; this.freq = freq; } public int getE() { return e; } public void setE(int e) { this.e = e; } public int getFreq() { return freq; } public void setFreq(int freq) { this.freq = freq; } @Override public int compareTo(Freq o) { if (this.freq < o.freq) { return -1; }else if (this.freq > o.freq) { return 1; }else { return 0; } } } public List<Integer> topKFrequent(int[] nums, int k) { Map<Integer,Integer> map = new TreeMap<>(); for (int num : nums) { if (map.putIfAbsent(num,1) != null) { map.put(num,map.get(num) + 1); } } Queue<Freq> pq = new PriorityQueue<>(); map.keySet().stream().forEach(key -> { if (pq.size() < k) { pq.add(new Freq(key,map.get(key))); }else if (map.get(key) > pq.peek().getFreq()) { pq.poll(); pq.add(new Freq(key,map.get(key))); } }); List<Integer> res = new LinkedList<>(); while (!pq.isEmpty()) { res.add(pq.poll().getE()); } return res; } }
提交给LeetCode
- 线段树封装
当我们在一个区间中进行统计和查询的时候，比如查询一个区间[i,j]的最大值，最小值，或者区间数字和，如果使用数组来遍历的话，它是一个O(n)的时间复杂度，但如果使用线段树，则时间复杂度就会减少到O(log n)级别。在线段树的应用中，区间本身是固定的，不考虑向区间中增加，删除元素的操作。
如果上图是一个求和的线段树，则根节点是整个区间A[0-7]所有元素的和，而下面的非叶节点分支则是不同中间分区间的元素的和。但并非所有的线段树都是一颗满二叉树。
由上图可以看到，线段树也不是一颗完全二叉树，但线段树是平衡二叉树。所谓平衡二叉树是指不同叶节点的深度最大不超过1。所以之前所说的堆也是平衡二叉树，但二分搜索树可能不是一颗平衡二叉树。虽然线段树不是完全二叉树，但依然可以用数组的形式来表示，我们可以将其看作是一颗满二叉树，只不过缺失的节点用空来表示。
如果区间有n个元素，用数组来组成线段树，根据满二叉树的原理，如果元素个数n刚好为2^k次幂个(如8个，16个)，则组成线段树的数组空间需要2n，因为上层节点数之和约等于叶节点数(如叶节点是8的时候，上层节点数之和为7)。而元素个数不为2^k次幂时，就需要增加一排叶节点来组成满二叉树，而增加的这一排就会约等于上层满二叉树的节点数之和，上层满二叉树之和为2n,则组成线段树的数组空间需要4n。
接口
public interface SegmentTree<T> { T get(int index); int getSize(); /** * 返回区间[queryL,queryR]的值 * @param queryL * @param queryR * @return */ T query(int queryL,int queryR); void set(int index,T t); }
实现类
public class DefaultSegmentTree<T> implements SegmentTree<T> { /** * 区间元素 */ private T[] data; /** * 线段树 */ private T[] tree; /** * 函数式接口，继承于BiFunction，用做线段树规则(求和，求最大，最小等等) */ private BinaryOperator<T> merger; @SuppressWarnings("unchecked") public DefaultSegmentTree(T[] data,BinaryOperator<T> merger) { this.merger = merger; this.data = (T[]) new Object[data.length]; for (int i = 0;i < data.length;i++) { this.data[i] = data[i]; } tree = (T[]) new Object[data.length * 4]; buildSegmentTree(0,0,data.length - 1); } /** * 在treeIndex的位置创建表示区间[l...r]的线段树 * @param treeIndex 根节点的索引 * @param l 区间左边界 * @param r 区间右边界 */ private void buildSegmentTree(int treeIndex,int l,int r) { if (l == r) { tree[treeIndex] = data[l]; return; } int leftTreeIndex = leftChild(treeIndex); int rightTreeIndex = rightChile(treeIndex); int mid = l + (r - l) / 2; buildSegmentTree(leftTreeIndex,l,mid); buildSegmentTree(rightTreeIndex,mid + 1,r); tree[treeIndex] = merger.apply(tree[leftTreeIndex],tree[rightTreeIndex]); } @Override public T get(int index) { if (index < 0 || index >= data.length) { throw new IllegalArgumentException("索引非法"); } return data[index]; } @Override public int getSize() { return data.length; } @Override public T query(int queryL, int queryR) { if (queryL < 0 || queryL >= data.length || queryR < 0 || queryR >= data.length || queryL > queryR) { throw new IllegalArgumentException("索引非法"); } return query(0,0,data.length - 1,queryL,queryR); } /** * 在以treeID为根的线段树中[l...r]的范围里，搜索区间[queryL...queryR]的值 * @param treeIndex 根节点的索引 * @param l 区间的左边界 * @param r 区间的右边界 * @param queryL 查询的左边界 * @param queryR 查询的右边界 * @return */ private T query(int treeIndex,int l,int r,int queryL,int queryR) { if (l == queryL && r == queryR) { return tree[treeIndex]; } int mid = l + (r - l) / 2; int leftTreeIndex = leftChild(treeIndex); int rightTreeIndex = rightChile(treeIndex); if (queryL >= mid + 1) { return query(rightTreeIndex,mid + 1,r,queryL,queryR); }else if (queryR <= mid) { return query(leftTreeIndex,l,mid,queryL,queryR); } T leftResult = query(leftTreeIndex, l, mid, queryL, mid); T rightResult = query(rightTreeIndex, mid + 1, r, mid + 1, queryR); return merger.apply(leftResult,rightResult); } @Override public void set(int index, T value) { if (index < 0 || index >= data.length) { throw new IllegalArgumentException("索引非法"); } data[index] = value; set(0,0,data.length - 1,index,value); } /** * 在以treeIndex为根的线段树中更新index的值为value * @param treeIndex * @param l * @param r * @param index * @param value */ private void set(int treeIndex,int l,int r,int index,T value) { if (l == r) { tree[treeIndex] = value; return; } int mid = l + (r - l) / 2; int leftTreeIndex = leftChild(treeIndex); int rightTreeIndex = rightChile(treeIndex); if (index >= mid + 1) { set(rightTreeIndex,mid + 1,r,index,value); }else { set(leftTreeIndex,l,mid,index,value); } tree[treeIndex] = merger.apply(tree[leftTreeIndex],tree[rightTreeIndex]); } /** * 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引 * @param index * @return */ private int leftChild(int index) { return index * 2 + 1; } /** * 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引 * @param index * @return */ private int rightChile(int index) { return index * 2 + 2; } @Override public String toString() { return "DefaultSegmentTree{" + "tree=" + Arrays.toString(tree) + '}'; } }
调用
public class SegmentTreeMain { public static void main(String[] args) { Integer[] nums = {-2,0,3,-5,2,-1}; SegmentTree<Integer> segmentTree = new DefaultSegmentTree<>(nums,(x,y) -> x + y); System.out.println(segmentTree); System.out.println(segmentTree.query(0,2)); segmentTree.set(3,5); System.out.println(segmentTree); System.out.println(segmentTree.query(1,4)); } }
运行结果
DefaultSegmentTree{tree=[-3, 1, -4, -2, 3, -3, -1, -2, 0, null, null, -5, 2, null, null, null, null, null, null, null, null, null, null, null]}
1
DefaultSegmentTree{tree=[7, 1, 6, -2, 3, 7, -1, -2, 0, null, null, 5, 2, null, null, null, null, null, null, null, null, null, null, null]}
10
从结果可以看到-3为所有元素的和。1为前3个元素的和，-4为后3个元素的和。而我们要查询的0到2区间的和为1。-5变更为5后，整个线段树重新变更结果。
LeetCode算法题 https://leetcode-cn.com/problems/range-sum-query-immutable/
这是LeetCode算法题的303题——区域和检索-数组不可变
这里我们就使用线段树来完成。
class NumArray { private SegmentTree<Integer> segmentTree; public NumArray(int[] nums) { if (nums.length > 0) { Integer[] data = new Integer[nums.length]; for (int i = 0;i < nums.length;i++) { data[i] = nums[i]; } segmentTree = new DefaultSegmentTree<>(data,(x, y) -> x + y); } } public int sumRange(int i, int j) { if (segmentTree == null) { throw new IllegalArgumentException("线段树为空"); } return segmentTree.query(i,j); } }
提交给LeetCode(提交的时候需要把线段树的接口以及实现类以私有方式放入NumArray类中)
不使用线段树，而采用预处理来完成
class NumArray { //预处理，sum[i]存储前i个元素和，sum[0] = 0 //sum[i]存储nums[0...i-1]的和 private int[] sum; public NumArray(int[] nums) { sum = new int[nums.length + 1]; sum[0] = 0; for (int i = 1;i < sum.length;i++) { sum[i] = sum[i - 1] + nums[i - 1]; } } public int sumRange(int i, int j) { return sum[j + 1] - sum[i]; } }
提交给LeetCode
LeetCode算法题 https://leetcode-cn.com/problems/range-sum-query-mutable/
这是LeetCode的第307题——区域和检索-数组可修改
我们依然使用线段树来处理
class NumArray { private SegmentTree<Integer> segmentTree; public NumArray(int[] nums) { if (nums.length > 0) { Integer[] data = new Integer[nums.length]; for (int i = 0;i < nums.length;i++) { data[i] = nums[i]; } segmentTree = new DefaultSegmentTree<>(data,(x,y) -> x + y); } } public void update(int i, int val) { if (segmentTree == null) { throw new IllegalArgumentException("线段树为空"); } segmentTree.set(i,val); } public int sumRange(int i, int j) { if (segmentTree == null) { throw new IllegalArgumentException("线段树为空"); } return segmentTree.query(i,j); } }
提交给LeetCode(提交的时候需要把线段树的接口以及实现类以私有方式放入NumArray类中)
- 字典树封装
字典树是一种查询每一个条目的时间复杂度，和字典中一共有多少条目无关的数据结构。而其时间复杂度为O(w),w为查询单词的长度。字典树是一个多叉树，对于小写英文字母来说，可以有26个指向下个节点的指针。
接口
public interface Trie { int getSize(); void add(String word); boolean contains(String word); boolean isEmpty(); boolean isPrefix(String prefix); void remove(String word); }
实现类(此处的Map和TreeMap皆为JDK内置)
public class DefaultTrie implements Trie { @Data private class Node { //单词节点的末尾 private Boolean word; private Map<Character,Node> next; public Node(boolean word) { this.word = word; next = new TreeMap<>(); } public Node() { this(false); } } private Node root; private int size; public DefaultTrie() { root = new Node(); size = 0; } @Override public int getSize() { return size; } @Override public void add(String word) { Node cur = root; for (int i = 0;i < word.length();i++) { char c = word.charAt(i); cur.getNext().putIfAbsent(c,new Node()); cur = cur.getNext().get(c); } if (!cur.getWord()) { cur.setWord(true); size++; } } @Override public boolean contains(String word) { Node cur = root; for (int i = 0;i < word.length();i++) { char c = word.charAt(i); if (cur.getNext().get(c) == null) { return false; } cur = cur.getNext().get(c); } return cur.getWord(); } @Override public boolean isEmpty() { return size == 0; } @Override public boolean isPrefix(String prefix) { Node cur = root; for (int i = 0;i < prefix.length();i++) { char c = prefix.charAt(i); if (cur.getNext().get(c) == null) { return false; } cur = cur.getNext().get(c); } return true; } @Override public void remove(String word) { if (contains(word)) { remove(word,word.length() - 1); } } private void remove(String word,int index) { if (index + 1 == word.length()) { Node node = get(word,index); char c = word.charAt(index); if (node.getNext().size() == 1 && mapIsEmpty(node.getNext().get(c).getNext())) { node.setNext(null); }else if (node.getNext().size() == 1 && node.getNext().get(c).getWord()) { node.getNext().get(c).setWord(false); size--; return; }else { node.getNext().remove(c); size--; return; } word = word.substring(0,word.length() - 1); } remove(word,index - 1); } private Node get(String word,int index) { Node cur = root; for (int i = 0;i < index;i++) { char c = word.charAt(i); cur = cur.getNext().get(c); } return cur; } private boolean mapIsEmpty(Map<?, ?> map) { return map == null || map.isEmpty(); } @Override public String toString() { return "DefaultTrie{" + "root=" + root + ", size=" + size + '}'; } }
调用
public class TrieMain { public static void main(String[] args) { System.out.println("傲慢与偏见"); Array<String> words = new DefaultArray<>(); FileOperation.readFile("/Users/admin/Downloads/pride-and-prejudice.txt",words); System.out.println("共有单词: " + words.getSize()); Trie trie = new DefaultTrie(); Stream.of(words.getData()).filter(word -> word != null) .forEach(trie::add); System.out.println("共有不同的单词: " + trie.getSize()); } }
运行结果
傲慢与偏见
共有单词: 125901
共有不同的单词: 6530
删除测试
public class TrieRemoveMain { public static void main(String[] args) { Trie trie = new DefaultTrie(); trie.add("adfatr"); trie.add("adfadhy");; trie.add("adfasd"); trie.remove("adfadhy"); System.out.println(trie); } }
运行结果
DefaultTrie{root=DefaultTrie.Node(word=false, next={a=DefaultTrie.Node(word=false, next={d=DefaultTrie.Node(word=false, next={f=DefaultTrie.Node(word=false, next={a=DefaultTrie.Node(word=false, next={s=DefaultTrie.Node(word=false, next={d=DefaultTrie.Node(word=true, next={})}), t=DefaultTrie.Node(word=false, next={r=DefaultTrie.Node(word=true, next={})})})})})})}), size=2}
由于字典树的设计有可能占用空间过大，所以有一种设计为压缩字典树
关于压缩字典树的应用可以参考字典树收集(初步读写锁实现线程安全,待续)
LeetCode算法题 https://leetcode-cn.com/problems/implement-trie-prefix-tree/
这是LeetCode的208题——实现Trie(前缀树)
该题跟我们实现的字典树完全一样,只是方法名称不同。
class Trie { private class Node { //单词节点的末尾 private Boolean word; private Map<Character,Node> next; public Node(boolean word) { this.word = word; next = new TreeMap<>(); } public Node() { this(false); } public Boolean getWord() { return word; } public void setWord(Boolean word) { this.word = word; } public Map<Character, Node> getNext() { return next; } public void setNext(Map<Character, Node> next) { this.next = next; } } private Node root; /** Initialize your data structure here. */ public Trie() { root = new Node(); } /** Inserts a word into the trie. */ public void insert(String word) { Node cur = root; for (int i = 0;i < word.length();i++) { char c = word.charAt(i); cur.getNext().putIfAbsent(c,new Node()); cur = cur.getNext().get(c); } if (!cur.getWord()) { cur.setWord(true); } } /** Returns if the word is in the trie. */ public boolean search(String word) { Node cur = root; for (int i = 0;i < word.length();i++) { char c = word.charAt(i); if (cur.getNext().get(c) == null) { return false; } cur = cur.getNext().get(c); } return cur.getWord(); } /** Returns if there is any word in the trie that starts with the given prefix. */ public boolean startsWith(String prefix) { Node cur = root; for (int i = 0;i < prefix.length();i++) { char c = prefix.charAt(i); if (cur.getNext().get(c) == null) { return false; } cur = cur.getNext().get(c); } return true; } }
提交给LeetCode
LeetCode算法题 https://leetcode-cn.com/problems/add-and-search-word-data-structure-design/
这是LeetCode的第211题——添加与搜索单词-数据结构设计
这道题的重点依然是递归的使用
class WordDictionary { private class Node { //单词节点的末尾 private Boolean word; private Map<Character,Node> next; public Node(boolean word) { this.word = word; next = new TreeMap<>(); } public Node() { this(false); } public Boolean getWord() { return word; } public void setWord(Boolean word) { this.word = word; } public Map<Character, Node> getNext() { return next; } public void setNext(Map<Character, Node> next) { this.next = next; } } private Node root; /** Initialize your data structure here. */ public WordDictionary() { root = new Node(); } /** Adds a word into the data structure. */ public void addWord(String word) { Node cur = root; for (int i = 0;i < word.length();i++) { char c = word.charAt(i); cur.getNext().putIfAbsent(c,new Node()); cur = cur.getNext().get(c); } if (!cur.getWord()) { cur.setWord(true); } } /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */ public boolean search(String word) { return match(root,word,0); } private boolean match(Node node,String word,int index) { if (index == word.length()) { return node.getWord(); } char c = word.charAt(index); if (c != '.') { if (node.getNext().get(c) == null) { return false; } return match(node.getNext().get(c),word,index + 1); }else { //遍历所有的字符节点，进行递归 for (char nextChar : node.getNext().keySet()) { if (match(node.getNext().get(nextChar),word,index + 1)) { return true; } } return false; } } }
提交给LeetCode
LeetCode算法题 https://leetcode-cn.com/problems/map-sum-pairs/
这是LeetCode的第677题——键值映射
同样也是使用递归来获取
class MapSum { private class Node { private int value; private Map<Character,Node> next; public Node(int value) { this.value = value; next = new TreeMap<>(); } public Node() { this(0); } public int getValue() { return value; } public void setValue(int value) { this.value = value; } public Map<Character, Node> getNext() { return next; } public void setNext(Map<Character, Node> next) { this.next = next; } } private Node root; /** Initialize your data structure here. */ public MapSum() { root = new Node(); } public void insert(String key, int val) { Node cur = root; for (int i = 0;i < key.length();i++) { char c = key.charAt(i); cur.getNext().putIfAbsent(c,new Node()); cur = cur.getNext().get(c); } cur.setValue(val); } public int sum(String prefix) { Node cur = root; for (int i = 0;i < prefix.length();i++) { char c = prefix.charAt(i); if (cur.getNext().get(c) == null) { return 0; } cur = cur.getNext().get(c); } return sum(cur); } private int sum(Node node) { int ret = node.getValue(); for (char c : node.getNext().keySet()) { ret += sum(node.getNext().get(c)); } return ret; } }
提交给LeetCode
- 并查集封装
并查集是解决连接问题的一种数据结构。我们认为在同一个集合中，两个元素是必然连接的，而不同的集合是不连接的。在并查集中，类似于线段树，同样不考虑并查集的增加、删除元素的操作。
接口
public interface UnionFind { int getSize(); /** * 查看元素p和元素q是否所属同一个集合 * @param p * @param q * @return */ boolean isConnected(int p,int q); /** * 合并元素p和元素q所属的集合 * @param p * @param q */ void unionElements(int p,int q); }
数组实现类
public class ArrayUnionFind implements UnionFind { //该数组的索引，我们称为元素的编号 //该数组的值，我们称之为元素所属不同集合的编号 //如果不同索引的值相同，则表示不同的元素属于同一个集合 private int[] id; public ArrayUnionFind(int size) { id = new int[size]; for (int i = 0;i < id.length;i++) { id[i] = i; } } /** * 查找元素p所对应的集合编号 * @param p * @return */ private int find(int p) { if (p < 0 || p >= id.length) { throw new IllegalArgumentException("p越界"); } return id[p]; } @Override public int getSize() { return id.length; } @Override public boolean isConnected(int p, int q) { return find(p) == find(q); } @Override public void unionElements(int p, int q) { int pID = find(p); int qID = find(q); if (pID == qID) { return; } for (int i = 0;i < id.length;i++) { if (id[i] == pID) { id[i] = qID; } } } }
对于ArrayUnionFind各操作的时间复杂度
isConnected(p,q) O(1)
unionElements(p,q) O(n)
由于ArrayUnionFind的unionElements()方法是O(n)级别的，所以在数据量比较大的情况下，它是无法支撑的。但因为它的isConnected()方法是O(1)级别的，所以我们称该实现类为Quick Find,而我们要改进的是Quick Union。
树实现类
我们将数组中的每个元素都当成一颗独立的树，初始化时，它们都是自己指向自己的指针。意思就是说每个元素的集合编号就是它们自己。
如果此时我们要改变元素4的集合编号变更为3的时候
此时我们又要将3的元素的集合编号变更为8
元素6的集合编号变更为5
元素9的集合编号变更与4相同，由于4的属于集合编号3的，而元素3是属于集合编号8的，所以要让9与4有相同的集合编号，所以9需要指向4的根节点的集合编号8.
元素2的集合编号变更为1
元素5的集合编号变更为0
元素7的集合编号变更与2相同，所以7的集合编号变更为2的根节点1
元素6的集合编号变更与2相同，只需要变更6的根结点0的集合编号为2的根节点的集合编号1
public class TreeUnionFind implements UnionFind { //该数组表示每个元素为一个向上指向自己指针的树 //当数组的值与索引相等时，表示自己指向自己 //当数组元素的值发生变动为其他元素的索引时，表示向上指针指向其他元素 private int[] parent; public TreeUnionFind(int size) { parent = new int[size]; for (int i = 0;i < parent.length;i++) { parent[i] = i; } } /** * 不断向上查找元素的根节点，直到找到根节点 * O(h)复杂度,h为树的高度 * @param p * @return */ private int find(int p) { if (p < 0 || p >= parent.length) { throw new IllegalArgumentException("p越界"); } 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; } }
对于TreeUnionFind各操作的时间复杂度
isConnected(p,q) O(h) h为树的高度
unionElements(p,q) O(h) h为树的高度
两种并查集的性能测试
public class TestUnionFindMain { private static double testUF(UnionFind uf,int m) { int size = uf.getSize(); Random random = new Random(); long startTime = System.nanoTime(); for (int i = 0;i < m;i++) { int a = random.nextInt(size); int b = random.nextInt(size); uf.unionElements(a,b); } for (int i = 0;i < m;i++) { int a = random.nextInt(size); int b = random.nextInt(size); uf.isConnected(a,b); } long endTime = System.nanoTime(); return (endTime - startTime) / 1000000000.0; } public static void main(String[] args) { int size = 1000000; int m = 10000; UnionFind arrayUnionFind = new ArrayUnionFind(size); System.out.println("arrayUnionFind : " + testUF(arrayUnionFind,m) + " s"); UnionFind treeUnionFind = new TreeUnionFind(size); System.out.println("treeUnionFind : " + testUF(treeUnionFind,m) + " s"); } }
测试结果
arrayUnionFind : 2.232692422 s
treeUnionFind : 0.002538113 s
但是当我们调整m的合并集合次数的时候
public class TestUnionFindMain { private static double testUF(UnionFind uf,int m) { int size = uf.getSize(); Random random = new Random(); long startTime = System.nanoTime(); for (int i = 0;i < m;i++) { int a = random.nextInt(size); int b = random.nextInt(size); uf.unionElements(a,b); } for (int i = 0;i < m;i++) { int a = random.nextInt(size); int b = random.nextInt(size); uf.isConnected(a,b); } long endTime = System.nanoTime(); return (endTime - startTime) / 1000000000.0; } public static void main(String[] args) { int size = 100000; int m = 100000; UnionFind arrayUnionFind = new ArrayUnionFind(size); System.out.println("arrayUnionFind : " + testUF(arrayUnionFind,m) + " s"); UnionFind treeUnionFind = new TreeUnionFind(size); System.out.println("treeUnionFind : " + testUF(treeUnionFind,m) + " s"); } }
测试结果
arrayUnionFind : 4.139503265 s
treeUnionFind : 8.657331935 s
出现这种情况，是因为在数组并查集，虽然它的合并集合unionElements()方法是O(n)级别的，但由于数组的内存地址是连续的，而树并查级的内存地址是非连续的，这里需要有一定的时间延迟，连续地址比非连续地址要快。而更重要的是增大了合并的次数m，有可能产生了类似于链表的树结构，也就是说树的高度接近于链表的长度，所以O(h)接近于O(n)。针对这个问题，我们需要改进合并集合的方式，让树向多分叉方向变化，而不是向链表方向变化。
改进的树并查集实现类,我们称之为基于树的节点元素个数的优化——size优化
public class SizeTreeUnionFind implements UnionFind { //该数组表示每个元素为一个向上指向自己指针的树 //当数组的值与索引相等时，表示自己指向自己 //当数组元素的值发生变动为其他元素的索引时，表示向上指针指向其他元素 private int[] parent; //sz[i]表示以i为根的集合中元素个数 private int[] sz; public SizeTreeUnionFind(int size) { parent = new int[size]; sz = new int[size]; for (int i = 0;i < parent.length;i++) { parent[i] = i; sz[i] = 1; } } /** * 不断向上查找元素的根节点，直到找到根节点 * O(h)复杂度,h为树的高度 * @param p * @return */ private int find(int p) { if (p < 0 || p >= parent.length) { throw new IllegalArgumentException("p越界"); } 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; } //根据两个元素所在树的元素个数不同判断合并方向 //将元素个数少的集合合并到元素个数多的集合上，降低树的高度 if (sz[pRoot] < sz[qRoot]) { parent[pRoot] = qRoot; sz[qRoot] += sz[pRoot]; }else { parent[qRoot] = pRoot; sz[pRoot] += sz[qRoot]; } } }
重新测试
public class TestUnionFindMain { private static double testUF(UnionFind uf,int m) { int size = uf.getSize(); Random random = new Random(); long startTime = System.nanoTime(); for (int i = 0;i < m;i++) { int a = random.nextInt(size); int b = random.nextInt(size); uf.unionElements(a,b); } for (int i = 0;i < m;i++) { int a = random.nextInt(size); int b = random.nextInt(size); uf.isConnected(a,b); } long endTime = System.nanoTime(); return (endTime - startTime) / 1000000000.0; } public static void main(String[] args) { int size = 100000; int m = 100000; UnionFind arrayUnionFind = new ArrayUnionFind(size); System.out.println("arrayUnionFind : " + testUF(arrayUnionFind,m) + " s"); UnionFind sizeTreeUnionFind = new SizeTreeUnionFind(size); System.out.println("sizeTreeUnionFind : " + testUF(sizeTreeUnionFind,m) + " s"); } }
测试结果
arrayUnionFind : 4.08657561 s
sizeTreeUnionFind : 0.019326149 s
基于降低树的高度的思想，我们又可以重新修改树并查集的代码，专门基于树的高度来进行优化
假设有现在的这种情况
此时我们要将4的元素的集合编号变更为与2相同，根据size的优化思路，由于2所在集合的元素要多于4所在集合的元素，所以我们此时合并集合后的结果如下，4的根节点8指向2的根节点7.
但是这样合并集合，无疑增大了树的高度，所以我们要让原树的高度低的合并到原树的高度高的中去，合并后结果如下
层级并查树实现类
public class RankTreeUnionFind implements UnionFind { //该数组表示每个元素为一个向上指向自己指针的树 //当数组的值与索引相等时，表示自己指向自己 //当数组元素的值发生变动为其他元素的索引时，表示向上指针指向其他元素 private int[] parent; //rank[i]表示以i为根的集合所表示的树的层数 private int[] rank; public RankTreeUnionFind(int size) { parent = new int[size]; rank = new int[size]; for (int i = 0;i < parent.length;i++) { parent[i] = i; rank[i] = 1; } } /** * 不断向上查找元素的根节点，直到找到根节点 * O(h)复杂度,h为树的高度 * @param p * @return */ private int find(int p) { if (p < 0 || p >= parent.length) { throw new IllegalArgumentException("p越界"); } 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; } //根据两个元素所在树的rank不同判断合并方向 //将rank低的集合合并到rank高的集合上 if (rank[pRoot] < rank[qRoot]) { parent[pRoot] = qRoot; }else if (rank[qRoot] < rank[pRoot]) { parent[qRoot] = pRoot; }else { parent[qRoot] = pRoot; rank[pRoot]++; } } }
现在我们调大合并集合的次数，重新测试，由于数组并查集合并集合方法为O(n)级别，所以不参与，无法完成运算
public class TestUnionFindMain { private static double testUF(UnionFind uf,int m) { int size = uf.getSize(); Random random = new Random(); long startTime = System.nanoTime(); for (int i = 0;i < m;i++) { int a = random.nextInt(size); int b = random.nextInt(size); uf.unionElements(a,b); } for (int i = 0;i < m;i++) { int a = random.nextInt(size); int b = random.nextInt(size); uf.isConnected(a,b); } long endTime = System.nanoTime(); return (endTime - startTime) / 1000000000.0; } public static void main(String[] args) { int size = 10000000; int m = 10000000; // UnionFind arrayUnionFind = new ArrayUnionFind(size); // System.out.println("arrayUnionFind : " + testUF(arrayUnionFind,m) + " s"); UnionFind sizeTreeUnionFind = new SizeTreeUnionFind(size); System.out.println("sizeTreeUnionFind : " + testUF(sizeTreeUnionFind,m) + " s"); UnionFind rankTreeUnionFind = new RankTreeUnionFind(size); System.out.println("rankTreeUnionFind : " + testUF(rankTreeUnionFind,m) + " s"); } }
测试结果
sizeTreeUnionFind : 5.12385286 s
rankTreeUnionFind : 4.823445856 s
路径压缩
现在我们都知道了，在并查集中，类似于下面这种树的集合其实是一个意思，它们都表示0、1、2、3、4这个5个元素属于同一个集合，集合编号为0，它们的根节点都是0。但由于这三种树的深度不同，所以查询根节点的效率是不同的。
而路径压缩要解决的问题就是将一颗比较高的树压缩成一颗比较矮的树。当我们在查找一个节点的根节点find()的过程中，顺便进行一下路径压缩。比如我们在最左边的图(类似链表)中查找4的根结点的时候，将4的父节点变更为其父节点的父节点，即parent[4] = parent[parent[4]]，这样图形就发生了如下的变化
由于2并非根节点，继续向上遍历，同时将2的父节点变更为2的父节点的父节点parent[2] = parent[parent[2]]，这样图形就发生了如下变化。
由于找到了根节点0，此时查找根节点find()结束。而整颗树的高度也变得更矮。所以SizeTreeUnionFind和RankTreeUnionFind也相应变更为
public class SizeTreeUnionFind implements UnionFind { //该数组表示每个元素为一个向上指向自己指针的树 //当数组的值与索引相等时，表示自己指向自己 //当数组元素的值发生变动为其他元素的索引时，表示向上指针指向其他元素 private int[] parent; //sz[i]表示以i为根的集合中元素个数 private int[] sz; public SizeTreeUnionFind(int size) { parent = new int[size]; sz = new int[size]; for (int i = 0;i < parent.length;i++) { parent[i] = i; sz[i] = 1; } } /** * 不断向上查找元素的根节点，直到找到根节点 * O(h)复杂度,h为树的高度 * @param p * @return */ private int find(int p) { if (p < 0 || p >= parent.length) { throw new IllegalArgumentException("p越界"); } while (p != parent[p]) { parent[p] = parent[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; } //根据两个元素所在树的元素个数不同判断合并方向 //将元素个数少的集合合并到元素个数多的集合上，降低树的高度 if (sz[pRoot] < sz[qRoot]) { parent[pRoot] = qRoot; sz[qRoot] += sz[pRoot]; }else { parent[qRoot] = pRoot; sz[pRoot] += sz[qRoot]; } } }
public class RankTreeUnionFind implements UnionFind { //该数组表示每个元素为一个向上指向自己指针的树 //当数组的值与索引相等时，表示自己指向自己 //当数组元素的值发生变动为其他元素的索引时，表示向上指针指向其他元素 private int[] parent; //rank[i]表示以i为根的集合所表示的树的层数 private int[] rank; public RankTreeUnionFind(int size) { parent = new int[size]; rank = new int[size]; for (int i = 0;i < parent.length;i++) { parent[i] = i; rank[i] = 1; } } /** * 不断向上查找元素的根节点，直到找到根节点 * O(h)复杂度,h为树的高度 * @param p * @return */ private int find(int p) { if (p < 0 || p >= parent.length) { throw new IllegalArgumentException("p越界"); } while (p != parent[p]) { parent[p] = parent[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; } //根据两个元素所在树的rank不同判断合并方向 //将rank低的集合合并到rank高的集合上 if (rank[pRoot] < rank[qRoot]) { parent[pRoot] = qRoot; }else if (rank[qRoot] < rank[pRoot]) { parent[qRoot] = pRoot; }else { parent[qRoot] = pRoot; rank[pRoot]++; } } }
重新测试TestUnionFindMain，结果如下
sizeTreeUnionFind : 3.952670823 s
rankTreeUnionFind : 3.968889342 s
当然我们也可以直接借助递归将一颗树的高度变成2
递归层级并查集实现类
public class RecursiveRankTreeUnionFind implements UnionFind { //该数组表示每个元素为一个向上指向自己指针的树 //当数组的值与索引相等时，表示自己指向自己 //当数组元素的值发生变动为其他元素的索引时，表示向上指针指向其他元素 private int[] parent; //rank[i]表示以i为根的集合所表示的树的层数 private int[] rank; public RecursiveRankTreeUnionFind(int size) { parent = new int[size]; rank = new int[size]; for (int i = 0;i < parent.length;i++) { parent[i] = i; rank[i] = 1; } } /** * 不断向上查找元素的根节点，直到找到根节点 * O(h)复杂度,h为树的高度 * @param p * @return */ private int find(int p) { if (p < 0 || p >= parent.length) { throw new IllegalArgumentException("p越界"); } if (p != parent[p]) { parent[p] = find(parent[p]); } return parent[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; } //根据两个元素所在树的rank不同判断合并方向 //将rank低的集合合并到rank高的集合上 if (rank[pRoot] < rank[qRoot]) { parent[pRoot] = qRoot; }else if (rank[qRoot] < rank[pRoot]) { parent[qRoot] = pRoot; }else { parent[qRoot] = pRoot; rank[pRoot]++; } } }
测试
public class TestUnionFindMain { private static double testUF(UnionFind uf,int m) { int size = uf.getSize(); Random random = new Random(); long startTime = System.nanoTime(); for (int i = 0;i < m;i++) { int a = random.nextInt(size); int b = random.nextInt(size); uf.unionElements(a,b); } for (int i = 0;i < m;i++) { int a = random.nextInt(size); int b = random.nextInt(size); uf.isConnected(a,b); } long endTime = System.nanoTime(); return (endTime - startTime) / 1000000000.0; } public static void main(String[] args) { int size = 10000000; int m = 10000000; // UnionFind arrayUnionFind = new ArrayUnionFind(size); // System.out.println("arrayUnionFind : " + testUF(arrayUnionFind,m) + " s"); UnionFind sizeTreeUnionFind = new SizeTreeUnionFind(size); System.out.println("sizeTreeUnionFind : " + testUF(sizeTreeUnionFind,m) + " s"); UnionFind rankTreeUnionFind = new RankTreeUnionFind(size); System.out.println("rankTreeUnionFind : " + testUF(rankTreeUnionFind,m) + " s"); UnionFind recursiveRankTreeUnionFind = new RecursiveRankTreeUnionFind(size); System.out.println("recursiveRankTreeUnionFind : " + testUF(recursiveRankTreeUnionFind,m) + " s"); } }
测试结果
sizeTreeUnionFind : 3.891047143 s
rankTreeUnionFind : 3.949480955 s
recursiveRankTreeUnionFind : 4.489701369 s
由结果可知，递归层级并查集的速度要慢过非递归，原因在于非递归的方式也可以最终将一棵树的高度降低为2，只不过不是一次调用，而是多次调用。而递归的方式本身会增加复杂度，增大开销。如下图所示，如果我们再次调用find(4)的时候，4的父节点就指向了父节点2的父节点0.
如果再调用一次find(3)，则将最终演变成一颗高度为2的树
- AVL树封装
AVL树是一种保持平衡的二分搜索树，使得该二分搜索树不会退化为一个链表。
平衡二叉树——对于任意一个节点，左子树和右子树的高度差不能超过1。平衡二叉树的高度和节点数量之间的关系也是O(log n)的。
由此可以定义任意一个节点的高度为左右子树较高的那颗子树的高度+1，加的这个1就是节点本身。
以上图数字5为例，他的左右子树的高度，分别为2和1，则5节点的高度为左右子树中高的子树的高度加1，则其高度为3.
我们定义一个节点的平衡因子为该节点左右子树的高度差，则很明显，当平衡因子为大于0的时候，说明左子树高于右子树；当平衡因子小于0的时候，说明右子树高于左子树。而当平衡因子大于1或者小于-1的时候，我们知道，该节点失去了平衡性。
又根据平衡二叉树的定义，我们知道上面这颗二分搜索树并不是一个平衡二分搜索树，因为到8这个节点的时候，它的平衡因子为2，超过了1.所以我们在AVL树的实现的时候，需要保持8这个节点的平衡性。
要维护一个节点的平衡性需要考虑4种情况
1、一直向一颗树的左侧添加元素，我们可以用LL来标记
此时可以肯定的是该节点的平衡因子是大于1的(左子树高过右子树2，一般也就高过2，不会超过2)，且该节点的左节点的平衡因子大于等于0才可能是一直向左侧添加元素.
右旋转
假设我们现在在树的最左侧添加了一个节点，并打破了平衡性，y的平衡因子为2.根据二分搜索树的性质(节点左子树的元素一律小于该节点的元素，节点右子树的元素，一律大于该节点元素)，此时图中各个元素的大小排序为
T1 < z < T2 < x < T3 < y < T4
当我们转换图形的位置如下时
各个元素的大小排序为
T1 < z < T2 < x < T3 < y < T4，可见元素的顺序并没有发生改变，说明这样的一颗二分搜索树跟之前的是等价的。
而所要做出的调整就为将x的右节点变成y,x的原右节点T3变为y的左节点，我们将此过程称为右旋转。旋转完之后，我们需要维护x跟y的高度。
2、一直向一棵树的右侧一直添加元素，我们可以用RR来标记
此时可以肯定的是该节点的平衡因子是小于-1的(右子树高过左子树2)，且该节点的右节点的平衡因子小于等于0才可能是一直向右侧添加元素.
左旋转
假设我们现在在树的最右侧添加了一个节点，并打破了平衡性，y的平衡因子为-2.根据二分搜索树的性质(节点左子树的元素一律小于该节点的元素，节点右子树的元素，一律大于该节点元素)，此时图中各个元素的大小排序为
T4 < y < T3 < x < T1 < z < T2
当我们转换图形的位置如下时
各个元素的大小排序为
T4 < y < T3 < x < T1 < z < T2,可见元素的顺序并没有发生改变，说明这样的一颗二分搜索树跟之前的是等价的。
而所要做出的调整就为将x的左节点变成y,x的原左节点T3变为y的右节点，我们将此过程称为左旋转。旋转完之后，我们需要维护x跟y的高度。
3、向节点的左节点添加右节点，我们可以用LR标识
此时可以肯定的是该节点的平衡因子是大于1的(左子树高过右子树2)，且该节点的左节点的平衡因子小于0才可能是这种情况。
现在我们知道无论对一颗二分搜索树做左旋转还是右旋转都不会改变一个二分搜索树的排序的性质，那么我们对x做一次左旋转，将x变成z的左节点，T2变成x的右节点。当然z要变成y的左节点。
那么此时，就变成了LL的情况，按照LL来处理就好了。
4、向节点的右节点添加左节点，我们可以用RL标识
此时可以肯定的是该节点的平衡因子是小于-1的(右子树高过左子树2)，且该节点的右节点的平衡因子大于0才可能是这种情况。
此时我们只需要将x做一次右旋转，将x变成z的右节点，将T3变成x的左节点，当然z变成y的右节点。
那么此时，就变成了RR的情况，按照RR来处理就好了。
实现类
public class AVLTree<T extends Comparable<T>> implements Tree<T> { @Data @AllArgsConstructor private class Node{ private T element; private Node left; private Node right; //节点的高度，在节点的左右子树增加、删除节点时需要维护该节点的高度 private int height; public Node(T element) { this(element,null,null,1); } } private Node root; private int size; public AVLTree() { root = null; size = 0; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } private int getHeight(Node node) { if (node == null) { return 0; } return node.getHeight(); } /** * 获得节点node的平衡因子(左右子树的高度差) * @param node * @return */ private int getBalanceFactor(Node node) { if (node == null) { return 0; } return getHeight(node.getLeft()) - getHeight(node.getRight()); } /** * 判断该二叉树是否是一颗二分搜索树 * @return */ public boolean isBST() { Array<T> elements = new DefaultArray<>(); inOrder(root,elements); for (int i = 1;i < elements.getSize();i++) { if (elements.get(i - 1).compareTo(elements.get(i)) > 0) { return false; } } return true; } /** * 判断该二叉树是否是一颗平衡二叉树 * @return */ public boolean isBalanced() { return isBalanced(root); } private boolean isBalanced(Node node) { if (node == null) { return true; } int balanceFactor = getBalanceFactor(node); if (Math.abs(balanceFactor) > 1) { return false; } return isBalanced(node.getLeft()) && isBalanced(node.getRight()); } /** * 对节点node进行右旋转操作，返回旋转后新的根节点(原node的左节点) * @param node * @return */ private Node rightRotate(Node node) { Node ret = node.getLeft(); Node rightRet = ret.getRight(); //向右旋转的过程 ret.setRight(node); node.setLeft(rightRet); //更新height node.setHeight(Math.max(getHeight(node.getLeft()),getHeight(node.getRight())) + 1); ret.setHeight(Math.max(getHeight(ret.getLeft()),getHeight(ret.getRight())) + 1); return ret; } /** * 对节点node进行左旋转操作，返回旋转后新的根节点(原node的右节点) * @param node * @return */ private Node leftRotate(Node node) { Node ret = node.getRight(); Node leftRet = ret.getLeft(); //向左旋转的过程 ret.setLeft(node); node.setRight(leftRet); //更新height node.setHeight(Math.max(getHeight(node.getLeft()),getHeight(node.getRight())) + 1); ret.setHeight(Math.max(getHeight(ret.getLeft()),getHeight(ret.getRight())) + 1); return ret; } @Override public void add(T value) { root = add(root,value); } private Node add(Node node,T value) { //递归终止条件 if (node == null) { size++; return new Node(value); } //递归 if (value.compareTo(node.getElement()) < 0) { node.setLeft(add(node.getLeft(),value)); }else if (value.compareTo(node.getElement()) > 0) { node.setRight(add(node.getRight(),value)); } return service(node); } @Override public boolean contains(T value) { return contains(root,value); } private boolean contains(Node node,T value) { if (node == null) { return false; } if (value.compareTo(node.getElement()) == 0) { return true; }else if (value.compareTo(node.getElement()) < 0) { return contains(node.getLeft(),value); }else { return contains(node.getRight(),value); } } @Override public void preOrder() { preOrder(root); } private void preOrder(Node node) { if (node == null) { return; } System.out.println(node.getElement()); preOrder(node.getLeft()); preOrder(node.getRight()); } /** * 非递归前序遍历 */ public void preOrderNR() { Stack<Node> stack = new ArrayStack<>(); stack.push(root); while (!stack.isEmpty()) { Node cur = stack.pop(); System.out.println(cur.getElement()); if (cur.getRight() != null) { stack.push(cur.getRight()); } if (cur.getLeft() != null) { stack.push(cur.getLeft()); } } } @Override public void inOrder() { inOrder(root); } private void inOrder(Node node) { if (node == null) { return; } inOrder(node.getLeft()); System.out.println(node.getElement()); inOrder(node.getRight()); } private void inOrder(Node node,Array<T> elements) { if (node == null) { return; } inOrder(node.getLeft(),elements); elements.addLast(node.getElement()); inOrder(node.getRight(),elements); } @Override public void postOrder() { postOrder(root); } private void postOrder(Node node) { if (node == null) { return; } postOrder(node.getLeft()); postOrder(node.getRight()); System.out.println(node.getElement()); } @Override public void levelOrder() { Queue<Node> queue = new LoopQueue<>(); queue.enqueue(root); while (!queue.isEmpty()) { Node cur = queue.dequeue(); System.out.println(cur.getElement()); if (cur.getLeft() != null) { queue.enqueue(cur.getLeft()); } if (cur.getRight() != null) { queue.enqueue(cur.getRight()); } } } @Override public T minimum() { if (size == 0) { throw new IllegalArgumentException("二分搜索树为空"); } return minimum(root).getElement(); } private Node minimum(Node node) { if (node.getLeft() == null) { return node; } return minimum(node.getLeft()); } @Override public T maximum() { if (size == 0) { throw new IllegalArgumentException("二分搜索树为空"); } return maximum(root).getElement(); } private Node maximum(Node node) { if (node.getRight() == null) { return node; } return maximum(node.getRight()); } @Override public T removeMin() { T ret = minimum(); root = removeMin(root); return ret; } private Node removeMin(Node node) { //递归的终止条件，当节点的左子树为空时，递归达到最大深度 if (node.getLeft() == null) { //保存最终节点的右子树 Node rightNode = node.getRight(); //将最终节点分离 node.setRight(null); size--; //将保存的右子树拼接回最终节点的父节点 return rightNode; } //从根节点开始不断向左子树递归，并逐层返回删除后的子节点重新 //设为上层节点的左节点 node.setLeft(removeMin(node.getLeft())); return service(node); } @Override public T removeMax() { T ret = maximum(); root = removeMax(root); return ret; } private Node removeMax(Node node) { if (node.getRight() == null) { Node leftNode = node.getLeft(); node.setLeft(null); size--; return leftNode; } node.setRight(removeMax(node.getRight())); return service(node); } @Override public void remove(T value) { root = remove(root,value); } private Node remove(Node node,T value) { if (node == null) { return null; } Node retNode; if (value.compareTo(node.getElement()) < 0) { node.setLeft(remove(node.getLeft(),value)); retNode = node; }else if (value.compareTo(node.getElement()) > 0) { node.setRight(remove(node.getRight(),value)); retNode = node; }else { //待删除节点左子树为空的情况 if (node.getLeft() == null) { Node rightNode = node.getRight(); node.setRight(null); size--; retNode = rightNode; } //待删除节点右子树为空的情况 else if (node.getRight() == null) { Node leftNode = node.getLeft(); node.setLeft(null); size--; retNode = leftNode; }else { //待删除节点左右子树均不为空的情况 //找到比待删除节点大的最小节点，即待删除节点右子树的最小节点 //用这个节点顶替待删除节点的位置 Node successor = minimum(node.getRight()); successor.setRight(removeMin(node.getRight())); successor.setLeft(node.getLeft()); node.setLeft(null); node.setRight(null); retNode = successor; //找到比待删除节点小的最大节点，即待删除节点左子树的最大节点 //用这个节点顶替待删除节点的位置,此二种方法取其一即可 // Node predecessor = maximum(node.getLeft()); // predecessor.setLeft(removeMax(node.getLeft())); // predecessor.setRight(node.getRight()); // node.setLeft(null); // node.setRight(null); // return predecessor; } } if (retNode == null) { return null; } return service(retNode); } /** * 维护节点平衡 * @param node * @return */ private Node service(Node node) { //更新height node.setHeight(1 + Math.max(getHeight(node.getLeft()),getHeight(node.getRight()))); //计算平衡因子 int balanceFactor = getBalanceFactor(node); //平衡维护 //LL if (balanceFactor > 1 && getBalanceFactor(node.getLeft()) >= 0) { return rightRotate(node); } //RR if (balanceFactor < -1 && getBalanceFactor(node.getRight()) <= 0) { return leftRotate(node); } //LR if (balanceFactor > 1 && getBalanceFactor(node.getLeft()) < 0) { node.setLeft(leftRotate(node.getLeft())); return rightRotate(node); } //RL if (balanceFactor < -1 && getBalanceFactor(node.getRight()) > 0) { node.setRight(rightRotate(node.getRight())); return leftRotate(node); } return node; } @Override public T floor(T value) { Node node = floor(root,value); if (node != null) { return node.getElement(); } return null; } private Node floor(Node node,T value) { if (node == null) { return null; } if (value.compareTo(node.getElement()) <= 0) { return floor(node.getLeft(),value); }else { if (node.getRight() == null) { return node; }else if (node.getRight().getLeft() == null && value.compareTo(node.getRight().getElement()) <= 0) { return node; }else if (node.getRight().getRight() == null && value.compareTo(node.getRight().getElement()) > 0) { return node.getRight(); } return floor(node.getRight(),value); } } @Override public T ceil(T value) { Node node = ceil(root,value); if (node != null) { return node.getElement(); } return null; } private Node ceil(Node node,T value) { if (node == null) { return null; } if (value.compareTo(node.getElement()) >= 0) { return ceil(node.getRight(),value); }else { if (node.getLeft() == null) { return node; }else if (value.compareTo(maximum(node.getLeft()).getElement()) >= 0) { return node; }else if (node.getLeft().getRight() == null && value.compareTo(node.getLeft().getElement()) >= 0) { return node; }else if (node.getLeft().getLeft() == null && value.compareTo(node.getLeft().getElement()) < 0) { return node.getLeft(); } return ceil(node.getLeft(),value); } } @Override public String toString() { StringBuilder builder = new StringBuilder(); generateBSTString(root,0,builder); return builder.toString(); } private void generateBSTString(Node node,int depth,StringBuilder builder) { if (node == null) { builder.append(generateDepthString(depth) + "null\n"); return; } builder.append(generateDepthString(depth) + node.getElement() + "\n"); generateBSTString(node.getLeft(),depth + 1,builder); generateBSTString(node.getRight(),depth + 1,builder); } private String generateDepthString(int depth) { StringBuilder builder = new StringBuilder(); for (int i = 0;i < depth;i++) { builder.append("--"); } return builder.toString(); } }
- AVL树映射封装
实现类
public class AVLTreeMap<K extends Comparable<K>,V> implements Map<K,V> { @Data @AllArgsConstructor private class Node{ private K key; private V value; private Node left; private Node right; private int height; public Node(K key) { this(key,null,null,null,1); } public Node(K key,V value) { this(key,value,null,null,1); } } private Node root; private int size; public AVLTreeMap() { root = null; size = 0; } private int getHeight(Node node) { if (node == null) { return 0; } return node.getHeight(); } private int getBalanceFactor(Node node) { if (node == null) { return 0; } return getHeight(node.getLeft()) - getHeight(node.getRight()); } private Node rightRotate(Node node) { Node ret = node.getLeft(); Node retRight = ret.getRight(); ret.setRight(node); node.setLeft(retRight); node.setHeight(Math.max(getHeight(node.getLeft()),getHeight(node.getRight())) + 1); ret.setHeight(Math.max(getHeight(ret.getLeft()),getHeight(ret.getRight())) + 1); return ret; } private Node leftRotate(Node node) { Node ret = node.getRight(); Node retLeft = ret.getLeft(); ret.setLeft(node); node.setRight(retLeft); node.setHeight(Math.max(getHeight(node.getLeft()),getHeight(node.getRight())) + 1); ret.setHeight(Math.max(getHeight(ret.getLeft()),getHeight(ret.getRight())) + 1); return ret; } @Override public void add(K key, V value) { root = add(root,key,value); } private Node add(Node node, K key, V value) { //递归终止条件 if (node == null) { size++; return new Node(key,value); } //递归 if (key.compareTo(node.getKey()) < 0) { node.setLeft(add(node.getLeft(),key,value)); }else if (key.compareTo(node.getKey()) > 0) { node.setRight(add(node.getRight(),key,value)); }else { node.setValue(value); } return service(node); } @Override public V remove(K key) { Node node = getNode(root,key); if (node != null) { root = remove(root,key); return node.getValue(); } return null; } private Node remove(Node node, K key) { if (node == null) { return null; } Node retNode; if (key.compareTo(node.getKey()) < 0) { node.setLeft(remove(node.getLeft(),key)); retNode = node; }else if (key.compareTo(node.getKey()) > 0) { node.setRight(remove(node.getRight(),key)); retNode = node; }else { //待删除节点左子树为空的情况 if (node.getLeft() == null) { Node rightNode = node.getRight(); node.setRight(null); size--; retNode = rightNode; } //待删除节点右子树为空的情况 else if (node.getRight() == null) { Node leftNode = node.getLeft(); node.setLeft(null); size--; retNode = leftNode; }else { //待删除节点左右子树均不为空的情况 //找到比待删除节点大的最小节点，即待删除节点右子树的最小节点 //用这个节点顶替待删除节点的位置 Node successor = minimum(node.getRight()); successor.setRight(removeMin(node.getRight())); successor.setLeft(node.getLeft()); node.setLeft(null); node.setRight(null); retNode = successor; } } if (retNode == null) { return null; } return service(retNode); } private Node service(Node node) { node.setHeight(1 + Math.max(getHeight(node.getLeft()),getHeight(node.getRight()))); int balanceFactor = getBalanceFactor(node); if (balanceFactor > 1 && getBalanceFactor(node.getLeft()) >= 0) { return rightRotate(node); } if (balanceFactor < -1 && getBalanceFactor(node.getRight()) <= 0) { return leftRotate(node); } if (balanceFactor > 1 && getBalanceFactor(node.getLeft()) < 0) { node.setLeft(leftRotate(node.getLeft())); return rightRotate(node); } if (balanceFactor < -1 && getBalanceFactor(node.getRight()) > 0) { node.setRight(rightRotate(node.getRight())); return leftRotate(node); } return node; } private Node minimum(Node node) { if (node.getLeft() == null) { return node; } return minimum(node.getLeft()); } private Node removeMin(Node node) { if (node.getLeft() == null) { Node rightNode = node.getRight(); node.setRight(null); size--; return rightNode; } node.setLeft(removeMin(node.getLeft())); return service(node); } @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.getValue(); } @Override public void set(K key, V value) { Node node = getNode(root,key); if (node == null) { throw new IllegalArgumentException(key + "不存在"); } node.setValue(value); } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } private Node getNode(Node node, K key) { if (node == null) { return null; } if (key.compareTo(node.getKey()) == 0) { return node; }else if (key.compareTo(node.getKey()) < 0) { return getNode(node.getLeft(),key); }else { return getNode(node.getRight(),key); } } }
调用
public class MapMain { public static void main(String[] args) { System.out.println("傲慢与偏见"); Array<String> words = new DefaultArray<>(); FileOperation.readFile("/Users/admin/Downloads/pride-and-prejudice.txt",words); System.out.println("共有单词: " + words.getSize()); Map<String,Integer> map = new AVLTreeMap<>(); Stream.of(words.getData()).filter(word -> word != null) .forEach(word -> { if (map.contains(word)) { map.set(word,map.get(word) + 1); }else { map.add(word,1); } }); System.out.println("共有不同的单词: " + map.getSize()); System.out.println("pride出现的次数: " + map.get("pride")); System.out.println("prejudice出现的次数: " + map.get("prejudice")); } }
运行结果
傲慢与偏见
共有单词: 125901
共有不同的单词: 6530
pride出现的次数: 53
prejudice出现的次数: 11
三种映射的性能测试
public class TestMapMain { private static double testMap(Map<String,Integer> map,String filename) { long startTime = System.nanoTime(); System.out.println(filename); Array<String> words = new DefaultArray<>(); FileOperation.readFile(filename,words); System.out.println("共有单词: " + words.getSize()); Stream.of(words.getData()).filter(word -> word != null) .forEach(word -> { if (map.contains(word)) { map.set(word,map.get(word) + 1); }else { map.add(word,1); } }); System.out.println("共有不同的单词: " + map.getSize()); System.out.println("pride出现的次数: " + map.get("pride")); System.out.println("prejudice出现的次数: " + map.get("prejudice")); long endTime = System.nanoTime(); return (endTime - startTime) / 1000000000.0; } public static void main(String[] args) { String filename = "/Users/admin/Downloads/pride-and-prejudice.txt"; Map<String,Integer> bstMap = new BSTMap<>(); double time1 = testMap(bstMap,filename); System.out.println("BST Map: " + time1 + " s"); Map<String,Integer> linkedListMap = new LinkedListMap<>(); double time2 = testMap(linkedListMap,filename); System.out.println("LinkedList Map: " + time2 + " s"); Map<String,Integer> avlTreeMap = new AVLTreeMap<>(); double time3 = testMap(avlTreeMap,filename); System.out.println("AVLTree Map: " + time3 + " s"); } }
测试结果
/Users/admin/Downloads/pride-and-prejudice.txt
共有单词: 125901
共有不同的单词: 6530
pride出现的次数: 53
prejudice出现的次数: 11
BST Map: 0.166421303 s
/Users/admin/Downloads/pride-and-prejudice.txt
共有单词: 125901
共有不同的单词: 6530
pride出现的次数: 53
prejudice出现的次数: 11
LinkedList Map: 9.416305469 s
/Users/admin/Downloads/pride-and-prejudice.txt
共有单词: 125901
共有不同的单词: 6530
pride出现的次数: 53
prejudice出现的次数: 11
AVLTree Map: 0.065798621 s
- AVL树集合封装
实现类
public class AVLTreeSet<T extends Comparable<T>> implements Set<T> { private Tree<T> avlTree; public AVLTreeSet() { avlTree = new AVLTree<>(); } @Override public void add(T value) { avlTree.add(value); } @Override public void remove(T value) { avlTree.remove(value); } @Override public boolean contains(T value) { return avlTree.contains(value); } @Override public int getSize() { return avlTree.getSize(); } @Override public boolean isEmpty() { return avlTree.isEmpty(); } }
三种集合的性能测试
public class TestSetMain { private static double testSet(Set<String> set,String filename) { long startTime = System.nanoTime(); System.out.println(filename); Array<String> words = new DefaultArray<>(); if (FileOperation.readFile(filename,words)) { System.out.println("共有单词: " + words.getSize()); Stream.of(words.getData()).filter(data -> data != null) .forEach(set::add); System.out.println("共有不同单词: " + set.getSize()); } long endTime = System.nanoTime(); return (endTime - startTime) / 1000000000.0; } public static void main(String[] args) { String filename = "/Users/admin/Downloads/pride-and-prejudice.txt"; Set<String> bstSet = new BSTSet<>(); double time1 = testSet(bstSet,filename); System.out.println("BST Set: " + time1 + " s"); System.out.println(); Set<String> linkedListSet = new LinkedListSet<>(); double time2 = testSet(linkedListSet,filename); System.out.println("LinkedList Set: " + time2 + " s"); System.out.println(); Set<String> avlTreeSet = new AVLTreeSet<>(); double time3 = testSet(avlTreeSet,filename); System.out.println("AVLTree Set: " + time3 + " s"); } }
测试结果
/Users/admin/Downloads/pride-and-prejudice.txt
共有单词: 125901
共有不同单词: 6530
BST Set: 0.153552536 s
/Users/admin/Downloads/pride-and-prejudice.txt
共有单词: 125901
共有不同单词: 6530
LinkedList Set: 2.292920811 s
/Users/admin/Downloads/pride-and-prejudice.txt
共有单词: 125901
共有不同单词: 6530
AVLTree Set: 0.057089254 s
- 红黑树封装
红黑树是一种等价于2-3树的数据结构，它满足以下几个特性
- 每个节点或者是红色，或者是黑色的
- 根节点是黑色的
- 每一个叶子结点(最后的空节点)是黑色的
- 如果一个节点是红色的，那么他的孩子节点都是黑色的
- 从任意一个节点到叶子节点，经过的黑色节点是一样的
2-3树
满足二分搜索树的基本性质，节点可以存放一个元素或者两个元素。是一颗绝对平衡的树(各个子树的高度差为0)
2-3树维护绝对平衡，2-3树在添加新节点的时候永远不会添加到一个空节点，我们依次添加42-37-12-18-6-11-5的过程依次如下
42为起始二节点的根节点，添加37会放入到42的同节点的左边产生节点的融合，产生一个三节点。
添加12会暂时融合为一个四节点，
然后转化为一个带左右子节点的二叉树。其中每一个节点都是二节点。
添加18，由于根节点37的左节点不为空，所以18直接添加到左节点，变成一个三节点
添加6的时候，会暂时把6添加到根节点的左节点，变成一个四节点
然后拆解成3个二节点的二叉树。
由于12的父节点是一个二节点，所以可以将12于父节点37融合为一个三节点。
添加11的时候，只需要将11与6融合成一个三节点。
增加5的时候，先暂时跟6、11的三节点融合成一个四节点
再拆分成3个二节点
再将6暂时融合到它的父节点，变成一个四节点。
再将6、12、37的四节点拆成三个二节点。
由次保持了2-3树的绝对平衡。
按照各种情况，2-3树新增节点有如下的各种
1、插入二节点
2、插入三节点(根节点)
3、插入三节点（叶节点，且父节点为二节点）
从左子节点进入
从中子节点进入
4、插入三节点(叶节点，且父节点为三节点)
从左子节点进入
从中子节点进入
从右子节点进入
2-3树删除最小元素
删除最小元素，无论如何如果最左的叶节点是一个三节点，这是非常容易的，只需要删除三节点的左元素。
所以我们认定删除必须发生在三节点或者临时的四节点中(因为四节点删除最小元素依然是一个三节点，依然符合2-3树的性质)。
但如果最左的叶节点是一个二节点，此时我们应该先把二节点给变换成一个三节点或者一个临时四节点再进行删除。
待删除节点的父节点为二节点，且父节点的中子节点是一个二节点
待删除节点的父节点为二节点，父节点的中子节点是一个三节点
待删除节点的父节点为三节点，父节点的中子节点是一个二节点
待删除节点的父节点为三节点，父节点的中子节点是一个三节点
2-3接口
public interface BTree<T> { void add(T t); boolean contains(T t); }
2-3树实现类
public class TwoThreeTree<T extends Comparable<T>> implements BTree<T> { private static final int N = 3; private class Node { @Getter @Setter private Node parent; //子节点，3个，左、中、右三个子节点 private Node[] childNodes; //节点保存的元素，1-2个 private T[] elements; //节点保存的元素个数 @Getter private int size; @SuppressWarnings("unchecked") public Node(Class<T> type) { parent = null; childNodes = (Node[]) Array.newInstance(Node.class,N); elements = (T[]) Array.newInstance(type,N - 1); size = 0; } /** * 判断是否是叶子节点 * @return */ private boolean isLeaf() { return childNodes[0] == null; } /** * 判断节点存储数据是否满了 * @return */ private boolean isFull() { return size == N - 1; } /** * 将子节点连接 * @param index 连接的位置(左子树、中子树、还是右子树) * @param child */ private void connectChild(int index,Node child) { childNodes[index] = child; if (child != null) { child.setParent(this); } } /** * 解除该节点和某个节点之间的连接 * @param index 解除连接的位置 * @return */ private Node disconnectChild(int index) { Node ret = childNodes[index]; childNodes[index] = null; return ret; } /** * 获取节点左或右的值 * @param index 0为左，1为右 * @return */ private T getData(int index) { return elements[index]; } /** * 获取某个位置的子树 * @param index 0为左子树，1为中子树，2为右子树 * @return */ private Node getChild(int index) { return childNodes[index]; } /** * 寻找value在节点的位置 * @param value * @return 未找到返回-1 */ private int findItem(T value) { for (int i = 0;i < size;i++) { if (elements[i] == null) { break; }else if (elements[i].compareTo(value) == 0) { return i; } } return -1; } /** * 向节点添加元素 * @param value * @return 返回添加的位置，0或1 */ private int add(T value) { if (size == 2) { throw new IllegalArgumentException("节点已满"); } size++; for (int i = N - 2;i >= 0;i--) { if (elements[i] == null) { continue; }else { if (value.compareTo(elements[i]) < 0) { elements[i + 1] = elements[i]; }else { elements[i + 1] = value; return i + 1; } } } elements[0] = value; return 0; } /** * 移除最后一个元素(先右后左) * @return */ private T remove() { T ret = elements[size - 1]; elements[size - 1] = null; size--; return ret; } @Override public String toString() { return "Node{" + "elements=" + Arrays.toString(elements) + '}'; } } private Node root; private Class<T> type; public TwoThreeTree(Class<T> type) { this.type = type; root = new Node(type); } @Override public void add(T value) { add(root,value); } private void add(Node node,T value) { //寻找叶节点 while (true) { if (node.isLeaf()) { break; }else { node = getNextChild(node,value); } } //如果是一个三节点 if (node.isFull()) { split(node,value); }else { //如果是一个二节点则直接在节点中添加元素 node.add(value); } } /** * 根据value的值获取节点的子节点(可能为左、中、右子节点) * @param node * @param value * @return */ private Node getNextChild(Node node,T value) { for (int i = 0;i < node.getSize();i++) { if (node.getData(i).compareTo(value) > 0) { return node.getChild(i); } } return node.getChild(node.getSize()); } /** * 裂变函数，裂变节点，该节点为一个三节点 * @param node 被裂变的节点 * @param value 要保存的元素 */ private void split(Node node,T value) { Node parent = node.getParent(); Node newNode = new Node(this.type); //裂变后的中间节点 Node midNode = new Node(this.type); T mid; //如果元素比节点左值要小 if (value.compareTo(node.getData(0)) < 0) { //创建一个节点右值的新节点 newNode.add(node.remove()); //取出节点的左值做为中间元素，此时节点没有任何值 mid = node.remove(); //节点放入新元素value node.add(value); //如果元素比节点左值大，比右值小 }else if (value.compareTo(node.getData(1)) < 0) { //创建一个节点右值的新节点，此时节点还剩下左值 newNode.add(node.remove()); //将新增元素做为中间元素 mid = value; //如果元素比节点右值大 }else { //取出节点右值做为中间元素，此时节点还剩下左值 mid = node.remove(); //创建一个新增元素的新节点 newNode.add(value); } if (node == root) { root = midNode; } //中间节点添加中间元素 midNode.add(mid); //中间节点连接左子节点 midNode.connectChild(0,node); //中间节点连接中子节点(二节点的中子节点可以理解为二叉树的右节点) midNode.connectChild(1,newNode); connectNode(parent,midNode); } /** * 连接node和parent * @param parent * @param node node为二节点 */ private void connectNode(Node parent,Node node) { //获取中间节点的唯一元素 T data = node.getData(0); if (node == root) { return; } //如果父节点是一个三节点 if (parent.isFull()) { //获取父节点的父节点 Node gParent = parent.getParent(); Node newNode = new Node(this.type); Node temp1,temp2; T itemData; //如果中间节点元素比父节点的左值小 //这种情况应该是从父节点的左子节点进来的中间节点 if (data.compareTo(parent.getData(0)) < 0) { //父节点分裂中子节点 temp1 = parent.disconnectChild(1); //父节点分裂右子节点 temp2 = parent.disconnectChild(2); //将分裂出的中子节点和右子节点连接到父节点的右值的新节点上 //成为该新节点的左子节点和中子节点(二节点的中子节点可以理解为二叉树的右节点) newNode.connectChild(0,temp1); newNode.connectChild(1,temp2); newNode.add(parent.remove()); itemData = parent.remove(); parent.add(itemData); //父节点连接中间节点为左子节点 parent.connectChild(0,node); //父节点连接新节点为中子节点，此时父节点是一个二节点 parent.connectChild(1,newNode); //如果中间节点元素比父节点的左值大，比右值小 //这种情况应该是从父节点的中子节点进来的中间节点 }else if (data.compareTo(parent.getData(1)) < 0) { //父节点分裂左子节点 temp1 = parent.disconnectChild(0); //父节点分裂右子节点 temp2 = parent.disconnectChild(2); Node tempNode = new Node(this.type); //创建一个父节点右值的新节点 newNode.add(parent.remove()); //将中间节点分裂出的中子节点连接到新节点的左子节点 newNode.connectChild(0,node.disconnectChild(1)); //将父节点分裂出的右子节点做为新节点的中子节点 newNode.connectChild(1,temp2); //创建一个父节点左值的临时节点(此时父节点中无值) tempNode.add(parent.remove()); //将父节点分裂出的左子节点做为临时节点的左子节点 tempNode.connectChild(0,temp1); //将中间节点分裂出的左子节点做为临时节点的中子节点 tempNode.connectChild(1,node.disconnectChild(0)); //将中间节点的唯一值移除并添加到父节点 parent.add(node.remove()); //将临时节点做为父节点的左子节点 parent.connectChild(0,tempNode); //将新节点做为父节点的中子节点 parent.connectChild(1,newNode); //如果中间节点元素比父节点的右值大 //这种情况应该是从父节点的右子节点进来的中间节点 }else { //分裂父节点的左子节点 temp1 = parent.disconnectChild(0); //分裂父节点的中子节点 temp2 = parent.disconnectChild(1); //取出父节点的右值 itemData = parent.remove(); //创建一个父节点左值的新节点(此时父节点无值) newNode.add(parent.remove()); //将分裂的左子节点做为新节点的左子节点 newNode.connectChild(0,temp1); //将分裂的中子节点做为新节点的中子节点 newNode.connectChild(1,temp2); //去除父节点的右子节点(此时右子节点会被垃圾回收) parent.disconnectChild(2); //将父节点的原右值添加回父节点做为唯一值 //此时父节点为一个二节点 parent.add(itemData); //将新节点做为父节点的左子节点 parent.connectChild(0,newNode); //将中间节点做为父节点的中子节点 parent.connectChild(1,node); } //将父节点做为中间节点向上递归到父节点的父节点(即祖节点) connectNode(gParent,parent); //如果父节点是一个二节点 }else { //如果中间节点元素比父节点的唯一元素小 //这种情况应该是从父节点的左子节点进来的中间节点 if (data.compareTo(parent.getData(0)) < 0) { //分裂父节点的中子节点 Node tempNode = parent.disconnectChild(1); //分裂中间节点的左子节点做为父节点的左子节点 parent.connectChild(0,node.disconnectChild(0)); //分裂中间节点的中子节点做为父节点的中子节点 parent.connectChild(1,node.disconnectChild(1)); //将原父节点的中子节点做为父节点的右子节点 parent.connectChild(2,tempNode); //如果中间节点元素比父节点的唯一元素大 //这种情况应该是从父节点的中子节点进来的中间节点 }else { //分裂中间节点的左子节点做为父节点的中子节点 parent.connectChild(1,node.disconnectChild(0)); //分裂中间节点的中子节点做为父节点的右子节点 parent.connectChild(2,node.disconnectChild(1)); } //父节点添加中间节点元素(此时父节点为一个三节点) parent.add(data); } } @Override public boolean contains(T value) { Node node = contains(root,value); if (node != null) { return true; } return false; } private Node contains(Node node,T value) { if (node == null) { return null; } for (int i = 0; i < node.getSize(); i++) { if (node.getData(i).compareTo(value) > 0) { return contains(node.getChild(i), value); } else if (node.getData(i).compareTo(value) == 0) { return node; } } return contains(node.getChild(node.getSize()), value); } }
调用(此处List为JDK中的java.util.List)
public class BTreeMain { public static void main(String[] args) { BTree<Integer> bTree = new TwoThreeTree<>(Integer.class); List<Integer> list = Arrays.asList(42,37,12,18,6,11,5); list.stream().forEach(bTree::add); System.out.println(bTree.contains(18)); System.out.println(bTree.contains(11)); System.out.println(bTree.contains(32)); } }
运行结果
true
true
false
题外话
其实2-3树就是一个3阶B树，还有2-3-4树属于4阶B树。而m阶的B树特性
1.如果根节点不是叶子节点那么至少有两个子树。
2.所有叶子节点都位于同一层。
3.节点包含：关键字数组，指向孩子节点的指针数组，关键字数量。
以上也说明B树是一颗绝对平衡树。
而对于我们数据库mysql索引使用的B+树在B树之上做了修改
B+树：由于B树进行遍历的时候效率太低，而对于数据库和文件系统来说会经常进行范围查询，所以产生了B+树。
B+树可以看作是信息都是在叶子节点上，其他非叶子节点都是索引，目的是找到叶子节点，每个非叶子节点都保存叶子节点最小值及最小值所在叶子节点的索引，并且叶子节点之间有指针指向。
(图片来源于网络)
区别：
1.功能上说，B+遍历，范围查询效率高。
2.结构上说：B+信息都保存在叶子节点上，其他节点保存最小值索引，并且关键字对应的地址都在叶子节点上，而B树中非叶子节点也保存关键字对应的地址。
节点结构：B树的性质B+树一般都满足。
B树：
关键字数组，关键字对应的地址数组 子节点的指针数组，关键字的数量（子节点的最小数量是阶数的二分之一）
B+树：
关键字数组，关键字数量，子节点的指针数组。（每个节点关键字数量和子节点数量相同，并且每个关键字都是对应一个子节点关键字的最小值）
2-3树与红黑树的等价关系
二节点
三节点(所有的红色节点都是左倾斜的)
在三节点中，我们可以看到红黑树中的红色节点表示了2-3树中的三节点的左值，黑色节点表示了2-3树中三节点的右值。
则以下这棵2-3树
就等价于
当然为了更加形象，我们可以将这颗红黑树变成这个样子
现在我们来看一下红黑树的几个特性
1、每个节点或者是红色，或者是黑色的 这是废话
2、根节点是黑色的 如果在2-3树中，根节点要么是二节点，要么是三节点，那么不论是哪一种，对应红黑树中，红色节点一定是左倾斜的，所以根节点一定是黑色的。
3、每一个叶子结点(最后的空节点)是黑色的 对于一个空的红黑树，它的根节点是空的，并且根节点一定是黑色的，所以空节点也一定是黑色的。
4、如果一个节点是红色的，那么他的孩子节点都是黑色的 因为在2-3树中，三节点的左值连接的要么是一个二节点，要么是一个三节点。二节点肯定是黑色的，而三节点就类比于看根节点一样，红色节点一定是左倾斜的，所以连接到父三节点的一定是子三节点的右值，所以是黑色的。
5、从任意一个节点到叶子节点，经过的黑色节点是一样的 由于2-3树是一颗绝对平衡的树，所以红黑树中黑色节点对应2-3树要么是一个二节点，要么是一个三节点的右值，红黑树中保证了黑色节点的绝对平衡型。但红黑树整体并不一定是一颗平衡二叉树。现在我们假设一个2-3树的所有节点都是一个三节点，那么对应红黑树，它的高度就是2log n的，但由于2是一个常数，所以红黑树的时间复杂度依然是O(log n)的。虽然红黑树和AVL树都是O(log n)级别的，但是如果只是查询元素来说，AVL树的性能会更好一点，但对于频繁的增加删除来说，红黑树的性能就比AVL树要好。
红黑树添加新元素
在2-3树中添加元素的时候，我们都知道，2-3树是不会将元素添加到空节点的，它一定是将元素添加到一个已经存在的节点上。那么对应红黑树中，我们可以理解成，我们初始添加的元素一定是一个红色的节点，因为只有红色的节点才会是对已存在节点的融合。
但是在添加根节点的时候，因为我们新添加节点是一个红色的节点，而红黑树的根节点一定是一个黑色的节点，所以在添加根节点的时候，我们需要主动把根节点的颜色变成黑色。但还有一种情况，就是在2-3树中，当某个节点的子节点(可能是左、中、右子节点)发生向上融合的时候
该图中向上融合的是节点元素为4的节点(此处称为中间节点)，向上融合的中间节点一定是红色的，所以4这个节点一定是红色的，在向上融合中发生裂变，6这个节点变成中间节点，继续向上融合，所以6这个节点也是一个红色的节点。
但如果6这个节点没有父节点，那么它就是一个根节点，所以我们也需要主动把它的颜色变成黑色。此过程可以参考代码中的add(T value)的第二行代码。
现在我们在红黑树中依次增加42-37-66，来看一看这个过程。
42为其实红黑树的根节点，所以是一个黑色的节点，添加37会根据二分搜索树的性质，添加到42的左节点，再根据红黑树的性质，变成红色的节点。
但如果第一个添加的元素是37，第二个添加的元素是42该怎么办呢？
很明显它不满足红黑树的基本性质(红色的节点一定是左倾斜的)，所以我们要将其进行一个左旋转，就变成了上面的以42为根节点，37为左节点的情况。所以无论是哪个先进来，其结果都一样。(左旋转的定义请参考AVL树中的内容，唯一不同的是我们要记得维护两个节点的颜色)，此过程对应于代码中的leftRotate()方法
在添加66的过程中，根据二分搜索树的性质，66应该添加到42的右节点
这在2-3树中，相当于一个这样的过程，它最终会分裂成3个二节点。所以在对应的红黑树中，最终分裂成的二节点都应该是黑色的。
但如果中间节点42有父节点，就表示中间节点需要跟它的父节点做融合，那么此时中间节点是红色的节点。(这里需要注意的是，我们只判断中间节点是否是根节点的时候才把它变成黑色，如果是向上融合的节点，就是红色的)，此过程对应于代码中的flipColors()方法
现在我们来依次向红黑树中添加42-37-12，来看看会是什么情况。根据二分搜索树的性质，会将12添加到37的左节点
在2-3树中，这个过程，就是这样的一个情况，它最终会裂变成3个二节点。
对应于红黑树中，我们需要对根节点42做一个右旋转(右旋转的定义请参考AVL树中的内容，唯一不同的是我们要记得维护两个节点的颜色)，此过程请参考代码中的rightRotate()方法。
在右旋转完成后，我们需要将新的中间节点变成原来中间节点的颜色，将向右旋转的42元素的原中间节点变成红色。
但是我们知道在2-3树中，二节点都是黑色的，所以上图的情况就跟我们之前处理42-37-66的过程一样了，只需要进行一个颜色翻转，所以最终的结果如下图所示(这里同样考虑了中间节点向上融合的情况，如果最终判定37是根结点，会将37转变为黑色)
现在我们来依次向红黑树中添加42-37-40，来看看会是什么情况。根据二分搜索树的性质，40将会被添加为37的右节点。
其实这种情况并不需要借助于2-3树来做分析，我们只需要将37这个节点进行一次左旋转就可以了
这样就变成了类似依次添加42-37-12的过程，按照这个过程进行处理就好了。
根据以上的种种情况，我们可以给红黑树添加新元素总结为以下的一整个流程。
我们可以看到这是一个在2-3树的三节点中添加一个元素的过程，如果我们添加的是一个比红色节点大，比黑色节点小的情况，就如上图一样。那如果我们添加的元素比红色节点小的话，就等于从第一步直接跳到了第三步。
那如果我们添加的元素比黑色节点大的话，就相当于从第一步直接跳到了第四步
在红黑树整个添加元素的过程中，首先是按照二分搜索树来进行添加的，这一点没有变，只不过在二分搜索树中添加完成了节点，我们需要对添加的节点进行红黑树性质的维护。维护的过程正是上面的整个过程，要根据不同的情况进行判断。
而判断的依据就是要看这个新添加的元素的节点到底添加到了它的父节点的哪个位置。
如果这个新节点在其父节点的右节点，且其父节点的左节点是黑色节点的时候(意思是父节点相当于2-3树的二节点或者三节点的左值)，对其父节点进行左旋转。
如果这个新节点在其父节点的左节点，当其父节点本身是红色节点的时候(意思是父节点相当于2-3树的三节点的左值)，对其祖节点(相当于2-3树的三节点的右值)进行右旋转。
如果这个新节点在其父节点的右节点，且其父节点的左节点是红色节点的时候(意思是父节点相当于2-3树的三节点的右值)，对其父节点以及父节点的左右节点进行颜色翻转。
红黑树实现类
public class RedBlackTree<T extends Comparable<T>> implements Tree<T> { private static final boolean RED = true; private static final boolean BLACK = false; @Data @AllArgsConstructor private class Node{ private T element; private Node left; private Node right; private Boolean color; public Node(T element) { this(element,null,null,RED); } } private Node root; private int size; public RedBlackTree() { root = null; size = 0; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } /** * 判断节点node的颜色 * @param node * @return */ private boolean isRed(Node node) { if (node == null) { return BLACK; } return node.getColor(); } /** * 左旋转 * @param node * @return */ private Node leftRotate(Node node) { Node ret = node.getRight(); Node retLeft = ret.getLeft(); node.setRight(retLeft); ret.setLeft(node); ret.setColor(node.getColor()); node.setColor(RED); return ret; } /** * 右旋转 * @param node * @return */ private Node rightRotate(Node node) { Node ret = node.getLeft(); Node retRight = ret.getRight(); node.setLeft(retRight); ret.setRight(node); ret.setColor(node.getColor()); node.setColor(RED); return ret; } /** * 颜色翻转 * @param node */ private void flipColors(Node node) { node.setColor(RED); node.getLeft().setColor(BLACK); node.getRight().setColor(BLACK); } private Node balance(Node node) { if (isRed(node.getRight())) { node = leftRotate(node); } //维护红黑树 if (isRed(node.getRight()) && !isRed(node.getLeft())) { node = leftRotate(node); } if (isRed(node.getLeft()) && isRed(node.getLeft().getLeft())) { node = rightRotate(node); } if (isRed(node.getLeft()) && isRed(node.getRight())) { flipColors(node); } return node; } @Override public void add(T value) { root = add(root,value); root.setColor(BLACK); } private Node add(Node node, T value) { //递归终止条件 if (node == null) { size++; return new Node(value); } //递归 if (value.compareTo(node.getElement()) < 0) { node.setLeft(add(node.getLeft(),value)); }else if (value.compareTo(node.getElement()) > 0) { node.setRight(add(node.getRight(),value)); } //维护红黑树 if (isRed(node.getRight()) && !isRed(node.getLeft())) { node = leftRotate(node); } if (isRed(node.getLeft()) && isRed(node.getLeft().getLeft())) { node = rightRotate(node); } if (isRed(node.getLeft()) && isRed(node.getRight())) { flipColors(node); } return node; } @Override public boolean contains(T value) { return contains(root,value); } private boolean contains(Node node, T value) { if (node == null) { return false; } if (value.compareTo(node.getElement()) == 0) { return true; }else if (value.compareTo(node.getElement()) < 0) { return contains(node.getLeft(),value); }else { return contains(node.getRight(),value); } } @Override public void preOrder() { preOrder(root); } private void preOrder(Node node) { if (node == null) { return; } System.out.println(node.getElement()); preOrder(node.getLeft()); preOrder(node.getRight()); } /** * 非递归前序遍历 */ public void preOrderNR() { Stack<Node> stack = new ArrayStack<>(); stack.push(root); while (!stack.isEmpty()) { Node cur = stack.pop(); System.out.println(cur.getElement()); if (cur.getRight() != null) { stack.push(cur.getRight()); } if (cur.getLeft() != null) { stack.push(cur.getLeft()); } } } @Override public void inOrder() { inOrder(root); } private void inOrder(Node node) { if (node == null) { return; } inOrder(node.getLeft()); System.out.println(node.getElement()); inOrder(node.getRight()); } @Override public void postOrder() { postOrder(root); } private void postOrder(Node node) { if (node == null) { return; } postOrder(node.getLeft()); postOrder(node.getRight()); System.out.println(node.getElement()); } @Override public void levelOrder() { Queue<Node> queue = new LoopQueue<>(); queue.enqueue(root); while (!queue.isEmpty()) { Node cur = queue.dequeue(); System.out.println(cur.getElement()); if (cur.getLeft() != null) { queue.enqueue(cur.getLeft()); } if (cur.getRight() != null) { queue.enqueue(cur.getRight()); } } } @Override public T minimum() { if (size == 0) { throw new IllegalArgumentException("二分搜索树为空"); } return minimum(root).getElement(); } private Node minimum(Node node) { if (node.getLeft() == null) { return node; } return minimum(node.getLeft()); } @Override public T maximum() { if (size == 0) { throw new IllegalArgumentException("二分搜索树为空"); } return maximum(root).getElement(); } private Node maximum(Node node) { if (node.getRight() == null) { return node; } return maximum(node.getRight()); } @Override public T removeMin() { T ret = minimum(); if (!isRed(root.getLeft()) && !isRed(root.getRight())) { root.setColor(RED); } root = removeMin(root); if (!isEmpty()) { root.setColor(BLACK); } return ret; } private Node removeRedLeft(Node node) { if (isRed(node) && !isRed(node.getLeft()) && !isRed(node.getLeft().getLeft())) { node.getLeft().setColor(RED); } if (isRed(node.getRight().getLeft())) { node.setRight(rightRotate(node.getRight())); node = leftRotate(node); } return node; } private Node removeMin(Node node) { if (node.getLeft() == null) { size--; return null; } if (!isRed(node.getLeft()) && !isRed(node.getLeft().getLeft())) { node = removeRedLeft(node); } node.setLeft(removeMin(node.getLeft())); return balance(node); } @Override public T removeMax() { T ret = maximum(); if (!isRed(root.getLeft()) && !isRed(root.getRight())) { root.setColor(RED); } root = removeMax(root); if (!isEmpty()) { root.setColor(BLACK); } return ret; } private Node removeRedRight(Node node) { if (isRed(node) && !isRed(node.getRight()) && !isRed(node.getRight().getLeft())) { node.getRight().setColor(RED); } if (!isRed(node.getLeft().getLeft())) { node = rightRotate(node); } return node; } private Node removeMax(Node node) { if (isRed(node.getLeft())) { node = rightRotate(node); } if (node.getRight() == null) { size--; return null; } if (!isRed(node.getRight()) && !isRed(node.getRight().getLeft())) { node = removeRedRight(node); } node.setRight(removeMax(node.getRight())); return balance(node); } @Override public void remove(T value) { if (!isRed(root.getLeft()) && !isRed(root.getRight())) { root.setColor(RED); } root = remove(root,value); if (!isEmpty()) { root.setColor(BLACK); } } private Node remove(Node node,T value) { if (value.compareTo(node.getElement()) < 0) { if (!isRed(node.getLeft()) && !isRed(node.getLeft().getLeft())) { size--; node = removeRedLeft(node); } node.setLeft(remove(node.getLeft(),value)); }else { if (isRed(node.getLeft())) { node = rightRotate(node); } if (value.compareTo(node.getElement()) == 0 && node.getRight() == null) { return null; } if (!isRed(node.getRight()) && !isRed(node.getRight().getLeft())) { node = removeRedRight(node); } if (value.compareTo(node.getElement()) == 0) { node.setElement(minimum(node.getRight()).getElement()); node.setRight(removeMin(node.getRight())); }else { node.setRight(remove(node.getRight(),value)); } } return balance(node); } @Override public T floor(T value) { Node node = floor(root,value); if (node != null) { return node.getElement(); } return null; } private Node floor(Node node, T value) { if (node == null) { return null; } if (value.compareTo(node.getElement()) <= 0) { return floor(node.getLeft(),value); }else { if (node.getRight() == null) { return node; }else if (node.getRight().getLeft() == null && value.compareTo(node.getRight().getElement()) <= 0) { return node; }else if (node.getRight().getRight() == null && value.compareTo(node.getRight().getElement()) > 0) { return node.getRight(); } return floor(node.getRight(),value); } } @Override public T ceil(T value) { Node node = ceil(root,value); if (node != null) { return node.getElement(); } return null; } private Node ceil(Node node, T value) { if (node == null) { return null; } if (value.compareTo(node.getElement()) >= 0) { return ceil(node.getRight(),value); }else { if (node.getLeft() == null) { return node; }else if (value.compareTo(maximum(node.getLeft()).getElement()) >= 0) { return node; }else if (node.getLeft().getRight() == null && value.compareTo(node.getLeft().getElement()) >= 0) { return node; }else if (node.getLeft().getLeft() == null && value.compareTo(node.getLeft().getElement()) < 0) { return node.getLeft(); } return ceil(node.getLeft(),value); } } @Override public String toString() { StringBuilder builder = new StringBuilder(); generateBSTString(root,0,builder); return builder.toString(); } private void generateBSTString(Node node, int depth, StringBuilder builder) { if (node == null) { builder.append(generateDepthString(depth) + "null\n"); return; } builder.append(generateDepthString(depth) + node.getElement() + "\n"); generateBSTString(node.getLeft(),depth + 1,builder); generateBSTString(node.getRight(),depth + 1,builder); } private String generateDepthString(int depth) { StringBuilder builder = new StringBuilder(); for (int i = 0;i < depth;i++) { builder.append("--"); } return builder.toString(); } }
- 红黑树映射封装
实现类
public class RedBlackTreeMap<K extends Comparable<K>,V> implements Map<K,V> { private static final boolean RED = true; private static final boolean BLACK = false; @Data @AllArgsConstructor private class Node{ private K key; private V value; private Node left; private Node right; private Boolean color; public Node(K key) { this(key,null,null,null,RED); } public Node(K key,V value) { this(key,value,null,null,RED); } } private Node root; private int size; public RedBlackTreeMap() { root = null; size = 0; } /** * 判断节点node的颜色 * @param node * @return */ private boolean isRed(Node node) { if (node == null) { return BLACK; } return node.getColor(); } /** * 左旋转 * @param node * @return */ private Node leftRotate(Node node) { Node ret = node.getRight(); Node retLeft = ret.getLeft(); node.setRight(retLeft); ret.setLeft(node); ret.setColor(node.getColor()); node.setColor(RED); return ret; } /** * 右旋转 * @param node * @return */ private Node rightRotate(Node node) { Node ret = node.getLeft(); Node retRight = ret.getRight(); node.setLeft(retRight); ret.setRight(node); ret.setColor(node.getColor()); node.setColor(RED); return ret; } /** * 颜色翻转 * @param node */ private void flipColors(Node node) { node.setColor(RED); node.getLeft().setColor(BLACK); node.getRight().setColor(BLACK); } @Override public void add(K key, V value) { root = add(root,key,value); } private Node add(Node node, K key,V value) { //递归终止条件 if (node == null) { size++; return new Node(key,value); } //递归 if (key.compareTo(node.getKey()) < 0) { node.setLeft(add(node.getLeft(),key,value)); }else if (key.compareTo(node.getKey()) > 0) { node.setRight(add(node.getRight(),key,value)); }else { node.setValue(value); } //维护红黑树 if (isRed(node.getRight()) && !isRed(node.getLeft())) { node = leftRotate(node); } if (isRed(node.getLeft()) && isRed(node.getLeft().getLeft())) { node = rightRotate(node); } if (isRed(node.getLeft()) && isRed(node.getRight())) { flipColors(node); } return node; } @Override public V remove(K key) { throw new IllegalArgumentException("未支持的方法"); } @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.getValue(); } @Override public void set(K key, V value) { Node node = getNode(root,key); if (node == null) { throw new IllegalArgumentException(key + "不存在"); } node.setValue(value); } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } private Node getNode(Node node,K key) { if (node == null) { return null; } if (key.compareTo(node.getKey()) == 0) { return node; }else if (key.compareTo(node.getKey()) < 0) { return getNode(node.getLeft(),key); }else { return getNode(node.getRight(),key); } } }
四种映射的性能测试
public class TestMapMain { private static double testMap(Map<String,Integer> map,String filename) { long startTime = System.nanoTime(); System.out.println(filename); Array<String> words = new DefaultArray<>(); FileOperation.readFile(filename,words); System.out.println("共有单词: " + words.getSize()); Stream.of(words.getData()).filter(word -> word != null) .forEach(word -> { if (map.contains(word)) { map.set(word,map.get(word) + 1); }else { map.add(word,1); } }); System.out.println("共有不同的单词: " + map.getSize()); System.out.println("pride出现的次数: " + map.get("pride")); System.out.println("prejudice出现的次数: " + map.get("prejudice")); long endTime = System.nanoTime(); return (endTime - startTime) / 1000000000.0; } public static void main(String[] args) { String filename = "/Users/admin/Downloads/pride-and-prejudice.txt"; Map<String,Integer> bstMap = new BSTMap<>(); double time1 = testMap(bstMap,filename); System.out.println("BST Map: " + time1 + " s"); Map<String,Integer> linkedListMap = new LinkedListMap<>(); double time2 = testMap(linkedListMap,filename); System.out.println("LinkedList Map: " + time2 + " s"); Map<String,Integer> avlTreeMap = new AVLTreeMap<>(); double time3 = testMap(avlTreeMap,filename); System.out.println("AVLTree Map: " + time3 + " s"); Map<String,Integer> redBlackTreeMap = new RedBlackTreeMap<>(); double time4 = testMap(redBlackTreeMap,filename); System.out.println("RedBlackTree Map: " + time4 + " s"); } }
测试结果
/Users/admin/Downloads/pride-and-prejudice.txt
共有单词: 125901
共有不同的单词: 6530
pride出现的次数: 53
prejudice出现的次数: 11
BST Map: 0.171121365 s
/Users/admin/Downloads/pride-and-prejudice.txt
共有单词: 125901
共有不同的单词: 6530
pride出现的次数: 53
prejudice出现的次数: 11
LinkedList Map: 9.213896232 s
/Users/admin/Downloads/pride-and-prejudice.txt
共有单词: 125901
共有不同的单词: 6530
pride出现的次数: 53
prejudice出现的次数: 11
AVLTree Map: 0.070547497 s
/Users/admin/Downloads/pride-and-prejudice.txt
共有单词: 125901
共有不同的单词: 6530
pride出现的次数: 53
prejudice出现的次数: 11
RedBlackTree Map: 0.061147762 s
LeetCode算法题 https://leetcode-cn.com/problems/first-unique-character-in-a-string/
这是LeetCode的第387题——字符串中的第一个唯一字符
因为马上要进入散列哈希表的话题，我们就先使用HashMap来解题
class Solution { public int firstUniqChar(String s) { Map<Character,Integer> map = new HashMap<>(); for (int i = 0;i < s.length();i++) { if (map.putIfAbsent(s.charAt(i),1) != null) { map.put(s.charAt(i),map.get(s.charAt(i)) + 1); } } for (int i = 0;i < s.length();i++) { if (map.get(s.charAt(i)) == 1) { return i; } } return -1; } }
提交给LeetCode
当然为了更好的说明哈希表的内部原理，我们将方法改写一下，只使用数组来实现。
public 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; } }
提交给LeetCode
- 哈希表封装
哈希是通过牺牲可比较性可排序性，来获取比树更快的时间复杂度的一种数据结构，而要实现哈希，最重要的在于两点：哈希函数的设计，哈希冲突的解决。
哈希函数的设计
哈希函数的设计是为了把"元素"通过哈希函数得到的"索引"在数组中分布越均匀越好。
整型
小范围的正整数直接使用，小范围的负整数进行偏移(-100~100->0~200)。
大整数，如身份证号，通常做法：取模，比如，取后四位，等同于mod 10000，但是取模有陷阱，如果取模的数选择不当，会造成分布不均匀。比如身份证中有的数字有日期的语义，如果取后六位mod 1000000，那么这个数就永远不可能大于320000.
如果不考虑具体数字有语义的话，一个简单的解决办法：模一个素数
10 % 4 = 2 10 % 7 = 3
20 % 4 = 0 20 % 7 = 6
30 % 4 = 2 30 % 7 = 2
40 % 4 = 0 40 % 7 = 4
50 % 4 = 2 50 % 7 = 1
通过上面两组数据的比较，我们可以看到4是一个合数，7是一个素数，则很明显，对7取模所得到的数分布更加均匀。
对于在什么范围内的数取模的素数是多少分布更加均匀，可以参考https://planetmath.org/goodhashtableprimes，其实这些也是数学家计算出来的结果。
浮点型
在计算机中都是32位或64位的二进制表示，只不过计算机解析成了浮点数。
我们只需要将其转成整型处理即可，然后再进行取模。
字符串
同样转成整型处理
code = c * B^3 + o * B^2 + d * B^1 + e * B^0
当然这个B是一个基数，由我们根据字符串的范围(如是否包含大小写，是否包含符号，是否包含汉字)来决定。
则我们的哈希函数可以设计为：hash(code) = (c * B^3 + o * B^2 + d * B^1 + e * B^0) % M
= ((((c * B) + o) * B + d) * B + e) % M
= ((((c % M) * B + o) % B * B + d) % M * B + e) % M
对于程序来说可以看成是如下所示
int hash = 0; for (int i = 0;i < s.length();i++) { hash = (hash * B + s.charAt(i)) % M; }
复合类型
同样是转成整型来处理。
哈希函数的设计有很多种，但原则为
- 一致性: 如果a == b,则hash(a) == hash(b)
- 高效性: 计算高效简便
- 均匀性: 哈希值均匀分布
当然在Java中，我们一般都是以对象的hashCode值来进行转化成整型的。
public class HashCodeMain { public static void main(String[] args) { int a = 42; System.out.println(((Integer)a).hashCode()); int b = -42; System.out.println(((Integer)b).hashCode()); double c = 3.1415926; System.out.println(((Double)c).hashCode()); String d = "code"; System.out.println(d.hashCode()); } }
运行结果
42
-42
219937201
3059181
但如果对于一个普通的类，我们就需要重写它的hashCode()方法(此处名字不区分大小写)，如果要判定两个该类的对象是否相等，就需要重写equals()方法
@AllArgsConstructor public class Student { private int grade; private int cls; String firstName; String lastName; @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Student student = (Student) o; if (grade != student.grade) return false; if (cls != student.cls) return false; if (!firstName.toLowerCase().equals(student.firstName.toLowerCase())) return false; return lastName.toLowerCase().equals(student.lastName.toLowerCase()); } @Override public int hashCode() { int B = 31; int result = 0; result = B * result + grade; result = B * result + cls; result = B * result + firstName.toLowerCase().hashCode(); result = B * result + lastName.toLowerCase().hashCode(); return result; } }
public class HashCodeMain { public static void main(String[] args) { int a = 42; System.out.println(((Integer)a).hashCode()); int b = -42; System.out.println(((Integer)b).hashCode()); double c = 3.1415926; System.out.println(((Double)c).hashCode()); String d = "code"; System.out.println(d.hashCode()); Student student = new Student(3,2,"bobo","liu"); System.out.println(student.hashCode()); } }
运行结果
42
-42
219937201
3059181
94107933
但如果我们没有重写Object父类的hashCode()方法，我们依然也可以使用hashCode()方法，只不过此时打印出来的hashCode()值是JVM为我们分配的一个内存地址，而此时每一个对象的内存地址都一定是不相同的。
public class HashCodeMain { public static void main(String[] args) { int a = 42; System.out.println(((Integer)a).hashCode()); int b = -42; System.out.println(((Integer)b).hashCode()); double c = 3.1415926; System.out.println(((Double)c).hashCode()); String d = "code"; System.out.println(d.hashCode()); Student student = new Student(3,2,"bobo","liu"); System.out.println(student.hashCode()); Student student1 = new Student(3,2,"bobo","liu"); System.out.println(student1.hashCode()); System.out.println(student.equals(student1)); } }
运行结果
42
-42
219937201
3059181
1496724653
553264065
false
但是如果我们重写了hashCode()和equals()方法后。
运行结果
42
-42
219937201
3059181
94107933
94107933
true
哈希冲突的处理——链地址法
这是一个有M个空间大小的数组，当我们有一个元素要放入这个数组中的时候
一般我们会对这个元素进行一次hashCode的获取，再对M取模——hashCode(k1) % M
但有可能hashCode(k1)是一个负的哈希值,此时我们完全可以使用取绝对值的形式将负号给抹去
Math.abs(hashCode(k1)) % M
我们已经知道了一个 int 型数值是 4 个字节。每个字节有 8 位。但对于一个 int 或者其它整数类型如 （long）的数值而言还要注意的是，它的最高位是符号位。
最高位为0表示正数。
最高位为1表示负数
原码 将一个数字转换成二进制就是这个数值的原码。
int a = 5; //原码 0000 0000 0000 0000 0000 0000 0000 0101
int b = -3; //原码 1000 0000 0000 0000 0000 0000 0000 0011
在进行位运算的时候，我们要将负号抹去，需要跟二进制0111 1111 1111 1111 1111 1111 1111 1111(十六进制为0x7fffffff)进行一次与运算,这样最高位的符号位1就被消除了，而其他位都保持不变。
所以消除负号在位运算中也可以写成
(hashCode(k1) & 0x7fffffff) % M
更多关于位运算的内容可以参考Java的二进制位操作整理
现在我们假设k1经过hash计算出来的索引值为4，而再来一个k2经过hash计算出来的索引值为1
此时再来一个k3，它的索引值也为1，这个时候就跟k2产生了哈希冲突，此时我们需要将k3放到1的位置，并且跟k2组成一个链表，放在k2的next节点。
但对于这种结构的连接可以属于查找表的范畴，我们也可以完全不使用链表，而使用树结构(比如红黑树)来构建查找表。所以我们在数组中存的就可以是一个TreeSet或者TreeMap
在JDK8之前，每一个位置对应一个链表，从JDK8开始，当哈希冲突达到一定程度，每一个位置从链表转成红黑树。但是这里有一个问题，那就是红黑树是一个二分搜索树，所以要求每一个存入红黑树的元素必须是可比较，可查找的，即实现了Comparable接口的元素，才会转成红黑树，否则是不会转成红黑树的，依然以链表的形式存在，因为链表并没有这个要求，不需要元素必须是可比较的。
接口
public interface Hash<T> { int getSize(); void add(T t); void remove(T t); boolean contains(T t); }
实现类(Set接口和TreeSet为JDK中的java.util.Set和java.util.TreeSet)
public class HashTable<T> implements Hash<T> { private final int[] capacity = {53,97,193,389,769,1543,3079,6151,12289,24593, 49157,98317,196613,393241,786433,1572869,3145739, 6291469,12582917,25165843,50331653,100663319, 201326611,402653189,805306457,1610612741}; //容忍度上界 private static final int upperTol = 10; //容忍度下届 private static final int lowerTol = 2; private int capacityIndex = 0; private Set<T>[] hashtable; private int M; private int size; @SuppressWarnings("unchecked") public HashTable() { this.M = capacity[capacityIndex]; size = 0; hashtable = new TreeSet[M]; for (int i = 0;i < M;i++) { hashtable[i] = new TreeSet<>(); } } private int hash(T value) { //消除value的哈希值的正负号再对M取模 return (value.hashCode() & 0x7fffffff) % M; } @Override public int getSize() { return size; } @Override public void add(T value) { Set<T> set = hashtable[hash(value)]; if (!set.contains(value)) { set.add(value); size++; if (size >= upperTol * M && capacityIndex + 1 < capacity.length) { capacityIndex++; resize(capacity[capacityIndex]); } } } @Override public void remove(T value) { Set<T> set = hashtable[hash(value)]; if (set.contains(value)) { set.remove(value); size--; if (size < lowerTol * M && capacityIndex - 1 >= 0) { capacityIndex--; resize(capacity[capacityIndex]); } } } @Override public boolean contains(T value) { return hashtable[hash(value)].contains(value); } @SuppressWarnings("unchecked") private void resize(int newM) { Set<T>[] newHashTable = new TreeSet[newM]; for (int i = 0;i < newM;i++) { newHashTable[i] = new TreeSet<>(); } int oldM = this.M; this.M = newM; for (int i = 0;i < oldM;i++) { Set<T> set = hashtable[i]; set.stream().forEach(value -> newHashTable[hash(value)].add(value)); } this.hashtable = newHashTable; } }
- Hash映射封装
实现类(此处SortedMap接口和TreeMap为JDK的java.util.SortedMap,java.util.TreeMap)
public class HashMap<K,V> implements Map<K,V> { private final int[] capacity = {53,97,193,389,769,1543,3079,6151,12289,24593, 49157,98317,196613,393241,786433,1572869,3145739, 6291469,12582917,25165843,50331653,100663319, 201326611,402653189,805306457,1610612741}; //容忍度上界 private static final int upperTol = 10; //容忍度下届 private static final int lowerTol = 2; private int capacityIndex = 0; private SortedMap<K,V>[] hashtable; private int M; private int size; @SuppressWarnings("unchecked") public HashMap() { this.M = capacity[capacityIndex]; size = 0; hashtable = new TreeMap[M]; for (int i = 0;i < M;i++) { hashtable[i] = new TreeMap<>(); } } private int hash(K key) { //消除key的哈希值的正负号再对M取模 return (key.hashCode() & 0x7fffffff) % M; } @Override public void add(K key, V value) { SortedMap<K,V> map = hashtable[hash(key)]; if (map.containsKey(key)) { map.put(key, value); }else { map.put(key, value); size++; if (size >= upperTol * M && capacityIndex + 1 < capacity.length) { capacityIndex++; resize(capacity[capacityIndex]); } } } @Override public V remove(K key) { SortedMap<K,V> map = hashtable[hash(key)]; if (map.containsKey(key)) { V ret = map.remove(key); size--; if (size < lowerTol * M && capacityIndex - 1 >= 0) { capacityIndex--; resize(capacity[capacityIndex]); } return ret; } return null; } @Override public boolean contains(K key) { return hashtable[hash(key)].containsKey(key); } @Override public V get(K key) { return hashtable[hash(key)].get(key); } @Override public void set(K key, V value) { SortedMap<K,V> map = hashtable[hash(key)]; if (!map.containsKey(key)) { throw new IllegalArgumentException("key不存在"); } map.put(key,value); } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @SuppressWarnings("unchecked") private void resize(int newM) { SortedMap[] newHashTable = new TreeMap[newM]; for (int i = 0;i < newM;i++) { newHashTable[i] = new TreeMap(); } int oldM = this.M; this.M = newM; for (int i = 0;i < oldM;i++) { SortedMap<K,V> map = hashtable[i]; map.keySet().stream().forEach(key -> newHashTable[hash(key)].put(key,map.get(key))); } this.hashtable = newHashTable; } }
对五种映射的性能测试
public class TestMapMain { private static double testMap(Map<String,Integer> map,String filename) { long startTime = System.nanoTime(); System.out.println(filename); Array<String> words = new DefaultArray<>(); FileOperation.readFile(filename,words); System.out.println("共有单词: " + words.getSize()); Stream.of(words.getData()).filter(word -> word != null) .forEach(word -> { if (map.contains(word)) { map.set(word,map.get(word) + 1); }else { map.add(word,1); } }); System.out.println("共有不同的单词: " + map.getSize()); System.out.println("pride出现的次数: " + map.get("pride")); System.out.println("prejudice出现的次数: " + map.get("prejudice")); long endTime = System.nanoTime(); return (endTime - startTime) / 1000000000.0; } public static void main(String[] args) { String filename = "/Users/admin/Downloads/pride-and-prejudice.txt"; Map<String,Integer> bstMap = new BSTMap<>(); double time1 = testMap(bstMap,filename); System.out.println("BST Map: " + time1 + " s"); Map<String,Integer> linkedListMap = new LinkedListMap<>(); double time2 = testMap(linkedListMap,filename); System.out.println("LinkedList Map: " + time2 + " s"); Map<String,Integer> avlTreeMap = new AVLTreeMap<>(); double time3 = testMap(avlTreeMap,filename); System.out.println("AVLTree Map: " + time3 + " s"); Map<String,Integer> redBlackTreeMap = new RedBlackTreeMap<>(); double time4 = testMap(redBlackTreeMap,filename); System.out.println("RedBlackTree Map: " + time4 + " s"); Map<String,Integer> hashMap = new HashMap<>(); double time5 = testMap(hashMap,filename); System.out.println("Hash Map: " + time5 + " s"); } }
测试结果
/Users/admin/Downloads/pride-and-prejudice.txt
共有单词: 125901
共有不同的单词: 6530
pride出现的次数: 53
prejudice出现的次数: 11
BST Map: 0.168990167 s
/Users/admin/Downloads/pride-and-prejudice.txt
共有单词: 125901
共有不同的单词: 6530
pride出现的次数: 53
prejudice出现的次数: 11
LinkedList Map: 9.299100543 s
/Users/admin/Downloads/pride-and-prejudice.txt
共有单词: 125901
共有不同的单词: 6530
pride出现的次数: 53
prejudice出现的次数: 11
AVLTree Map: 0.067501294 s
/Users/admin/Downloads/pride-and-prejudice.txt
共有单词: 125901
共有不同的单词: 6530
pride出现的次数: 53
prejudice出现的次数: 11
RedBlackTree Map: 0.058438515 s
/Users/admin/Downloads/pride-and-prejudice.txt
共有单词: 125901
共有不同的单词: 6530
pride出现的次数: 53
prejudice出现的次数: 11
Hash Map: 0.039921075 s
