数据结构（红黑树、B/B+树、跳表、位图等）

数据结构

---

查找算法

• 二叉树基础
• 最大堆和最小堆
• 二分查找
• 二叉排序树
• 平衡二叉树
• 多路查找树2-3树
• 红黑树
• B/B+树
• 哈希表
• 跳表
• 位图

数组和链表

• 数组和链表的区别

赫夫曼编码

• 赫夫曼树
• 赫夫曼编码

二叉树基础

• 二叉树定义
  • n个结点的有限集合，该集合为空集，或者一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成
• 满二叉树
  • 一棵二叉树中所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上
• 完全二叉树
  • 一棵有n个结点的二叉树按层序编号，编号为i的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同
• 二叉树的性质
  • 非空二叉树第 i 层最多 2^(i-1) 个结点 （i >= 1）
  • 深度为 k 的二叉树最多 2^k - 1 个结点 （k >= 1）
  • 度为 0 的结点数为 n0，度为 2 的结点数为 n2，则 n0 = n2 + 1
  • 有 n 个结点的完全二叉树深度 k = ⌊ log2(n) ⌋ + 1
  • 对于含 n 个结点的完全二叉树中编号为 i （1 <= i <= n） 的结点
    • 若 i = 1，为根，否则双亲为 ⌊ i / 2 ⌋
    • 若 2i > n，则 i 结点没有左孩子，否则孩子编号为 2i
    • 若 2i + 1 > n，则 i 结点没有右孩子，否则孩子编号为 2i + 1

最大堆和最小堆

堆是完全二叉树，根据结点和左右孩子的大小关系，分为最大堆和最小堆

• 最大堆
  • 每个结点的值都大于或等于其左右孩子结点的值
• 最小堆
  • 每个结点的值都小于或等于其左右孩子结点的值

二分查找

二分查找适用于有序数组

• 查找时间复杂度O(logn)

二叉排序树

• 查找时间复杂度O(logn)，最坏情况变成右斜树O(n)

二叉排序树，又称二叉搜索树，若二叉排序树不为空，则具有下列性质

• 若左子树不为空，则左子树上所有结点的值小于根节点的值
• 若右子树不为空，则右子树上所有结点的值大于根节点的值

平衡二叉树

• 查找时间复杂度O(logn)，插入和删除时间复杂度O(logn)

平衡二叉树是二叉排序树，每一个结点左右子树高度之差的绝对值不超过1

多路查找树2 3树

多路查找树，每一个结点的孩子数可以多于两个，每一个节点处可以存储多个元素

2-3树

每一个结点都具有两个孩子(2结点)或三个孩子(3结点)
一个2结点包含一个元素和两个孩子
一个3结点包含一小一大两个元素和三个孩子