57-Day4.md

DAY 4

​ 今日要点：中值与选择、B+树、哈希

中值与选择

• 选取数组中第k大的数，排序后查找（O(n log n)）

• 优化：通过第二节课所讲的分治的思路，选取支点，比较两侧小于支点的数的个数，等于k返回支点，否则去两侧继续进一步寻找支点

• 进一步优化：将数组按5个一组进行分割，再找中位数（当且仅当是5个一组（这个就很神奇了），复杂度为O(n)，不过常数项很大，只有当n较大时，才能体现出比归并快）

B+ 树

• 在数据库中较为泛用的数据结构，本质为2-3-4树
• 由于子节点存放父节点的数据，且叶子节点除数据外还存放着指向下一个叶子节点的指针，故遍历叶子节点即可获取树中包含的所有数据，且遍历过程较为容易

哈希

• 能O(1)地实现数据的插入、删除与查找
• 为避免哈希函数的糟糕选取导致性能的退化，可构造哈希函数族，每次使用时从其中随机选取

总结

​ 今日深入学习了树结构中较为广泛使用的B+树，另外了解了哈希这一在查找、删除与插入方面的利器，对于数据结构有了更为深刻的认识。另外对于各位同学在Study Memo中的优秀分享表示诚挚的感谢，课后对于知识的理解与消化有很好的帮助！