# 数据结构整理

2020/01/22 20:41

• 数组封装

public interface Array<T> {
T[] getData();
int getSize();
int getCapacity();
boolean isEmpty();
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
}

@Override
}

@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);
System.out.println(array);
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 = 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会被忽略

resize                             O(n)

removeLast()                 O(1)

removeFirst()                 O(n)

remove(index)                O(n/2) = 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) {
}

@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)

• push(value)              O(1) 均摊
• Pop()                         O(1) 均摊
• peek()                       O(1)
• getSize()                   O(1)
• isEmpty()                  O(1)

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

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) {
}

@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)

enqueue(value)                      O(1) 均摊

dequeue()                               O(n)

getFront()                               O(1)

getSize()                                 O(1)

isEmpty()                                O(1)

• 循环队列封装

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

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

• 单向链表封装

public interface List<T> {
int getSize();
boolean isEmpty();
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 int size;

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("添加错误，非法索引");
}

for (int i = 0; i < index; i++) {
prev = prev.getNext();
}
prev.setNext(new Node(value, prev.getNext()));
size++;

}

@Override
}

@Override
}

@Override
public T get(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("获取错误，非法索引");
}
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("设置错误，非法索引");
}
for (int i = 0;i < index;i++) {
cur = cur.getNext();
}
cur.setElement(value);
}

@Override
public boolean contains(T value) {
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("删除错误，非法索引");
}
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) {
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();
while (cur != null) {
builder.append(cur + "->");
cur = cur.getNext();
}
builder.append("NULL");
return builder.toString();
}
}

public class ListMain {
public static void main(String[] args) {
for (int i = 0;i < 5;i++) {
}

}
}

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

removeLast()                         O(n)

removeFirst()                         O(1)

remove(index)                       O(n/2) = O(n)

removeElement(value)         O(n)

set(index,value)                    O(n)

get(index)                              O(n)

contains(value)                     O(n)

• 链表栈封装

@ToString
public class LinkedListStack<T> implements Stack<T> {
private List<T> list;

}

@Override
public void push(T 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) {
for (int i = 0;i < 5;i++) {
stack.push(i);
System.out.println(stack);
}
stack.pop();
System.out.println(stack);
}
}

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");

System.out.println("LinkedListStack,time: " + time2 + " s");
}
}

ArrayStack,time: 0.891863504 s

• 链表队列封装

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 tail;
/**
* 队列元素个数
*/
private int size;

tail = null;
size = 0;
}

@Override
public void enqueue(T value) {
//当整个队列为空的时候
if (tail == null) {
tail = new Node(value);
}else { //从尾部入队
tail.setNext(new Node(value));
tail = tail.getNext();
}
size++;
}

@Override
public T dequeue() {
if (isEmpty()) {
throw new IllegalArgumentException("无法从空队列出队");
}
//从头部出队
retNode.setNext(null);
tail = null;
}
size--;
return retNode.getElement();
}

@Override
public T getFront() {
if (isEmpty()) {
throw new IllegalArgumentException("队列为空");
}
}

@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 ");
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) {
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");

System.out.println("LinkedListQueue,time: " + time3 + " s");
}
}

ArrayQueue,time: 2.727521755 s
LoopQueue,time: 0.011994964 s

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");

System.out.println("LinkedListQueue,time: " + time3 + " s");
}
}

LoopQueue,time: 1.198824936 s

[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]
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 (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]
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

-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]
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

输入: 1->2->6->3->4->5->6, val = 6

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的头部节点
delNode.next = null;
}
return null;
}
//移除所有可能值为val的中间节点
while (prev.next != null) {
if (prev.next.val == val) {
ListNode delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
}else {
prev = prev.next;
}
}
}
}

public class Solution {
public ListNode removeElements(ListNode head, int val) {
//建立虚拟头节点
//移除所有可能值为val的中间节点
while (prev.next != null) {
if (prev.next.val == val) {
ListNode delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
}else {
prev = prev.next;
}
}
}
}

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) {
//建立虚拟头节点
//移除所有可能值为val的中间节点
while (prev.next != null) {
if (prev.next.val == val) {
ListNode delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
}else {
prev = prev.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

• 链表的递归性

public class Solution {
public ListNode removeElements(ListNode head, int val) {
//求解最基本的问题
return null;
}
//把原问题转化成更小的问题
//此时把链表拆分成头节点+一个不包含头节点的链表
//拼接头节点
return node;
}else {
}
}

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) {
//求解最基本的问题
return null;
}
//把原问题转化成更小的问题
//此时把链表拆分成头节点+一个不包含头节点的链表
//是否拼接头节点
}

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 + "中");
//求解最基本的问题
System.out.print(depthString);
return null;
}
//把原问题转化成更小的问题
//此时把链表拆分成头节点+一个不包含头节点的链表
ListNode node = removeElements(head.next, val,depth + 1);
System.out.print(depthString);
System.out.println("删除 " + val + "之后: " + node);
//是否拼接头节点
ListNode ret;
ret = node;
}else {
}
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在 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

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 int size;

