week08 总结

用户头像
Safufu
关注
发布于: 2020 年 07 月 29 日

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



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



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



树常用于排序查找场景。

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

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

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

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

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



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

用户头像

Safufu

关注

还未添加个人签名 2018.11.16 加入

还未添加个人简介

评论

发布
暂无评论
week08总结