数据结构的栈队列和链表

栈可以使用动态数组实现

1
2


队列

循环队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
public class LoopQueue<E> implements Queue<E> {

private E[] data;
private int front, tail;
private int size;

public LoopQueue(int capacity){
data = (E[])new Object[capacity + 1];
front = 0;
tail = 0;
size = 0;
}



public LoopQueue(){
this(10);
}

public int getCapacity(){
return data.length - 1;
}

@Override
public boolean isEmpty(){
return front == tail;
}


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


@Override
public void enqueue(E e) {
if ((tail+1)%data.length == front){
resize(getCapacity()*2);
}

data[tail]=e;
size++;
tail=(tail+1)%data.length;
}



@Override
public E dequeue() {

if (isEmpty())
throw new IllegalArgumentException("Cannot dequeue from empty");

E ret = data[front];
data[front] = null;
front=(front+1) %data.length;
size--;

if(size == getCapacity() / 4 && getCapacity() / 2 != 0)
resize(getCapacity() / 2);
return ret;
}

@Override
public E getFront() {
return data[front];
}

private void resize(int newCapacity){
E[] newData = (E[]) new Object[newCapacity+1];
for (int i = 0; i < size; i++) {
newData[i] = data[(i+front)%data.length];
}

data=newData;
front=0;
tail=size;
}

@Override
public String toString(){

StringBuilder res = new StringBuilder();
res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity()));
res.append("front [");
for(int i = front ; i != tail ; i = (i + 1) % data.length){
res.append(data[i]);
if((i + 1) % data.length != tail)
res.append(", ");
}
res.append("] tail");
return res.toString();
}

}

但以下整个就不是平衡二叉树了
因为8的左子树高度为3 右子树 高度为1

23树

在 23树 中 我们添加节点 永远不会添加到一个空节点中
只会与最后找到的叶子节点 做融合

第一步:
42 为 根节点 37需要插入 37比42小 需要插入左子树中 左子树为空 那么就会与 42 融合

第二步:
12 要插入 37 42 融合的节点 由于12比37小 37的左子树为空 那么就会再进行融合

第三步:
由于23树 最多只能有3个子节点 节点中 最多有两个元素 那么就会使子树进行分裂 分裂后刚好平衡

第四步:
18想要插入树中 18比37小 于是找到37的右子树 12 12的右子树为空 那么他不会插入空节点 就会与12融合

第五步:
6想要插入树种 就会形成这样

第六步:
由于 23树每个节点只能有1或2个元素 会进行拆解

第七步:
由于拆解后 这个23树 不是一个绝对平衡树了 就会将12 向上融合

第八步:
又有11 这个元素插入 11小于12 有比12的左子树6大 就和6融合

第九步:
插入5元素

然后拆分

节点6 融合入父亲节点

再拆分

一个完整的序列

红黑树和23树的等价关系

红黑树和23树之间的等价关系

我们将这个并列关系的边绘制为红色

但由于不方便表示边 的种类 由于子节点只能有一个父节点 我们可以使用子节点来标识这个边
我们将子节点标识为红色

这种红色节点的意思就是
和 他父亲节点 一起表示 23树中 有两个元素的 3节点
根据这种定义 所有的红节点 都是左斜的

23 树 与 红黑树

算法3中 红黑树的5条性质

  1. 每个节点 要么是红色 要么是黑色
  2. 根节点是黑丝的
  3. 每个叶子节点都是黑色的
  4. 如果一个节点是红色的 那么它的孩子节点 一定是黑色的
  5. 从任意节点到叶子节点 经历的黑色节点个数是一样的

二分搜索树的代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
public class BinarySearchTree<E extends Comparable> {

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

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


private int size;
private Node root;

public BinarySearchTree() {
this.root = null;
this.size = 0;
}

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

//向二分搜索树中添加新元素
public void add(E e) {
// root = add(root, e);

if (root == null) {
size++;
root = new Node(e);
return;
}
nodeAdd2(root,e);
}

// 向node为根的节点添加新元素
public Node add(Node node, E e) {

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



// 向node为根的节点添加新元素
public void nodeAdd2(Node node, E e) {

if (e.equals(node.e)) {
return;
} else if (e.compareTo(node.e) < 0 && node.left == null) {
node.left = new Node(e);
size++;
} else if (e.compareTo(node.e) > 0 && node.right == null) {
node.right = new Node(e);
size++;
}

if (e.compareTo(node.e) < 0) {
nodeAdd2(node.left, e);
} else if (e.compareTo(node.e) > 0) {
nodeAdd2(node.right, e);
}
}


public boolean contains(E e) {
return contains(root, e);
}

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

public void preOrder() {
preOrder(root);
}

private void preOrder(Node node) {
if (node == null) {
return;
}
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}

@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
generateStringBuilder(root, 0, stringBuilder);
return stringBuilder.toString();
}

private void generateStringBuilder(Node node, int depth, StringBuilder resString) {
if (node == null) {
resString.append(generatedepthString(depth) + "null\n");
return;
}
resString.append(generatedepthString(depth) + node.e + "\n");

generateStringBuilder(node.left,depth+1,resString);
generateStringBuilder(node.right,depth+1,resString);
}

private String generatedepthString(int depth) {
StringBuilder deepstring = new StringBuilder();
for (int j = 0; j < depth; j++) {
deepstring.append("--");
}
return deepstring.toString();
}
}

链表

给链表添加元素

第一步 先将需要添加的元素的next 指向前面节点的next
node.next = prev.next

第二步 将pre节点的next指向指向需要添加的节点
prev.next = node

链表元素的删除

第一步
prev.next = delNode.next

第二步(可以不用)
delNode.next=null;

Linked链表时间复杂度分析