forked from HappySnailSunshine/JavaInterview
-
Notifications
You must be signed in to change notification settings - Fork 0
/
DataStructure.md
128 lines (61 loc) · 3.24 KB
/
DataStructure.md
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
# DataStructure
## 数据结构
>这一部分可以看王道考研数据结构
>
>可以做LeetCode上面习题
>
>牛客网剑指Offer也挺好
>
>我学的时候看的同学推荐的慕课网 玩转数据结构
>
>
>
>这一部分非常不完整，缺很多东西，后续会陆续加进来。
>
>下面的截图来自慕课网，玩转数据结构，如有侵权，请联系删除
>
>学习进度 慕课网 看到13-4结束。
## 0.绪论
<img src="../media/pictures/DataStructure.assets/1584411756451.png" alt="1584411756451" style="zoom:50%;" />
### 数据库中用到的数据结构
<img src="../media/pictures/DataStructure.assets/1584411856883.png" alt="1584411856883" style="zoom:50%;" />
### 操作系统中用到的数据结构
<img src="../media/pictures/DataStructure.assets/1584412042368.png" alt="1584412042368" style="zoom: 67%;" />
### 文件压缩用到的数据结构
<img src="../media/pictures/DataStructure.assets/1584412137312.png" alt="1584412137312" style="zoom:50%;" />
### 通讯录中的数据结构
<img src="../media/pictures/DataStructure.assets/1584412225311.png" alt="1584412225311" style="zoom: 67%;" />
### 图论算法：（深度优先遍历，广度优先遍历）
<img src="../media/pictures/DataStructure.assets/1584412312478.png" alt="1584412312478" style="zoom:50%;" />
### 课程
<img src="../media/pictures/DataStructure.assets/1584412511377.png" alt="1584412511377" style="zoom:67%;" />
## 13.红黑树
红黑树的结构图：
<img src="../media/pictures/DataStructure.assets/1586510733644.png" alt="1586510733644" style="zoom:50%;" />
红黑树的性质：
右边那本书，叫计算机程序设计艺术
<img src="../media/pictures/DataStructure.assets/1586511461928.png" alt="1586511461928" style="zoom:50%;" />
学习红黑树之前，了解一下2-3树，红黑树和2-3树是等价的。
2-3树是一颗绝对平衡的树。
红黑树中添加一个元素：类比2-3树添加元素
<img src="../media/pictures/DataStructure.assets/1586513325954.png" alt="1586513325954" style="zoom:50%;" />
右旋转：
<img src="../media/pictures/DataStructure.assets/1586513628842.png" alt="1586513628842" style="zoom:50%;" />
<img src="../media/pictures/DataStructure.assets/1586514589407.png" alt="1586514589407" style="zoom:50%;" />
2-3树和红黑树是等价的
<img src="../media/pictures/DataStructure.assets/1586514805299.png" alt="1586514805299" style="zoom:50%;" />
由上面性质5可以知道，红黑树是保持了“黑平衡”的二叉树，
严格意义上说不是平衡二叉树
红黑树时间复杂度是O（logn）
将红黑树的一个博客!很详细!
https://blog.csdn.net/Sun_TTTT/article/details/65445754
简书上面讲红黑树的：https://www.jianshu.com/p/e136ec79235c
# Interview
> 这一部分在考研408或者面试，算是最重要的一部分，尤其进大厂，对这一部分要求很高。
>
> 后续会更新内容。
我自己碰见过的有问红黑树的。