知识快速回顾（数据结构+算法）

打卡时间：2020-2-23 19:46 ～ 20:30

跳表

什么是跳表 ？

跳表是一种高效的链表结构，它通过增加多级索引的方式提高访问效率。

跳表的结构图是怎样的？

image.png

跳表的时间、空间复杂度是多少？

时间复杂度:O(logN)
空间复杂度:O(N)

跳表的问题

1.在插入/删除节点时，需要维护索引数据(定时更新)，否则，会导致跳表的检索效率下降，严重时会退化成单链表结构。
2.跳表通过随机函数的维护数据的平衡，通过随机函数来决定数据插入到第几层索引中。

树

树的关键概念

1.高度：节点-->叶子的最长路径。 （从下往上）
2.深度：根节点-->子节点经过的边的数量。（从上往下）
3.层：深度+1
插图

image.png

二叉树、完全二叉树、满二叉树

1.二叉树：每个节点最多有两个分支的数。
2.满二叉树：所有的节点都有左右节点的数
3.完全二叉树
a.叶子节点都在最后两层
b.最后一层节点都在左边
c.除最后一层，其他节点都是满的

二叉树的存储结构

1.链表结构
value、left节点 、right节点
特点：
1.检索的性能比较低
2.耗内存

插图

image.png

2.数组结构
1.从数组下标1开始存储。
2.左节点：2i , 右节点: 2i+1
特点：
1.当二叉树为完成二叉树时，数组适用的内存是最少的。
2.检索的性能很快，根据2i或者2i+1就能检索到左右节点。
插图

image.png

二叉树的遍历

前序遍历
检索顺序:自己->左节点->右节点 (⬇️⬅️➡️)
递推公式
preOrder(r) = print r -> preOrder(left) -> preOrder(right)
插图

image.png

中序遍历
检索顺序:左节点->自己->右节点 (⬅️⬇️➡️)
递推公式
inOrder(r) = inOrder(left)-> print r -> inOrder(right)
插图

image.png

后序遍历
检索顺序:左节点->右节点->自身（⬅️➡️⬇️）
递推公式
postOrder(r) =postOrder(left) -> postOrder(right) -> print r
插图

image.png