size = 0;
}
@Override
public int getSize() {
return size;
}

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

@Override
}

@Override
public void add(int index, T value) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("添加错误，非法索引");
}
}

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;
}
return node;
}

@Override
}

@Override
public T get(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("查找错误，非法索引");
}
}

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("更新错误，非法索引");
}
}

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) {
}

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("删除错误，非法索引");
}
}

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) {
}

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();
while (cur != null) {
builder.append(cur + "->");
cur = cur.getNext();
}
builder.append("NULL");
return builder.toString();
}
}

public class ListMain {
public static void main(String[] args) {
for (int i = 0;i < 5;i++) {
}

}
}

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 tail;
private int size;

tail = null;
size = 0;
}
@Override
public int getSize() {
return size;
}

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

@Override
}

@Override
public void add(int index, T value) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("添加错误，非法索引");
}
if (index <= size / 2 + 1) {
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) {
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
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) {
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) {
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) {
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) {
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) {
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();
while (cur != null) {
builder.append(cur + "->");
cur = cur.getNext();
}
builder.append("NULL");
return builder.toString();
}
}

public class ListMain {
public static void main(String[] args) {
for (int i = 0;i < 5;i++) {
}

}
}

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

removeLast()                         O(1)

removeFirst()                         O(1)

remove(index)                       O(n/2) = O(n)

set(index,value)                    O(n/2) = O(n)

get(index)                              O(n/2) = O(n)

contains(value)                     O(n)

• 二分搜索树的封装

public interface Tree<T> {
int getSize();
boolean isEmpty();
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
}

private Node add(Node node,T value) {
//递归终止条件
if (node == null) {
size++;
return new Node(value);
}
//递归
if (value.compareTo(node.getElement()) < 0) {
}else if (value.compareTo(node.getElement()) > 0) {
}
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};
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++) {
}
Array<Integer> numsMin = new DefaultArray<>();
while (!bst.isEmpty()) {
}
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++) {
}
Array<Integer> numsMax = new DefaultArray<>();
while (!bst.isEmpty()) {
}
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测试成功

• 二分搜索树集合的封装

public interface Set<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
}

@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();
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<>();
System.out.println("共有单词: " + words.getSize());
Set<String> set = new BSTSet<>();
Stream.of(words.getData()).filter(word -> word != null)
System.out.println("共有不同的单词: " + set.getSize());
}
}

• 链表集合的封装

public class LinkedListSet<T> implements Set<T> {
private List<T> list;

}
@Override
if (!list.contains(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<>();
System.out.println("共有单词: " + words.getSize());
Stream.of(words.getData()).filter(word -> word != null)
System.out.println("共有不同的单词: " + set.getSize());
}
}

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<>();
System.out.println("共有单词: " + words.getSize());
Stream.of(words.getData()).filter(data -> data != null)
System.out.println("共有不同单词: " + set.getSize());
}
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
public static void main(String[] args) {
Set<String> bstSet = new BSTSet<>();
double time1 = testSet(bstSet,filename);
System.out.println("BST Set: " + time1 + " s");
System.out.println();
System.out.println("LinkedList Set: " + time2 + " s");
}
}

BST Set: 0.140089974 s

contains(value)               O(n)

remove(value)                 O(n)

contains(value)               O(h)

remove(value)                 O(h)

1层的节点数为                         2

2层的节点数为                        4

3层的节点数为                        8

4层的节点数为                        16

h-1层的节点数为                    2^(h-1)

contains(value)               O(log n)

remove(value)                 O(log n)

log n                           n

n = 16                     4                               16               相差4倍

n = 1024                10                              1024           相差100倍

n = 100万              20                              100万          相差5万倍

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']);
}
});
return set.size();
}
}

• 链表映射封装

public interface Map<K,V> {
V remove(K key);
boolean contains(K key);
V get(K key);
void set(K key,V value);
int getSize();
boolean isEmpty();
}

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 int size;

