42-Day3.md

Day3-学习小结

学习内容

• 桶排序

  通常用在数据极差不大的情况，否则需要创建过多的桶；

  首先比较数据的个位（数位数大的时候逐级比较上去）

  QuickSort快排

  每次随机抽取一个支点，左小右大进行排列；

  复杂度平均期望：O(nlogn)

  最差情况下的复杂度O(n^2)

• BST（二元搜索树）

  • Every LEFT descendant of a node has key less than that node.

  • Every RIGHT descendant of a node has key larger than that node.

  根节点，叶节点，children，NIL末尾的节点探讨树的复杂度情况; 考虑树的高度Height; 从search delete insert三个方面分别去考虑

• 红黑树

  通过旋转，变换上下红黑颜色实现自我平衡，红黑树的条件：根结点是黑的，红的children是黑的，到NIL结点的距离相等

• 2-3-4 Trees

  Every Path from root to leaf has same length

  Insertion:

  Search to bottom for key.

  2-node at bottom: convert to a 3-node.

  3-node at bottom: convert to a 4-node

  4-node at bottom: no room for new key

• LLRB Trees