写在开头
之前说好要整理出一篇关于如何使用 “GitHub Pages + hexo” 创建博客目前没有一点进展，单纯是因为懒。
到六月份就得忙起来了，所以就更没有时间了
于是便安排在暑假里吧。由于在自学的过程中，认识到了数据结构。我对此起了些许兴趣，为了让自己对数据结构有所记忆，所以就想先整理出这篇“初识数据结构”的博客。
接触数据结构
在我开始学习算法的时候，教材首先就给我讲了数据结构的基础。
程序设计 = 数据结构 + 算法。
这充分地说明数据结构与算法的关联性。
我对它的基本理解是：数据结构是计算机存储数据的方式，
数据以怎样的组织，怎样的存储格式，被计算机所管理。
数据结构分类
数据结构的分类一般有两种维度，一种是根据数据结构的原理从它们的逻辑结构来区分，一种是从数据结构存储时的物理结构来区分。
逻辑结构
是指数据与数据之间的关系，通常可以分为线性结构和非线性结构。
线性结构:
数据元素之间存在着一对一的关系。
例：顺序表，栈，队列
非线性结构:
数据元素之间存在着一对多或者多对多的关系。
例：树形结构，图形结构
物理结构
是指数据在计算机是以何种方式存储的，也就是所谓的映像。针对数据在存储器中的存储方法而言的，通常可以分为顺序存储和链式存储。
顺序存储结构
顺序存储的数据是在一段连续的空间中，靠相对位置来表示元素之间的相互关系，像在一个小教室上课的同班同学靠前后座关系就能建立联系
例：数组
链序存储结构
链式存储的数据内存地址不一定是连续的，每一个节点上都有一个指针存储域，靠指针来建立元素之间的相互关系，像几个班级的同学同时上公选课时分散在一个大教室里，同一个班级的同学之间需要靠学号来建立联系。
例：链表
八大数据结构
Array（数组）
Stack（栈）
Linked List（链表）
Graph（图）
Hash（散列表）
Queue（队列）
Tree（树）
Heap（堆）
Java中常用的数据结构
Java 中常用的数据结构都在 java.util 包下，都是对 Collection 和 Map 两个顶级接口的实现类。
实现该接口的几种数据类型
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
| 蓝标是```Map``` 接口和实现该接口的```SortedMap```<br>
此外实现``` Map``` 接口的还有```HashMap、TreeMap、Hashtable、SortedMap```<br>
另外还有 ```Collections、Arrays```两个工具类。
# 树形结构——红黑树
```红黑树```是一种接近平衡的二叉搜索树，它能够保证任意一个节点左右子树的高度差不会超过较低子树的高度，也就是两棵子树的高度比值不会超过 2 倍。这样我们可以使搜索的时间复杂度更接近 O (logN)。为了保证树的平衡，我们需要在添加或删除元素的时候不断的调整树的结构，使每个节点的左右子树上的节点个数尽可能相等。
<br></br>
## 红黑树的性质
> 1. 每个节点不是红色就是黑色。
> 2. 根节点永远是黑色。
> 3. 红色节点的子节点必须是黑色。
> 4. 任意一个节点到每个叶子节点的路径上都包含相同数量的黑色节点。
> 5. 每次添加新节点都默认为红色。
<br></br>
## 红黑树调整的方式
如果每次添加节点都设置为红色，当父节点已经是红色时，会违背上面的第 3 条性质，这时候我们需要按照一定的方法去调整树，调整的方式有三种：改变节点颜色、左旋和右旋。
<br></br>
## 红黑树的插入操作
插入元素会导致原本平衡的红黑树失去平衡，还会导致红黑树五大特性的不满足。因此插入后我们需要做调整，使其重新成为一个红黑树。
<br></br>
### 第一步：插入
要把元素插进红黑树的第一步就是要找到插入的位置。
> 1. 如果是空树，直接插入到跟节点。
> 2. 如果与当前节点的key值相等，则更新当前节点的value值。
> 3. 如果比当前节点的key值大，则继续寻找当前节点的右子节点。
> 4. 如果比当前节点的key值小，则继续寻找当前节点的左子节点
> 5. 如果当前节点为null（或nil节点），则插入在当前节点的父节点下。
<br></br>
### 第二步：插入后重新调整至平衡状态
以下为```JDK1.8```的HashMap中对红黑树的调整源码。
```java
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) {
x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//false条件：当前节点存在父节点
if ((xp = x.parent) == null) {
//父节点为空，当前节点是根节点，直接设置根节点为黑色后返回
x.red = false;
return x;
}
//false条件：且父节点是红色，且存在爷爷节点
else if (!xp.red || (xpp = xp.parent) == null)
return root;
if (xp == (xppl = xpp.left)) {
//false条件：且叔叔节点为空，或者是黑色；
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
//true条件：当前节点是其父节点的右子节点；
if (x == xp.right) {
// 左旋父节点
root = rotateLeft(root, x = xp);
// 爷爷节点不存在则结束，存在则将指针指向父节点
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// true条件：父节点不为空
if (xp != null) {
// 父节点变为黑色
xp.red = false;
// true条件：祖父节点不为空
if (xpp != null) {
// 祖父节点变为红色
xpp.red = true;
// 右旋祖父节点
root = rotateRight(root, xpp);
}
}
}
}
else {
//false条件：且叔叔节点为空，或者是黑色；
if (xppl != null && xppl.red) {
// 当前节点的父节点以及左叔父节点都是红色 则颜色变为黑色
xppl.red = false;
xp.red = false;
// 黑节点的父节点必须红色
xpp.red = true;
x = xpp;
}
else {
//true条件：当前节点是其父节点的左子节点；
if (x == xp.left) {
// 右旋父节点
root = rotateRight(root, x = xp);
// 指针指向父节点
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// true条件：父节点不为空
if (xp != null) {
// 父节点变为黑色
xp.red = false;
// true条件：祖父节点不为空
if (xpp != null) {
// 祖父节点变为红色
xpp.red = true;
// 右旋祖父节点
root = rotateLeft(root, xpp);
}
}
}
}
}
}
|
红黑树的删除操作
删除操作可能触发的情况分为有子节点和无子节点，没有子节点的情况非常简单，直接删除后执行自平衡即可。有子节点的时候我们要先找到替换节点，如果只有一个子节点，这个节点就是替换节点；如果有两个子节点，要找到左子树的最大节点或右子树的最小节点作为替换节点。