size = 0;
}

@Override
public void add(K key, V value) {
Node node = getNode(key);
if (node == null) {
size++;
}else {
node.setValue(value);
}
}

@Override
public V remove(K key) {
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) {
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<>();
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 {
}
});
System.out.println("共有不同的单词: " + map.getSize());
System.out.println("pride出现的次数: " + map.get("pride"));
System.out.println("prejudice出现的次数: " + map.get("prejudice"));
}
}

pride出现的次数: 53
prejudice出现的次数: 11

• 二分搜索树映射封装

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) {
}

private Node add(Node node, K key,V value) {
//递归终止条件
if (node == null) {
size++;
return new Node(key,value);
}
//递归
if (key.compareTo(node.getKey()) < 0) {
}else if (key.compareTo(node.getKey()) > 0) {
}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<>();
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 {
}
});
System.out.println("共有不同的单词: " + map.getSize());
System.out.println("pride出现的次数: " + map.get("pride"));
System.out.println("prejudice出现的次数: " + map.get("prejudice"));
}
}

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<>();
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 {
}
});
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) {
Map<String,Integer> bstMap = new BSTMap<>();
double time1 = testMap(bstMap,filename);
System.out.println("BST Map: " + time1 + " s");

System.out.println("LinkedList Map: " + time2 + " s");
}
}

pride出现的次数: 53
prejudice出现的次数: 11
BST Map: 0.178329962 s

pride出现的次数: 53
prejudice出现的次数: 11

remove(key)                          O(n)

contains(key)                        O(n)

get(key)                                 O(n)

set(key,value)                        O(n)

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) 最差

class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new TreeSet<>();
for (int num : nums1) {
}
List<Integer> list = new ArrayList<>();
for (int num : nums2) {
if (set.contains(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;
}
}

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)) {
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;
}
}

• 最大堆封装

parent(i) = (i - 1) / 2

left child = 2 * i + 1

right child = 2 * i + 2

public interface Heap<T> {
int getSize();
boolean isEmpty();

/**
* 取出最大元素(最大堆)或最小元素(最小堆)
* @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
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++) {
}
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("测试最大堆完成");
}
}

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<>();
}
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");
}
}

• 优先队列封装

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) {
}

@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();
}
}

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) {
}else if (map.get(key) > pq.peek().getFreq()) {
pq.poll();
}
});
while (!pq.isEmpty()) {
}
return res;
}
}

• 线段树封装

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

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);
}
}

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];
}
}

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);
}
}

• 字典树封装

public interface Trie {
int getSize();
boolean contains(String word);
boolean isEmpty();
boolean isPrefix(String prefix);
void remove(String word);
}

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
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<>();
System.out.println("共有单词: " + words.getSize());
Trie trie = new DefaultTrie();
Stream.of(words.getData()).filter(word -> word != null)
System.out.println("共有不同的单词: " + trie.getSize());
}
}

public class TrieRemoveMain {
public static void main(String[] args) {
Trie trie = new DefaultTrie();
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}

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;
}
}

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. */
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;
}
}
}

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;
}
}

• 并查集封装

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;
}
}
}
}

isConnected(p,q)                      O(1)

unionElements(p,q)                  O(n)

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;
}
}

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

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

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

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]++;
}
}
}

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

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]++;
}
}
}

sizeTreeUnionFind : 3.952670823 s
rankTreeUnionFind : 3.968889342 s

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

• AVL树封装

AVL树是一种保持平衡的二分搜索树，使得该二分搜索树不会退化为一个链表。

1、一直向一颗树的左侧添加元素，我们可以用LL来标记

T1 < z < T2 < x < T3 < y < T4

T1 < z < T2 < x < T3 < y < T4，可见元素的顺序并没有发生改变，说明这样的一颗二分搜索树跟之前的是等价的。

2、一直向一棵树的右侧一直添加元素，我们可以用RR来标记

T4 < y < T3 < x < T1 < z < T2

T4 < y < T3 < x < T1 < z < T2,可见元素的顺序并没有发生改变，说明这样的一颗二分搜索树跟之前的是等价的。

3、向节点的左节点添加右节点，我们可以用LR标识

4、向节点的右节点添加左节点，我们可以用RL标识

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
}

private Node add(Node node,T value) {
//递归终止条件
if (node == null) {
size++;
return new Node(value);
}
//递归
if (value.compareTo(node.getElement()) < 0) {
}else if (value.compareTo(node.getElement()) > 0) {
}
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);
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) {
}

