内容
- 了解树是如何用于实现文件系统的
- 了解树如何用来计算算术表达式的值
- 了解如何用树实现O(logN)时间进行搜素
- 讨论并使用set和map
二叉树的遍历
- 前序：先处理自己后处理左右儿子
- 中序：先处理左儿子再处理自己再处理右儿子
- 后序：先处理左右儿子再处理自己
二叉查找树（平均深度O(logN)）
性质：对于树中的每个节点X，左子树中所有项的值小于X中的项，右子树中所有项的值大于X中的项
缺点：不能动态调整，若输入为已排序序列则构造出最坏情况下的斜树
AVL树
- 带有平衡条件的二叉查找树
- 一棵AVL树是每个节点的左子树和右子树的高度最多相差1的二叉查找树（空树高度定义为-1）
- 插入新节点可能破坏AVL树的平衡，需要通过旋转解决
把需要平衡的节点叫α
- 对α的左儿子的左子树进行一次插入
- 对α的左儿子的右子树进行一次插入
- 对α的右儿子的左子树进行一次插入
- 对α的右儿子的右子树进行一次插入
1和4（左左，右右）发生在外边，进行一次单旋转即可，2和3（左右，右左）则发生在内部，需要通过双旋转调整
伸展树
节点可以达到任意深度，每次访问某节点后把该节点调整为根节点，任意连续M次操作花费O(MlogN)时间
B树（平衡M路树）
M=3时：2-3树，实现平衡查找树的另一种方法
注意
通过插入元素构造查找树，然后执行中序遍历，可以得到排序后的元素。
这是一种O(NlogN)的排序算法