数据结构中的平衡二叉树（第二部分）

众所周知，在大多数情况下（如插入序列是有序时），二叉搜索树的高度会显著增加（即成为一条链），从而使各种操作的时间复杂度也随之提升至O(n)水平）。然而，在进行了多次随机化建立之后发现，在删除操作中我们总是选择用待删除节点的后继节点替代其本身位置这一做法会导致右子树数量不断减少甚至消失（即导致整棵树向左倾斜）。这种现象直接破坏了二叉搜索树的平衡性并显著提升了其操作的时间复杂度。因此我们引入了平衡二叉树以解决这些问题

平衡二叉搜索树定义：自平衡二叉搜索树（Self-balancing binary search tree）也被称为AVL Tree（与AVL算法不同），具有以下特性：它是一棵空树或者其左右子树的高度差绝对值不超过1，并且左右子_tree均为一棵平衡二_ search_ tree。常见的实现方法包括红黑_ tree和AVL等。在_ search_ 操作中其时间复杂度通常维持在O(log₂n)范围内

最小二叉平衡树的节点的公式如下：

F(n)=F(n-1)+F(n-2)+1

它类似于一个递归定义的序列，并遵循类似的模式于每个层级中构建数值关系网络。这种序列结构与经典的斐波那契数列具有相似性特征，在每一层都采用根节点作为基准点进行数值计算与分布安排。具体而言，在该序列中根节点为1；在第n层中左侧子树的节点数目由前一层决定（即F(n-1)），右侧子树则由前前一层决