private Node add(Node node, K key, V value) {
//递归终止条件
if (node == null) {
size++;
return new Node(key,value);
}
//递归
if (key.compareTo(node.getKey()) < 0) {
}else if (key.compareTo(node.getKey()) > 0) {
}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<>();
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 {
}
});
System.out.println("共有不同的单词: " + map.getSize());
System.out.println("pride出现的次数: " + map.get("pride"));
System.out.println("prejudice出现的次数: " + map.get("prejudice"));
}
}

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<>();
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 {
}
});
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) {
Map<String,Integer> bstMap = new BSTMap<>();
double time1 = testMap(bstMap,filename);
System.out.println("BST Map: " + time1 + " s");

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");
}
}

pride出现的次数: 53
prejudice出现的次数: 11
BST Map: 0.166421303 s

pride出现的次数: 53
prejudice出现的次数: 11

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
}

@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<>();
System.out.println("共有单词: " + words.getSize());
Stream.of(words.getData()).filter(data -> data != null)
System.out.println("共有不同单词: " + set.getSize());
}
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
public static void main(String[] args) {
Set<String> bstSet = new BSTSet<>();
double time1 = testSet(bstSet,filename);
System.out.println("BST Set: " + time1 + " s");
System.out.println();
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");
}
}

BST Set: 0.153552536 s

AVLTree Set: 0.057089254 s

• 红黑树封装

1. 每个节点或者是红色，或者是黑色的
2. 根节点是黑色的
3. 每一个叶子结点(最后的空节点)是黑色的
4. 如果一个节点是红色的，那么他的孩子节点都是黑色的
5. 从任意一个节点到叶子节点，经过的黑色节点是一样的

2-3树

2-3树维护绝对平衡2-3树在添加新节点的时候永远不会添加到一个空节点，我们依次添加42-37-12-18-6-11-5的过程依次如下

42为起始二节点的根节点，添加37会放入到42的同节点的左边产生节点的融合，产生一个三节点。

1、插入二节点

2、插入三节点(根节点)

3、插入三节点（叶节点，且父节点为二节点）

4、插入三节点(叶节点，且父节点为三节点)

2-3树删除最小元素

2-3接口

public interface BTree<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
*/
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
}

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 {
//如果是一个二节点则直接在节点中添加元素
}
}

