27-Day3.md

第三周课程小结

复杂度记号

复杂度上界O()

渐进时间复杂度 $$\theta$$ ()

复杂度下界$\Omega$ ()

排序算法

quick sort: worst case O($n^2$), average case O($nlogn$)

bucket sort: average case O($n\log_nM$), M is the peak of the list

数据结构——树

链表

二叉搜索树（BST），建立、搜索、插入、删除、遍历

2-3-4树，建立、搜索、插入、删除

红黑树

性质1：每个节点要么是黑色，要么是红色。

性质2：根节点是黑色。

性质3：每个叶子节点（NIL）是黑色。

性质4：每个红色结点的两个子结点一定都是黑色。

性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。