章节 2: 树结构：搜索、索引与建模

树结构提供了一种层次化的方式来组织和访问数据，在机器学习 (machine learning)中有着重要用途，可用于从高效搜索到构建可解释模型等各类任务。本章将介绍树结构如何运作，以及它们在机器学习工具箱中的定位。

我们将学习：

• 基本原理： 回顾树的基本术语和想法，例如节点、边、高度和深度。
• 二叉搜索树 (BST)： 它们的特性及操作（搜索、插入、删除），用于高效数据检索，通常在搜索时达到 $O(\log n)$ 的平均时间复杂度。
• 平衡树： 理解平衡的必要性（例如，AVL树、红黑树），以避免数据倾斜时二叉搜索树出现最坏情况下的 $O(n)$ 性能下降。
• 决策树与集成方法： 将抽象的树结构与具体的机器学习模型联系起来，例如决策树、随机森林和梯度提升树，了解它们如何划分特征空间。
• 树的遍历： 学习如中序、前序和后序遍历等方法，这些方法对模型检查或特征提取很有用。

本章结束后，您将了解如何为特定的机器学习问题选择和使用基于树的结构，并识别它们的性能特点。