不同类型的树结构

二进制是树形结构的最基本形式，每个节点最多有两个子节点。子节点被称为左节点和右节点。二叉树的结构如下图所示：

二叉搜索树（BST）是一种特殊的二叉树，其节点以排序方式存储。它的排序方式是，在任何给定的点上，节点值必须大于或等于左侧子节点值，小于右侧子节点值。每个节点都必须满足这一属性，才能将其视为二叉搜索树。由于节点是按特定顺序排列的，因此二进制搜索算法可以在对数时间内搜索 BST 中的项目。它总是优于线性搜索，后者需要 \$O(n)\$ 时间，我们将在下一章探讨它。下面是二叉搜索树的一个示例：

自平衡二叉搜索树或高度平衡二叉搜索树是一种特殊类型的二叉搜索树，它试图通过自动调整来始终保持树的高度或层数尽可能小。例如，下图左边是一棵二叉搜索树，右边是一棵自平衡二叉搜索树：

高度平衡二叉树总是更好，因为与普通二叉树相比，它有助于更快地进行搜索操作。自平衡或高度平衡二叉搜索树有不同的实现方式。以下是一些常用的实现方法：

我们将在下面的部分中讨论一些高度平衡的树。

B 树是一种特殊的二叉树，它是自平衡的。这与自平衡二叉搜索树不同。主要区别在于，在 B 树中，我们可以将任意数量的节点作为子节点，而不仅仅是两个。B 型树适用于大型数据集，主要用于文件系统和数据库。B 树中不同操作的复杂度是对数。

N 叉树是一种特殊的树，其中一个节点最多可以有 N 个子节点。这也被称为 k 向树或 M 向树。二叉树是一种 N 叉树，其中 N 的值为 2。