动态搜索-平衡二叉树，C/C++语言代码实现

1.简介

平衡二叉树具有以下性质：空树或左右子树的高度差绝对值不超过1，左右子树为平衡二叉树。平衡二叉树常用的实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。其中最经典的是AVL树。

综上所述：平衡二叉树是一种二叉排序树，其中左子树与每个节点的右子树的高度差至少等于1。

2。属性值

AVL树是一棵二叉树，具有以下属性（注意空树也是平衡二叉树）：

l 一定是二叉搜索树

l 左子树和右子树是两棵二叉树平衡，且左子树树与右子树的深度差的绝对值不超过1。

l 如果定义二叉树节点的平衡因子BF为左子树节点的深度减去。右子树的宽度，则平衡二叉树中所有节点的平衡因子只能是-1,0,1。

l 只要二叉树中节点的平衡因子的绝对值为大于1，则平衡二叉树是不平衡的。

3。实现：

要构建AVL树，我们需要了解核心操作。整个实现过程就是将元素按顺序插入到平衡二叉树中（通过二叉排序树的方法）。如果存在不平衡，则应根据新插入的节点与最低不平衡节点的位置关系进行适当的调整。每种调节方式又分为4种类型：LL型、RR型、LR型和RL型。其他操作类似于在通用树中插入和修改数据。由于空间限制，我们不会在这里做太多，所以我们将使用其中之一。以这种LR型排列为例进行说明，其他各种方法也是以此类推：

因为在A（L）的左孩子的右子树（R）中插入一个新节点，原来的平衡二进制。树变得不平衡，此时平衡因子A从1变为2。图5是LR类型的最简单形式。显然，根据大小关系，应该将节点C作为新的根节点，另外两个节点作为左右子节点，以达到平衡。 ？或者，CL和CR被设置为B和左子树A)的右子树。

4。代码演示：

代码仅供参考。具体实现请根据实际情况修改：