# 数据结构整理 顶

• 数组封装

```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 LinkedListStack,time: 3.731664658 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 LinkedListQueue,time: 0.008463007 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 LinkedListQueue,time: 3.531655449 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] LinkedListQueue,time: 3.412228277 s Heap PSYoungGen total 272896K, used 131467K [0x000000076ab00000, 0x0000000792600000, 0x00000007c0000000) eden space 262144K, 50% used [0x000000076ab00000,0x0000000772b62e80,0x000000077ab00000) from space 10752K, 0% used [0x000000077ab00000,0x000000077ab00000,0x000000077b580000) to space 185344K, 0% used [0x0000000787100000,0x0000000787100000,0x0000000792600000) ParOldGen total 605696K, used 271533K [0x00000006c0000000, 0x00000006e4f80000, 0x000000076ab00000) object space 605696K, 44% used [0x00000006c0000000,0x00000006d092b670,0x00000006e4f80000) Metaspace used 3486K, capacity 4566K, committed 4864K, reserved 1056768K class space used 376K, capacity 390K, committed 512K, reserved 1048576K

[GC (Allocation Failure) [PSYoungGen: 260301K->43511K(305664K)] 260301K->83257K(1005056K), 0.0813630 secs] [Times: user=0.99 sys=0.04, real=0.08 secs] LoopQueue,time: 0.443129398 s [GC (Allocation Failure) [PSYoungGen: 305655K->43495K(305664K)] 345401K->254481K(1005056K), 1.0359483 secs] [Times: user=12.20 sys=0.14, real=1.04 secs] LinkedListQueue,time: 1.261171544 s Heap PSYoungGen total 305664K, used 223003K [0x00000007aab00000, 0x00000007c0000000, 0x00000007c0000000) eden space 262144K, 68% used [0x00000007aab00000,0x00000007b5a4d0e8,0x00000007bab00000) from space 43520K, 99% used [0x00000007bd580000,0x00000007bfff9dc8,0x00000007c0000000) to space 43520K, 0% used [0x00000007bab00000,0x00000007bab00000,0x00000007bd580000) ParOldGen total 699392K, used 210985K [0x0000000780000000, 0x00000007aab00000, 0x00000007aab00000) object space 699392K, 30% used [0x0000000780000000,0x000000078ce0a708,0x00000007aab00000) Metaspace used 3488K, capacity 4566K, committed 4864K, reserved 1056768K class space used 376K, capacity 390K, committed 512K, reserved 1048576K

-XX:+PrintGCDetails -Xmx1G -Xms1G -XX:+UseParallelGC -XX:+UseCompressedOops -XX:SurvivorRatio=4 -XX:ParallelGCThreads=8

[GC (Allocation Failure) [PSYoungGen: 233472K->57831K(291328K)] 233472K->174728K(990720K), 0.1696696 secs] [Times: user=1.25 sys=0.09, real=0.17 secs] LoopQueue,time: 0.521021115 s [GC (Allocation Failure) [PSYoungGen: 291303K->57831K(291328K)] 408200K->279688K(990720K), 0.6708571 secs] [Times: user=5.25 sys=0.10, real=0.67 secs] LinkedListQueue,time: 0.866029237 s Heap PSYoungGen total 291328K, used 290384K [0x00000007aab00000, 0x00000007c0000000, 0x00000007c0000000) eden space 233472K, 99% used [0x00000007aab00000,0x00000007b8e1a330,0x00000007b8f00000) from space 57856K, 99% used [0x00000007bc780000,0x00000007bfff9dc8,0x00000007c0000000) to space 57856K, 0% used [0x00000007b8f00000,0x00000007b8f00000,0x00000007bc780000) ParOldGen total 699392K, used 221857K [0x0000000780000000, 0x00000007aab00000, 0x00000007aab00000) object space 699392K, 31% used [0x0000000780000000,0x000000078d8a84f8,0x00000007aab00000) Metaspace used 3488K, capacity 4566K, committed 4864K, reserved 1056768K class space used 376K, capacity 390K, committed 512K, reserved 1048576K

```输入: 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在 1->2->6->3->4->5->6->NULL中 --调用: 删除 6在 2->6->3->4->5->6->NULL中 ----调用: 删除 6在 6->3->4->5->6->NULL中 ------调用: 删除 6在 3->4->5->6->NULL中 --------调用: 删除 6在 4->5->6->NULL中 ----------调用: 删除 6在 5->6->NULL中 ------------调用: 删除 6在 6->NULL中 --------------调用: 删除 6在 null中 --------------返回:null ------------删除 6之后: null ------------返回: null ----------删除 6之后: null ----------返回: 5->NULL --------删除 6之后: 5->NULL --------返回: 4->5->NULL ------删除 6之后: 4->5->NULL ------返回: 3->4->5->NULL ----删除 6之后: 3->4->5->NULL ----返回: 3->4->5->NULL --删除 6之后: 3->4->5->NULL --返回: 2->3->4->5->NULL 删除 6之后: 2->3->4->5->NULL 返回: 1->2->3->4->5->NULL 1->2->3->4->5->NULL

• 单向链表的递归改写

```public class RecursiveLinkedList<T> implements List<T> {
@AllArgsConstructor
@Data
private class Node {
private T element;
private Node next;

public Node(T element) {
this(element,null);
}

public Node() {
this(null,null);
}

@Override
public String toString() {
return element.toString();
}
}

/**
* 链表虚拟头节点
*/
private 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 ------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");
}
}```

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

• 二分搜索树映射封装

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

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

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

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

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

0 条评论

• ### 归并排序算法 顶

合并排序算法就是把多个有序数据表合并成一个有序数据表。如果参与合并的只有两个有序表，则称为二路合并。

• ### spring cloud zuul网关的作用

zuul一般有两大作用,1是类似于Nginx的网址重定向,但zuul的重定向的一般是整个spring cloud里在Eureka注册中心的模块.

• ### 数据结构 02

在《数据结构 01》一文中，说到了数组、链表、栈以及队列这几种基本的线性结构，接下来就一起来看看剩下的内容。

• ### 洛谷P1291 [SHOI2002]百事世界杯之旅(期望DP)

题目描述 “……在2002年6月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。只要凑齐所有百事球星的名字，就可参加百事世界杯之旅的抽奖活动，获得球星背...

• ### Codeforces Round #504 A. Single Wildcard Pattern Matching(思维)

题目链接：http://codeforces.com/contest/1023/problem/A

• ### 为了程序的健壮性，我们可以使用空对象模式

在写代码的时候我们经常会遇到空指针，为了避免空指针的发生需要做一些判断。如果是复杂对象的话，还需要一层层地去判断。这个时候我就无比怀念groovy、kotlin...

• ### 首次回归，居然发这个！！！

已经有好长时间没有发文章了，也不是懒，总想做一些安全方面的积累，再进行输出，这样的产出可能更有价值。

• ### SpringMVC源码深度解析之拦截器&过滤器&视图层&异步源码分析

加入这个注解EnableWebMvc重复注入了WebMvcConfigurationSupport，会覆盖我们自定义的配置类