堆

性质

左右孩子节点的值都小于根节点，且左右孩子都是堆的完全二叉树

最小堆构建

一个数组，从数组的最后一个元素的父亲节点（n/2）开始进行调整，以保证该父亲节点比所有的子节点都小（需要递归向下），然后对节点(n/2-1)进行调整, n(logn)

插入

插入最后一个位置，然后上浮（O(logn)）【可以发现根节点到这个新数据的父亲节点之间必为一个有序数列，现在的任务就是将新数据插入这个有序数列中】(O(logn))

删除

删除操作都是针对的根节点，方法是将最后一个数据赋值给根节点，然后进行一次下沉操作 O(logn)

堆排序

将根元素与最后一个根元素交换位置，再进行下沉操作即可

二叉搜索树

性质

左子树的值都小于根节点，右子树的值均大于根节点，且左右子树都是二叉搜索树；

查询

递归查找是否存在key。 logn

插入

原树中不存在key，插入key返回true，否则返回false。 logn

删除 logn

  1. 叶子节点：直接删除，不影响原树。
  2. 仅仅有左或右子树的节点：节点删除后，将它的左子树或右子树整个移动到删除节点的位置就可以，子承父业。
  3. 既有左又有右子树的节点：找到须要删除的节点p的直接前驱（左子树最大值）或者直接后继（右子树最小值）s，用s来替换节点p，然后再删除节点s。

AVL树

定义

一颗左右孩子的高度差不会超过1的二叉搜索树

查找

插入节点

插入新节点O(logn)–> 从新插入的节点向上搜索第一个失衡节点O(logn)–>判断失衡类型–>调整

删除

前半部分和二叉搜索树的删除过程相同，删除之后调整平衡，更新高度 O(logn)

AVL和红黑树的区别

  1. AVL平衡性更高，适用于查询频繁的情况；
  2. 红黑树插入、删除操作进行的旋转次数更少，所以适用于插入、删除频繁的情况；

红黑树

定义

  1. 根节点是黑色；
  2. 不能有连续的两个红色；
  3. 根节点到叶子节点的所有路径包含相同个数的黑色节点

插入

将新节点插入红黑树并将其标为红色–>若插入位置是根节点直接将此节点涂为黑色即可–>若其父亲节点是黑色则什么都不需要做–>若父亲节点是红色，违背了不能有连续两个红色节点的要求，所以需要根据其叔叔节点的颜色进行调整；

删除

前半部分和二叉搜索树删除过程相同；若删除的节点是红色，则不会影响；若是黑色则会影响红黑树性质，此时需要进行recolor或rotation进行调整；

B树

定义

一颗平衡m叉搜索树： 1. 根节点至少两个子女； 2. 每个中间节点都包含k-1个元素和k个孩子，其中（$\lceil m/2 \rceil \leq k\leq m$） 3. 每一个叶子节点都包含k-1个元素，其中（$\lceil m/2 \rceil \leq k\leq m$） 4. 所有的叶子节点都在同一层；（叶节点等深） 5. 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分

插入

查找B树，找到新元素应该插入的叶子节点的位置，然后按照以下步骤进行插入： 1. 如果该叶子节点所包含元素个数少于要求的最大值，则直接将新元素按照大小关系直接插入叶子节点即可 2. 如果该叶子节点已经满了，将叶子节点中的元素按照中间元素分裂为两部分，小于中间元素的做左子树，大于中间元素的做右子树，并将中间元素插入其父亲节点（若没有父亲节点，则创建一个父亲节点）。 3. 如果向父亲节点插入时发生了上述问题，则重复步骤1-3；

删除

可能引起合并、自旋

和红黑树的关系

一颗4阶b树（2-3-4树）与红黑树是等价的

B+树

定义：

  1. 有k个子树的中间节点包含有k个元素（B树是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点
  2. 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接
  3. 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

和B树的区别

  1. 父节点中的元素都包含在子节点中，所以叶子节点中包含所有的元素；
  2. 并且每个叶子节点都带有指向下一个节点的指针，形成了一个有序链表
  3. 中间节点只包含索引，不包含数据，所有的数据都在叶子节点

优点

  1. 由于不包含卫星数据，所以中间节点可以包含更多元素，树会更“矮”从而可以减少IO次数
  2. 由于所有数据都在叶子节点，所以查询性能更稳定
  3. 由于叶子节点形成一个有序链表，所以更方便进行范围查询