数据结构学习——二叉树
Vector和List的特点：
| 类型 | 底层结构 | 随机访问 | 插入和删除 | 空间利用率 | 使用场景 |
| Vector | vector的底层结构是动态顺序表，在内存中是一段连续的空间 | O(1) | 查询数据位置最坏需要O(N)，且数据迁移最坏也需要O(N) | 内存中是一段连续的空间，所以不容易造成内存碎片，利用率高 | vector适合需要高效率存储，需要随机访问，并且不管行插入和删除效率的场景 |
| List | list的底层结构是带头节点的双向循环链表，在内存中不是一段连续的空间 | O(N) | 查询数据位置最坏需要O(N)，插入和删除仅改变前后指针指向需要O(1) | 动态开辟空间，容易造成内存碎片，空间利用率低 | list适合有大量的插入和删除操作，并且不关心随机访问的场景 |
二叉树的概念引入，是为了兼顾Vector和List的优点：高效地查找、插入和删除。以平衡二叉搜索树（已经有序）为例，静态查找和动态修改操作都可以在O(logn)以内。
二叉搜索树（Binary Search Tree）——>AVL树()
二叉搜索树的search、insert和remove操作的运行时间正比于树高，当最坏情况下，二叉树会退化成列表，查找时间复杂度降为O(N).为了解决这个问题引入平衡二叉搜索树的概念，即兄弟子树高级尽可能接近，维持一定的平衡状态（通过旋转操作实现）。
伸展树：逐层伸展，节点V一旦被访问，随即转移到树根。（一步一步往上爬；自下而上，逐层单旋；直到v最终被推送至根。）