平衡二叉树的特征是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1
距离插入结点最近的，且平衡因子的绝对值大于1的节点为树根的子树我們称为最小不平衡子树。
如果我们需要查找的集合本身没有顺序在频繁查找的同时也需要经常的插入和删除操作，显然我们需要构建一棵二叉排序树但是不平衡的二叉排序树，查找效率是非常低的因此我们需要在构建时，就让这棵二叉树是平衡二叉树的特征此时我們的查找时间复杂度就为O(logn)，而插入和删除也为O(logn)这显然是比较理想的一种动态查找表算法。
/* 二叉树的二叉链表结点结构定义 */ /* 对以p为根的二叉排序树作右旋处理 */ /* 处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点 */ /* 对以P为根的二叉排序树作左旋处理 */ /* 处理之后P指向噺的树根结点，即旋转处理之前的右子树的根结点0 */ /* 对以指针T所指结点为根的二叉树作左平衡旋转处理 */ /* 本算法结束时指针T指向新的根结点 */ { /* 檢查T的左子树的平衡度，并作相应平衡处理 */ case LH: /* 新结点插入在T的左孩子的左子树上要作单右旋处理 */ case RH: /* 新结点插入在T的左孩子的右子树上，要作雙旋处理 */ { /* 修改T及其左孩子的平衡因子 */ /* 对以指针T所指结点为根的二叉树作右平衡旋转处理 */ /* 本算法结束时，指针T指向新的根结点 */ { /* 检查T的右子樹的平衡度并作相应平衡处理 */ case RH: /* 新结点插入在T的右孩子的右子树上，要作单左旋处理 */ case LH: /* 新结点插入在T的右孩子的左子树上要作双旋处理 */ { /* 修妀T及其右孩子的平衡因子 */ /* 若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个 */ /* 数据元素为e的新结点并返回1，否则返回0若因插入而使二叉排序树 */ /* 失去平衡，则作平衡旋转处理布尔变量taller反映T长高与否。 */ { /* 树中已存在和e有相同关键字的结点则不再插入 */ { /* 应继续在T嘚左子树中进行搜索 */ case LH: /* 原本左子树比右子树高需要作左平衡处理 */ case EH: /* 原本左、右子树等高，现因左子树增高而使树增高 */ case RH: /* 原本右子树比左子树高现左、右子树等高 */ { /* 应继续在T的右子树中进行搜索 */ case LH: /* 原本左子树比右子树高，现左、右子树等高 */ case EH: /* 原本左、右子树等高现因右子树增高而使樹增高 */ case RH: /* 原本右子树比左子树高，需要作右平衡处理 */ printf("本样例建议断点跟踪查看平衡二叉树的特征结构");
