39-Day3.md

day-3

快速排序

• 选枢轴量，交换，左右各自递归
• o(nlogn)

桶排序

数据结构 BST

数组和链表

二叉搜索树

删除 直接后继替代

B树

• 以2,4B树为例

• 最多m个孩子，最多m-1个元素，最少【m-1/2】个，向下取整

• 深度相同

  插入

  先下滤到底部插入

  如果个数超了则拆分，上滤

红黑树

根节点为黑

外部NIL节点为黑

红节点的孩子和父亲均为黑节点

提升变换：把红节点向上提，可以划为2,4B树

插入：

​ 找到相应的位置并染红

双红修正

​ 即父亲是红色时需要修正，此时爷爷必然是黑色

​ 叔叔不是红色 g,p,v中的中间节点上提，换色

​ 叔叔也是红色 父亲和叔叔涂黑，爷爷涂红，上滤

​