邯郸建设企业网站,wordpress线报主题,购物优惠券网站怎么做,湖北省住房建设厅网站一、树的基础概念
1. 定义 树是一种非线性数据结构#xff0c;由 n 个有限节点组成层次关系集合。特点#xff1a; 有且仅有一个根节点其余节点分为若干互不相交的子树节点间通过父子关系连接
2. 关键术语 术语定义节点包含数据和子节点引用的单元根节点树的起始节点#…
一、树的基础概念
1. 定义 树是一种非线性数据结构由 n 个有限节点组成层次关系集合。特点 有且仅有一个根节点其余节点分为若干互不相交的子树节点间通过父子关系连接
2. 关键术语 术语定义节点包含数据和子节点引用的单元根节点树的起始节点没有父节点子节点直接连接到父节点的节点叶子节点没有子节点的节点度节点拥有的子树数目树的高度从根节点到最远叶子节点的最长路径边数树的深度从根节点到当前节点的层数路径从根到某节点的唯一通道
3. 分类 二叉树每个节点最多两个子节点左子树 / 右子树多叉树每个节点可包含多个子节点如三叉树、四叉树有序树子树顺序有意义如二叉搜索树无序树子树顺序无关
二、二叉树的核心特性
1. 特殊二叉树 满二叉树所有层节点数达到最大值完全二叉树最后一层节点靠左排列其余层满二叉搜索树左子树值 根值 右子树值
2. 重要性质 第 i 层最多有 2^(i-1) 个节点高度为 h 的二叉树最多有 2^h -1 个节点完全二叉树节点编号 i 的子节点为 2i 和 2i1叶子节点数 度为 2 的节点数 1
3. 存储结构 方式实现方式适用场景数组存储按层序编号存储节点值完全二叉树链式存储结构体包含左右指针任意二叉树
三、二叉树遍历方法
1. 深度优先遍历 前序遍历根→左→右 递归实现: 收起 python def preorder(root):if root:print(root.val)preorder(root.left)preorder(root.right)中序遍历左→根→右 应用: 二叉搜索树中序遍历结果有序后序遍历左→右→根 应用: 计算表达式树
2. 广度优先遍历 层序遍历逐层访问节点 队列实现: 收起 python def levelorder(root):queue [root]while queue:node queue.pop(0)print(node.val)if node.left: queue.append(node.left)if node.right: queue.append(node.right)3. 遍历对比 遍历方式时间复杂度空间复杂度典型应用前序O(n)O(h)复制树、生成括号中序O(n)O(h)二叉搜索树排序后序O(n)O(h)删除树、计算表达式层序O(n)O(w)层次处理、找最近公共祖先
四、树结构的典型应用 文件系统目录结构Windows 资源管理器XML/JSON 解析文档对象模型DOM数据库索引B 树 / B 树优化查询压缩算法哈夫曼树构建最优前缀编码人工智能决策树、蒙特卡洛树搜索网络路由路由表的层次化存储
五、高级树结构详解
5.1 B 树B-Tree
5.1.1 定义与特性 平衡多路查找树所有叶子节点在同一层阶数 m每个节点最多有 m 个子节点m≥2关键特性 根节点至少 2 个子节点非根节点至少⌈m/2⌉个子节点叶子节点包含所有数据
5.1.2 操作复杂度 操作时间复杂度查找O(log_m n)插入O(log_m n)删除O(log_m n)
5.1.3 典型应用 数据库索引如 MySQL 的 InnoDB 引擎文件系统目录结构外部存储数据管理
5.1.4 与二叉搜索树对比 特性B 树二叉搜索树平衡方式多叉平衡二叉平衡查找效率更低的 I/O 次数依赖树的高度适用场景外存数据管理内存数据管理
5.2 红黑树Red-Black Tree
5.2.1 定义与性质 自平衡二叉搜索树通过颜色标记保持平衡五大性质 节点颜色为红或黑根节点为黑色叶子节点NIL为黑色红节点的子节点必须为黑色从任一节点到其叶子的路径包含相同数量黑节点
5.2.2 操作复杂度 操作时间复杂度查找O(log n)插入O(log n)删除O(log n)
5.2.3 典型应用 Java 的 TreeMap/TreeSetC 的 std::mapLinux 内核的进程调度Nginx 的定时器管理
5.2.4 旋转操作 左旋转将某个节点作为支点向左下方旋转右旋转将某个节点作为支点向右上方旋转示例代码片段 收起
python
def left_rotate(x):y x.rightx.right y.leftif y.left:y.left.parent xy.parent x.parentif x.parent is None:root yelif x x.parent.left:x.parent.left yelse:x.parent.right yy.left xx.parent y5.3 其他重要树结构 类型核心特性典型应用AVL 树严格平衡左右子树高度差≤1内存中的有序数据哈夫曼树带权路径长度最小数据压缩如 ZIP 算法B 树所有数据在叶子节点非叶子存索引数据库索引线段树区间查询优化统计类问题字典树 (Trie)前缀共享存储拼写检查、IP 路由表
六、树结构对比与选择策略
6.1 平衡树对比 结构平衡条件插入 / 删除复杂度适用场景B 树多叉平衡O(log_m n)外存数据管理红黑树颜色标记平衡O(log n)内存有序结构AVL 树高度差平衡O(log n)频繁查询场景
6.2 选择策略 内存场景 数据量小 → 二叉搜索树数据量大 → 红黑树 / AVL 树 外存场景 读多写少 → B 树读写均衡 → B 树 特殊需求 前缀匹配 → Trie 树数据压缩 → 哈夫曼树
七、树结构算法优化技巧 空间优化 使用数组存储完全二叉树节省指针空间共享子树结构如 Trie 树的前缀共享 时间优化 利用缓存友好性B 树的节点大小与磁盘块对齐延迟更新如红黑树的懒删除 并行处理 多叉树的多路并行查找分布式哈希表DHT的树状路由
