week08 总结

本周学习了数据结构算法和网络通信协议及数据库原理和性能优化。



数据结构有数组/链表/hash表/栈/队列/树/跳表。



数组一般是内存中的一块连续空间，是读写性能最高的数据结构。



树常用于排序查找场景。

二叉排序树左子树小于等于跟节点小于等于右子树，查询时间复杂度O(long n)。

二叉树易出现不平衡情况甚至退化成链表。为此设计出了平衡二叉树，平衡二叉树规定任意子树左右子树深度之差不超过1。可通过旋转二叉树保持树的平衡。

平衡二叉树在大量增删场景下可能需要进行多次旋转效率较低。

红黑树规定根节点是黑色，每个叶子结点都是黑色空节点，从跟节点到叶子结点不会出现连续红色节点，从任何节点出发到叶子节点黑色节点数都相同。

红黑树最多只需3次旋转即可平衡，因此在修改情况下效率更高，但是在查找上较平衡二叉树稍差一些。



常用算法有穷举算法/递归算法/贪心算法/动态规划。