Skip to content

Commit f76550a

Browse files
dunwudunwu
committed
docs: 更新文档
1 parent fa916ae commit f76550a

File tree

8 files changed

+201
-43
lines changed

8 files changed

+201
-43
lines changed

‎README.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -31,7 +31,7 @@
3131
- [线性表的排序](docs/线性表的排序.md)
3232
- [跳表](docs/跳表.md)
3333
- [散列表](docs/散列表.md)
34-
- [树](docs/tree.md)
34+
- [树和二叉树](docs/树和二叉树.md)
3535
- [图](docs/graph.md)
3636
- [堆](docs/heap.md)
3737
- [字典树](docs/trie.md)

‎assets/算法.xmind‎

56 KB
Binary file not shown.

‎assets/线性结构.eddx‎

192 Bytes
Binary file not shown.

‎docs/README.md‎

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
> - 🔁 项目同步维护：[Github](https://github.com/dunwu/algorithm-tutorial/) | [Gitee](https://gitee.com/turnon/algorithm-tutorial/)
1010
> - 📖 电子书阅读：[Github Pages](https://dunwu.github.io/algorithm-tutorial/) | [Gitee Pages](http://turnon.gitee.io/algorithm-tutorial/)
1111
12-
## 内容
12+
## 📖 内容
1313

1414
![img](https://raw.githubusercontent.com/dunwu/images/dev/snap/20200702071922.png)
1515

@@ -18,14 +18,15 @@
1818
- [线性表的查找](线性表的查找.md)
1919
- [栈和队列](栈和队列.md)
2020
- [线性表的排序](线性表的排序.md)
21+
- [跳表](跳表.md)
2122
- [散列表](散列表.md)
22-
- [树](tree.md)
23+
- [树和二叉树](树和二叉树.md)
2324
- [图](graph.md)
2425
- [堆](heap.md)
2526
- [字典树](trie.md)
2627
- [算法代码模板](algorithm-template.md)
2728

28-
## 刷题
29+
## 💻 刷题
2930

3031
### 数组
3132

‎docs/sidebar.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
- [线性表的排序](线性表的排序.md)
88
- 非线性结构
99
- [散列表](散列表.md)
10-
- [树](tree.md)
10+
- [树](算法练习-树.md)
1111
- [图](graph.md)
1212
- [堆](heap.md)
1313
- [字典树](trie.md)

docs/tree.md renamed to docs/树和二叉树.md

Lines changed: 45 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,8 @@
1-
# 数据结构 - 树
1+
# 树和二叉树
22

3-
## 一、树的简介
3+
## 树
4+
5+
### 什么是树
46

57
在计算机科学中，**树**（英语：tree）是一种[抽象数据类型](https://zh.wikipedia.org/wiki/抽象資料型別)（ADT）或是实现这种抽象数据类型的[数据结构](https://zh.wikipedia.org/wiki/資料結構)，用来模拟具[有树状结构](https://zh.wikipedia.org/wiki/樹狀結構)性质的数据集合。它是由 n（n>0）个有限节点组成一个具有层次关系的[集合](https://zh.wikipedia.org/wiki/集合)。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
68

@@ -50,76 +52,81 @@
5052
- [霍夫曼树](https://zh.wikipedia.org/wiki/霍夫曼树)：[带权路径](https://zh.wikipedia.org/w/index.php?title=带权路径&action=edit&redlink=1)最短的二叉树称为哈夫曼树或最优二叉树；
5153
- [B 树](https://zh.wikipedia.org/wiki/B树)：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个子树。
5254

53-
### 二叉树
55+
## 二叉树
5456

55-
二叉树是 N 个节点的有限集合，它或者是空树，或者是由一个根节点及两棵不想交的且分别称为左右子树的二叉树所组成。
57+
二叉树（Binary Tree）是 N 个节点的有限集合，它或者是空树，或者是由一个根节点及两棵不想交的且分别称为左右子树的二叉树所组成。
5658

57-
#### 二叉树的性质
59+
### 二叉树的性质
5860

5961
1. 二叉树第 i 层上的结点数目最多为 **2<sup>i-1</sup>** (i≥1)。
6062
2. 深度为 k 的二叉树至多有 **2<sup>k</sup>-1** 个结点(k≥1)。
6163
3. 包含 n 个结点的二叉树的高度至少为 **log<sub>2</sub>(n+1)**。
6264
4. 在任意一棵二叉树中，若终端结点的个数为 n0，度为 2 的结点数为 n2，则 n0=n2+1。
6365

64-
#### 满二叉树
66+
### 满二叉树
6567

6668
定义：高度为 h，并且由 **2<sup>h</sup>–1** 个结点的二叉树，被称为满二叉树。
6769

6870
![img](https://raw.githubusercontent.com/dunwu/images/dev/cs/data-structure/tree/满二叉树.png)
6971

70-
#### 完全二叉树
72+
### 完全二叉树
7173

7274
定义：一棵二叉树中，只有最下面两层结点的度可以小于 2，并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树。
7375

7476
特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。
7577

7678
![img](https://raw.githubusercontent.com/dunwu/images/dev/cs/data-structure/tree/完全二叉树.png)
7779

78-
## 二、算法要点
80+
## 二叉查找树
81+
82+
二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。顾名思义，二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。
83+
84+
**二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。**
85+
86+
![](https://raw.githubusercontent.com/dunwu/images/dev/snap/20220310172814.jpg)
87+
88+
### 二叉查找树的查找
89+
90+
首先，我们看如何在二叉查找树中查找一个节点。我们先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。
91+
92+
![](https://raw.githubusercontent.com/dunwu/images/dev/snap/20220310172913.jpg)
93+
94+
### 二叉查找树的插入
95+
96+
如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。
97+
98+
![](https://raw.githubusercontent.com/dunwu/images/dev/snap/20220310172949.jpg)
99+
100+
### 二叉查找树的删除
79101

80-
## 三、练习
102+
第一种情况是，如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为 null。比如图中的删除节点 55。
81103

82-
### 二叉树经典题
104+
第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如图中的删除节点 13。
83105

84-
#### 深度优先搜索（DFS）
106+
第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 18。
85107

86-
在这个策略中，我们采用 深度 作为优先级，以便从跟开始一直到达某个确定的叶子，然后再返回到达另一个分支。深度优先搜索策略又可以根据根节点、左孩子和右孩子的相对顺序被细分为**先序遍历**，**中序遍历**和**后序遍历**。
108+
![](https://raw.githubusercontent.com/dunwu/images/dev/snap/20220310173049.jpg)
87109

88-
- [二叉树的前序遍历](https://leetcode-cn.com/problems/binary-tree-preorder-traversal)
89-
- [二叉树的中序遍历](https://leetcode-cn.com/problems/binary-tree-inorder-traversal)
90-
- [二叉树的后序遍历](https://leetcode-cn.com/problems/binary-tree-postorder-traversal)
110+
### 二叉查找树的时间复杂度
91111

92-
#### 宽度优先搜索（BFS）
112+
不管操作是插入、删除还是查找，**时间复杂度其实都跟树的高度成正比，也就是 O(logn)**。
93113

94-
我们按照高度顺序一层一层的访问整棵树，高层次的节点将会比低层次的节点先被访问到。
114+
二叉查找树的形态各式各样。比如这个图中，对于同一组数据，我们构造了三种二叉查找树。它们的查找、插入、删除操作的执行效率都是不一样的。图中第一种二叉查找树，根节点的左右子树极度不平衡，已经退化成了链表，所以查找的时间复杂度就变成了 O(n)。
95115

96-
- [二叉树的层序遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal)
116+
![](https://raw.githubusercontent.com/dunwu/images/dev/snap/20220310173253.jpg)
97117

98-
#### 二叉树和递归
118+
### 为什么需要二叉查找树
99119

100-
- [二叉树的最大深度](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree)
101-
- [对称二叉树](https://leetcode-cn.com/problems/symmetric-tree)
102-
- [路径总和](https://leetcode-cn.com/problems/path-sum)
120+
第一，散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。
103121

104-
#### 其他
122+
第二，散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。
105123

106-
- [ ] [maximum-depth-of-binary-tree](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/)
107-
- [ ] [balanced-binary-tree](https://leetcode-cn.com/problems/balanced-binary-tree/)
108-
- [ ] [binary-tree-maximum-path-sum](https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/)
109-
- [ ] [lowest-common-ancestor-of-a-binary-tree](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)
110-
- [ ] [binary-tree-level-order-traversal](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)
111-
- [ ] [binary-tree-level-order-traversal-ii](https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/)
112-
- [ ] [binary-tree-zigzag-level-order-traversal](https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/)
113-
- [ ] [validate-binary-search-tree](https://leetcode-cn.com/problems/validate-binary-search-tree/)
114-
- [ ] [insert-into-a-binary-search-tree](https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)
124+
第三，笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。
115125

116-
### 二叉搜索树经典题
126+
第四，散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。
117127

118-
- [ ] [validate-binary-search-tree](https://leetcode-cn.com/problems/validate-binary-search-tree/)
119-
- [ ] [insert-into-a-binary-search-tree](https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)
120-
- [ ] [delete-node-in-a-bst](https://leetcode-cn.com/problems/delete-node-in-a-bst/)
121-
- [ ] [balanced-binary-tree](https://leetcode-cn.com/problems/balanced-binary-tree/)
128+
最后，为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。
122129

123130
## 参考资料
124131

125-
- [https://zh.wikipedia.org/wiki/树\_(数据结构)](<https://zh.wikipedia.org/wiki/树_(数据结构)>)
132+
- [数据结构与算法之美](https://time.geekbang.org/column/intro/100017301)

‎docs/算法练习-树.md‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
# 数据结构 - 树
2+
3+
## 二叉树经典题
4+
5+
### 深度优先搜索（DFS）
6+
7+
在这个策略中，我们采用 深度 作为优先级，以便从跟开始一直到达某个确定的叶子，然后再返回到达另一个分支。深度优先搜索策略又可以根据根节点、左孩子和右孩子的相对顺序被细分为**先序遍历**，**中序遍历**和**后序遍历**。
8+
9+
- [二叉树的前序遍历](https://leetcode-cn.com/problems/binary-tree-preorder-traversal)
10+
- [二叉树的中序遍历](https://leetcode-cn.com/problems/binary-tree-inorder-traversal)
11+
- [二叉树的后序遍历](https://leetcode-cn.com/problems/binary-tree-postorder-traversal)
12+
13+
### 宽度优先搜索（BFS）
14+
15+
我们按照高度顺序一层一层的访问整棵树，高层次的节点将会比低层次的节点先被访问到。
16+
17+
- [二叉树的层序遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal)
18+
19+
### 二叉树和递归
20+
21+
- [二叉树的最大深度](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree)
22+
- [对称二叉树](https://leetcode-cn.com/problems/symmetric-tree)
23+
- [路径总和](https://leetcode-cn.com/problems/path-sum)
24+
25+
### 其他
26+
27+
- [ ] [maximum-depth-of-binary-tree](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/)
28+
- [ ] [balanced-binary-tree](https://leetcode-cn.com/problems/balanced-binary-tree/)
29+
- [ ] [binary-tree-maximum-path-sum](https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/)
30+
- [ ] [lowest-common-ancestor-of-a-binary-tree](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)
31+
- [ ] [binary-tree-level-order-traversal](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)
32+
- [ ] [binary-tree-level-order-traversal-ii](https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/)
33+
- [ ] [binary-tree-zigzag-level-order-traversal](https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/)
34+
- [ ] [validate-binary-search-tree](https://leetcode-cn.com/problems/validate-binary-search-tree/)
35+
- [ ] [insert-into-a-binary-search-tree](https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)
36+
37+
## 二叉搜索树经典题
38+
39+
- [ ] [validate-binary-search-tree](https://leetcode-cn.com/problems/validate-binary-search-tree/)
40+
- [ ] [insert-into-a-binary-search-tree](https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)
41+
- [ ] [delete-node-in-a-bst](https://leetcode-cn.com/problems/delete-node-in-a-bst/)
42+
- [ ] [balanced-binary-tree](https://leetcode-cn.com/problems/balanced-binary-tree/)

0 commit comments

Comments
 (0)