平衡二叉搜索树

平衡二叉树也称为高度平衡树。它被定义为这样一种二叉树：其左子树和右子树的高度差不超过 m，其中 m 通常等于 1。树的高度是根节点和叶节点之间最长路径上的边数。

上面的树是一棵二叉搜索树。二叉搜索树是一种树，其中左侧的每个节点的值都小于其父节点，而右侧的节点的值都大于其父节点。在上面的树中，n1 是根节点，n4、n6、n7 是叶节点。n7 节点是距离根节点最远的节点。n4 和 n6 包含 2 条边，根节点和 n7 节点之间存在 3 条边。由于 n7 距离根节点最远；因此，上面树的高度为 3。

现在我们将看看上面的树是否平衡。左子树包含节点 n2、n4、n5 和 n7，而右子树包含节点 n3 和 n6。左子树有两个叶节点，即 n4 和 n7。节点 n2 和 n4 之间只有一条边，节点 n7 和 n2 之间有两条边；因此，节点 n7 距离根节点最远。左子树的高度为 2。右子树只包含一个叶节点，即 n6，并且只有一条边；因此，右子树的高度为 1。左子树和右子树的高度差为 1。由于我们得到的值是 1，所以我们可以说上面的树是高度平衡树。计算高度差的过程应该对每个节点（如 n2、n3、n4、n5、n6 和 n7）都执行。当我们处理每个节点时，我们会发现 k 的值不超过 1，因此我们可以说上面的树是平衡的二叉树。

在上面的树中，n6、n4 和 n3 是叶节点，其中 n6 是距离根节点最远的节点。根节点和叶节点之间存在三条边；因此，上面树的高度为 3。当我们以 n1 作为根节点时，左子树包含节点 n2、n4、n5 和 n6，而右子树包含节点 n3。在左子树中，n2 是根节点，n4 和 n6 是叶节点。在 n4 和 n6 节点中，n6 是距离其根节点最远的节点，n6 有两条边；因此，左子树的高度为 2。右子树在其左侧和右侧都没有任何子节点；因此，右子树的高度为 0。由于左子树的高度为 2，右子树的高度为 0，所以左子树和右子树的高度差为 2。根据定义，左子树和右子树的高度差不能大于 1。在这种情况下，差值为 2，大于 1；因此，上面的二叉树是不平衡的二叉搜索树。

为什么我们需要平衡二叉树？

让我们通过一个例子来理解平衡二叉树的必要性。

上面的树是一棵二叉搜索树，因为所有左子树节点都小于其父节点，所有右子树节点都大于其父节点。假设我们想在上面的树中找到值 79。首先，我们将节点 n1 的值与 79 进行比较；由于 79 的值不等于 35 且大于 35，所以我们移到节点 n3，即 48。由于值 79 不等于 48 且 79 大于 48，所以我们移到 48 的右子节点。节点 48 的右子节点的值是 79，它等于要搜索的值。搜索元素 79 所需的跳数是 2，搜索任何元素所需的最大跳数是 2。搜索元素的平均情况是 O(logn)。

上面的树也是一棵二叉搜索树，因为所有左子树节点都小于其父节点，所有右子树节点都大于其父节点。假设我们想在上面的树中找到值 79。首先，我们将值 79 与节点 n4（即 13）进行比较。由于值 79 大于 13，所以我们移到节点 13 的右子节点，即 n2 (21)。节点 n2 的值是 21，小于 79，所以我们再次移到节点 21 的右侧。节点 21 的右子节点的值是 29。由于值 79 大于 29，所以我们移到节点 29 的右子节点。节点 29 的右子节点的值是 35，小于 79，所以我们移到节点 35 的右子节点，即 48。值 79 大于 48，所以我们移到节点 48 的右子节点。节点 48 的右子节点的值是 79，它等于要搜索的值。在这种情况下，搜索元素所需的跳数是 5。在这种情况下，最坏情况是 O(n)。

如果节点数增加，树图 1 中使用的公式比树图 2 中使用的公式更有效。假设上面两棵树中可用的节点数为 100,000。在树图 2 中搜索任何元素所需的时间是 100,000 µs，而在树图 1 中搜索元素所需的时间是 log(100,000)，即 16.6 µs。我们可以观察到上面两棵树之间巨大的时间差异。因此，我们得出结论，平衡二叉树比线性树数据结构提供更快的搜索速度。