树¶

1 二叉树¶

• 根节点（root node）
• 父节点（parent node）
• 子节点（left-child node）（right-child node）
• 子树（left subtree）（right subtree）
• 叶节点（leaf node）
• 边（edge）
• 节点所在的层（level）
• 节点的度（degree）
• 二叉树的高度（height）
• 节点的深度（depth）
• 节点的高度（height）

平衡二叉树：任意节点的左子树和右子树的高度之差的绝对值不超过 1

2 二叉树遍历¶

层序遍历（广度优先）

前、中、后序遍历（深度优先）

3 二叉树树组表示¶

• 数组存储在连续的内存中，对缓存友好，访问与遍历虚度快
• 没有指针，节省空间

• 允许随机访问节点

• 空间连续，不能存储大数据

• 增删节点效率极低
• 树中有很多none时，效率低

4 二叉搜索树¶

对于跟节点：左子树索引节点的值 < 根节点的值 <右子树中所有节点的值
任意子树满足上述要求

4.1 查找¶

查找 num ，声明一个节点 cur ，从根节点 root 出发，循环比较节点值 cur.val 和 num 之间的大小关系。
- 若 cur.val < num ，说明目标节点在 cur 的右子树中，因此执行 cur = cur.right 。
- 若 cur.val > num ，说明目标节点在 cur 的左子树中，因此执行 cur = cur.left 。
- 若 cur.val = num ，说明找到目标节点，跳出循环并返回该节点。

4.2 插入¶

插入 num 
1. 查找插入位置：与查找操作相同，根据当前节点值和 num 的大小关系循环向下搜索，直到越过叶节点（遍历至 None ）时跳出。
2. 在该位置插入节点：初始化节点 num ，将该节点置于 None 的位置。

4.3 删除¶

先查找目标节点，再将其删除。
待删除节点的度为 0 时，表示该节点是叶节点，可以直接删除。
当待删除节点的度为 1 时，将待删除节点替换为其子节点即可。
当待删除节点的度为 2 时，将右子树的最小节点或左子树的最大节点替换（中序遍历有序）

5 平衡二叉搜索树¶

内存中使用：
- 查找：AVL > 红黑 > B+
- 插入：红黑 > AVL > B+
- 删除：红黑 > AVL > B+
磁盘上使用：
- 查找：B+ > AVL > 红黑（因为B+树减少了磁盘I/O操作）
- 插入：B+ >红黑 > AVL
- 删除：B+ >红黑 > AVL

5.1 AVL¶

数据记录每个节点的高度和节点平衡因子（左子树高度-右子树高度），当节点平衡因子绝对值>1时旋转树。

应用场景：
- 内存管理：如Windows NT内核的内存管理。
- 嵌入式系统：资源有限，需要高效查找操作的场景。
- 编译器实现：符号表的管理。

5.2 红黑树¶

应用场景：
- 语言库实现：如C++的std::map和std::set
- 操作系统中的调度器：如Linux内核的完全公平调度器（CFS）

5.3 B+树¶

应用场景：
- 数据库索引：如MySQL的InnoDB存储引擎中的索引实现。
- 文件系统：如NTFS文件系统中的索引结构。
- 大数据处理：需要高效磁盘I/O的应用场景。