树 (Tree)

定义与概念

树是一种非线性分层数据结构，由节点和边组成，每个节点有零个或多个子节点。

核心特点

• 层次结构：数据按层次组织
• 一对多关系：父节点对应多个子节点
• 高效搜索：有序树支持快速查找
• 递归性质：子树具有相同结构

主要类型

• 二叉树：每个节点最多两个子节点
• 二叉搜索树：左子树值小于根节点，右子树值大于根节点
• 平衡二叉树：自动保持平衡的BST（AVL、红黑树）
• 堆：完全二叉树，用于优先队列
• B树：多路搜索树，用于文件系统和数据库

基本操作复杂度

操作	平均情况	最坏情况
访问	O(log n)	O(n)
搜索	O(log n)	O(n)
插入	O(log n)	O(n)
删除	O(log n)	O(n)

应用场景

• 文件系统目录结构
• 数据库索引
• 组织结构图
• 决策树算法
• HTML DOM树