【架构师训练营第 1 期 08 周】 学习总结

【架构师训练营第 1 期 08 周】 学习总结



这周学习的主题是性能优化，讲解了硬盘、数据结构、经典算法和并发网络编程的基础知识。

知识点太多不一一描述，讲一下我印象最深刻的是数据结构和算法模块。在看老师讲解知识点的时候是还觉得比较容易理解，但是做作业的时候才发现有很多细节要考虑。比如遇到一道算法题，经过思考会有很多种解决方法，但是各种方法的时间复杂度却各不相同，自己也对时间复杂度计算不是很明白，需要在后面补充知识。做题的时候再去网上搜索相关问题发现也是各种解题方案都有，有的代码简短，需要思考很久才能明白，惊叹与大神的奇思妙想。还是想学习针对我这种普通人的算法题解决思路。

另外听着老师梳理了树的各种结构，加深了印象。因为现在HashMap或者数据库索引都会用到红黑树结构，之前一直不太明白，这次终于理解深刻了一点。



部分总结：

1.排序二叉树：每个节点的左边比节点小，右边比节点大，效率可以，但是有可能退化成链表，效率低；

2.平衡二叉（排序）树：节点层级相差不超过1，通过左旋和右旋保持平衡，但是插入和更新效率会低；

3.红黑（排序）树：

每个节点只有两种颜色：红色和黑色

根节点是黑色的。

每个叶子节点（NIL）都是黑色的空节点。

从根节点到叶子节点，不会出现两个连续的红色节点。

从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。



红黑树 VS 平衡二叉树：红黑树要求没那么严格，所以插入更新效率会比平衡二叉树高，所以一般数据会变化得频繁的情况就使用红黑树。平衡二叉树查询效率高，但是插入更新效率低，谨慎使用。