栈
堆
树
前序遍历
中序遍历
二叉树
搜索二叉树（二叉查找树）
二叉查找树（BST：Binary Search Tree）是一种特殊的二叉树，它改善了二叉树节点查找的效率。二叉查找树有以下性质：
对于任意一个节点 n，
- 其左子树（left subtree）下的每个后代节点（descendant node）的值都小于节点 n 的值；
- 其右子树（right subtree）下的每个后代节点的值都大于节点 n 的值。
红黑树
树的遍历
四种主要的遍历思想为：
-
前序遍历：根结点 —> 左子树 —> 右子树
-
中序遍历：左子树—> 根结点 —> 右子树
-
后序遍历：左子树 —> 右子树 —> 根结点
-
层次遍历：只需按层次遍历即可
二分查找
https://mp.weixin.qq.com/s/0Ni9i78uRWjZj4hrhTH03g
二分思想
本质上是折半查找思想，每一轮查找的范围是上一轮的一半，每次查找比较中间元素的值和目标值的大小，比较结论决定取哪一半边作为下一轮的查找范围。当查找范围缩小到空时停止。
局限性：有序、数组
- 有序性：保证每次取半的意义
- 数组：数组寻址的复杂度是 O(1)
如果是用链表存储的一串数，二分查找是无意义的。链表的寻址是 O(n)。
跳表
为什么需要跳表
- 链表查询太慢 → O(n)
- 什么算法查询快？二分！→ O(logn)
- 怎么把二分思想在链表中实践？→ 跳表的诞生 → O(?)
二分查找
改造链表
- 有序，不在改造范围内
- 加快寻址速度
-
空间换时间 → 上索引
- 构建索引层 → 每 2 个节点提取 1 个到上一级，逐层构建
时间复杂度
- 跳表高度：n, n/2, n/4, n/8, …, n/(2^k) → log2n
- 每层遍历 m 个节点 → O(m*logn)
- 每层索引最多只需要遍历 3 个节点 → O(logn)
空间复杂度
- n/2 + n/4 + n/8 + … + 8 + 4 + 2 → n-2 → O(n)
- 实际操作中，链表中存储的对象元素很大，索引节点只会存- - 关键信息（比如 id）和指针，索引占用的额外空间可以忽略不计
跳表 索引的更新实现（随机 + 概率）
随机建立索引
- 原链表，随机抽 n/2 个元素建立一级索引
- 一级索引，随机抽 n/4 个元素建立二级索引
- 以此类推，元素越多，索引分布越均匀
概率（随机）更新索引
- 设计一个特别的函数，按照概率返回 [1, MAX_LEVEL] 之间的整数
- 1/2 的概率返回 1，不需要更新索引，直接在在原链表中插入元素
- 1/4 的概率返回 2，需要为新元素建立一级索引
- 以此类推，无论插入多少个元素，各级索引的节点数依然是 n/2, n/4, ….
Redis 源码
跳表相关问题
加分点
- 索引层的更新，看过 Redis 跳表的源码，一些侃侃而谈
- 跳表和红黑树的对比
- 跳表能按照指定的区间查数据
- 红黑树实现起来很复杂，跳表实现起来不容易出错（不给自己挖坑）
- 高效查找、动态插入删除，都能做到 O(logn)
- 共同点
- 区别
延伸点
- 对比红黑树
- 对比散列表
- Redis 的其他特性，除了跳表，我还知道 xxxx
