打卡时间：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
网友评论