查找——平衡二叉树

想要了解完整的动态查找可以看看前面的文章

平衡二叉树

（1）平衡二叉树又称为 AVL 树。在平衡二叉树中每个结点都有一个平衡因子域，用来存放该结点的平衡因子值;例如假设用 TL 代表结点 T 的左子树的最大深度;TR 代表结点 T 的右子树的最大深度;那么，AVL 树每个结点的平衡因子值 T->BF=TL-TR。

• 若 TL-TR=0(即该结点平衡因子值为 0)，则称其为平衡结点。

• 若 TL-TR=1(即该结点平衡因子值为 1)，则称其为左重结点。

• 若 TL-TR=-1，则称其为右重结点。

在一棵二叉排序树中，如果每个结点的平衡因子值都是-1、0、1 三者之一，那么，称这棵树为平衡二叉排序树简称平衡二叉树。树中结点的平衡因子的绝对值大于等于 2，该树不平衡。

（2）观察二叉排序树构造过程找出造成不平衡的原因。新结点插在平衡因子值为 0 的结点左或右都不会造成不平衡。新结点插在平衡因子值为 1(或-1)的结点的右(或左)分支，该结点也不会造成不平衡。新结点插在平衡因子值为 1(或-1)的结点的左(或右)分支上，此时，该结点的平衡因子的绝对值≧2，造成二叉排序树不平衡。下图 10.7 的左图中在 70 插入前，50 的平衡因子值为-1，而右图中 20 插入前，50 的平衡因子值为 1。

• 二叉排序树的类型定义

typedef structBSTNode{

ElemType data;

int bf;(结点的平衡因子域)

struct BSTNode *lchild,*rchild;

} BSTNode,*BSTree;

Void R-Rotate(BSTree &p){(作右旋转处理，)

lc=p->lchild;(LC 为*P 的左子树根结点)

p->lchild=lc->rchild;(LC 的右子树作为*P 的左子树)

lc->rchild=p; p=lc;(P 指向新的根结，即 B 带替 A)

}// R- Rotate

Void L-Rotate(BSTree &p){(作左旋转处理)

rc=p->rchild; (RC 为*P 的右子树根结点)

p->rchild=lc->lchild;(RC 的左子树作为*P 的右子树)

lc->lchild=p;p=rc;(P 指向新的根结，即 B 带替 A)

}// L- Rotate

平衡二叉树算法相对复杂，不做要求，理解平衡二叉树即可。