1. 树
根结点: 没有父结点的结点
分支结点: 有子结点的结点
叶子结点: 没有子结点的结点
兄弟结点: 拥有相同父结点的结点
边: 父结点与自结点之间的连线. 一棵树有 n 个结点, 则有 n-1 条边
路径长度: 路径上边的条数; 路径上有 n 个结点, 则路径长度为 n-1
内部路径长: 一棵树的所有结点的深度的和
深度: 从根结点到任意结点的路径长度
层数: 根结点在1层, 其他任一结点的层数是其父结点的层数加1
高度: 从任意结点到叶子结点的层数
树的高度 = 树的层数: 从根结点到叶子结点的最大层数
度: 子结点个数
树的度: 最大子结点个数
1.1. 遍历方式
- 前序遍历 结点的处理在它的子结点之前. 根左右
- 后序遍历 结点的处理在它的子结点之后. 左右根
- 中序遍历 先处理左子结点, 再处理当前结点, 最后处理右子结点. 左根右
- 层序遍历 深度为 d 的结点要在 d+1 的结点前处理.
2. 二叉树 Binary Tree
一棵平均二叉树的深度要比结点个数小的多
2.1. 二叉查找树 Binary Search Tree
特点:
对于树中每个结点 X, 它的左子树中所有项的值都小于 X 中的项, 而它的右子树中的所有项的值都大于 X 中的项.
查找时间复杂度与二叉查找树的高度成正比: , n 为结点个数
3. 平衡树
平衡树有: AVL, SBT, 伸展树, 红黑树, TREAP, B-Tree, B+Tree, B*Tree等
3.1. 平衡二叉树 AVL
左右子树的树高不大于 1.
在插入或删除后自动平衡左右分支的高度.
用于解决普通二叉树在大量插入或删除后出现查询复杂度退化的问题
4. B-Tree
5. 红黑树 RB-Tree
6. Resource
- 数据结构 – 清华大学出版社