/**
* 根据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) {
//创建一个节点右值的新节点
//取出节点的左值做为中间元素，此时节点没有任何值
mid = node.remove();
//节点放入新元素value
//如果元素比节点左值大，比右值小
}else if (value.compareTo(node.getData(1)) < 0) {
//创建一个节点右值的新节点，此时节点还剩下左值
//将新增元素做为中间元素
mid = value;
//如果元素比节点右值大
}else {
//取出节点右值做为中间元素，此时节点还剩下左值
mid = node.remove();
//创建一个新增元素的新节点
}
if (node == root) {
root = midNode;
}
//中间节点添加中间元素
//中间节点连接左子节点
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);

itemData = parent.remove();
//父节点连接中间节点为左子节点
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.connectChild(0,node.disconnectChild(1));
//将父节点分裂出的右子节点做为新节点的中子节点
newNode.connectChild(1,temp2);
//创建一个父节点左值的临时节点(此时父节点中无值)
//将父节点分裂出的左子节点做为临时节点的左子节点
tempNode.connectChild(0,temp1);
//将中间节点分裂出的左子节点做为临时节点的中子节点
tempNode.connectChild(1,node.disconnectChild(0));
//将中间节点的唯一值移除并添加到父节点
//将临时节点做为父节点的左子节点
parent.connectChild(0,tempNode);
//将新节点做为父节点的中子节点
parent.connectChild(1,newNode);
//如果中间节点元素比父节点的右值大
//这种情况应该是从父节点的右子节点进来的中间节点
}else {
//分裂父节点的左子节点
temp1 = parent.disconnectChild(0);
//分裂父节点的中子节点
temp2 = parent.disconnectChild(1);
//取出父节点的右值
itemData = parent.remove();
//创建一个父节点左值的新节点(此时父节点无值)
//将分裂的左子节点做为新节点的左子节点
newNode.connectChild(0,temp1);
//将分裂的中子节点做为新节点的中子节点
newNode.connectChild(1,temp2);
//去除父节点的右子节点(此时右子节点会被垃圾回收)
parent.disconnectChild(2);
//将父节点的原右值添加回父节点做为唯一值
//此时父节点为一个二节点
//将新节点做为父节点的左子节点
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));
}
//父节点添加中间节点元素(此时父节点为一个三节点)
}
}

@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);
}
}

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);
System.out.println(bTree.contains(18));
System.out.println(bTree.contains(11));
System.out.println(bTree.contains(32));
}
}

true
true
false

1.如果根节点不是叶子节点那么至少有两个子树。

2.所有叶子节点都位于同一层。

3.节点包含：关键字数组，指向孩子节点的指针数组，关键字数量。

B+树：由于B树进行遍历的时候效率太低，而对于数据库和文件系统来说会经常进行范围查询，所以产生了B+树。

B+树可以看作是信息都是在叶子节点上，其他非叶子节点都是索引，目的是找到叶子节点，每个非叶子节点都保存叶子节点最小值及最小值所在叶子节点的索引，并且叶子节点之间有指针指向。

(图片来源于网络)

1.功能上说，B+遍历，范围查询效率高。

2.结构上说：B+信息都保存在叶子节点上，其他节点保存最小值索引，并且关键字对应的地址都在叶子节点上，而B树中非叶子节点也保存关键字对应的地址。

B树：

关键字数组，关键字对应的地址数组  子节点的指针数组，关键字的数量（子节点的最小数量是阶数的二分之一）

B+树：

关键字数组，关键字数量，子节点的指针数组。（每个节点关键字数量和子节点数量相同，并且每个关键字都是对应一个子节点关键字的最小值）

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树要好。

42为其实红黑树的根节点，所以是一个黑色的节点，添加37会根据二分搜索树的性质，添加到42的左节点，再根据红黑树的性质，变成红色的节点。

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
root.setColor(BLACK);
}

private Node add(Node node, T value) {
//递归终止条件
if (node == null) {
size++;
return new Node(value);
}
//递归
if (value.compareTo(node.getElement()) < 0) {
}else if (value.compareTo(node.getElement()) > 0) {
}
//维护红黑树
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) {
}

private Node add(Node node, K key,V value) {
//递归终止条件
if (node == null) {
size++;
return new Node(key,value);
}
//递归
if (key.compareTo(node.getKey()) < 0) {
}else if (key.compareTo(node.getKey()) > 0) {
}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<>();
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 {
}
});
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) {
Map<String,Integer> bstMap = new BSTMap<>();
double time1 = testMap(bstMap,filename);
System.out.println("BST Map: " + time1 + " s");

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");
}
}

pride出现的次数: 53
prejudice出现的次数: 11
BST Map: 0.171121365 s

pride出现的次数: 53
prejudice出现的次数: 11

pride出现的次数: 53
prejudice出现的次数: 11
AVLTree Map: 0.070547497 s

pride出现的次数: 53
prejudice出现的次数: 11
RedBlackTree Map: 0.061147762 s

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;
}
}

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;
}
}

• 哈希表封装

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

code = c * B^3 + o * B^2 + d * B^1 + e * B^0

= ((((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;
}

1. 一致性: 如果a == b,则hash(a) == hash(b)
2. 高效性: 计算高效简便
3. 均匀性: 哈希值均匀分布

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

@AllArgsConstructor
public class Student {
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 (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

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

42
-42
219937201
3059181
94107933
94107933
true

Math.abs(hashCode(k1)) % M

int a = 5; //原码 0000 0000 0000 0000 0000 0000 0000 0101

int b = -3; //原码 1000 0000 0000 0000 0000 0000 0000 0011

(hashCode(k1) & 0x7fffffff) % M

public interface Hash<T> {
int getSize();
void remove(T t);
boolean contains(T t);
}

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
Set<T> set = hashtable[hash(value)];
if (!set.contains(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];
}
this.hashtable = newHashTable;
}
}
• Hash映射封装

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<>();
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 {
}
});
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) {
Map<String,Integer> bstMap = new BSTMap<>();
double time1 = testMap(bstMap,filename);
System.out.println("BST Map: " + time1 + " s");

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");
}
}

pride出现的次数: 53
prejudice出现的次数: 11
BST Map: 0.168990167 s

pride出现的次数: 53
prejudice出现的次数: 11

pride出现的次数: 53
prejudice出现的次数: 11
AVLTree Map: 0.067501294 s

pride出现的次数: 53
prejudice出现的次数: 11
RedBlackTree Map: 0.058438515 s

pride出现的次数: 53
prejudice出现的次数: 11
Hash Map: 0.039921075 s

0
0 收藏

0 评论
0 收藏
0