数据结构与算法分析（七）——C++实现平衡二叉树

平衡二叉树的概念

概念：

1.每个节点的左子树和右子树的高度最多差1的二叉查找树

操作时的注意事项：

每一次的插入可能会破坏平衡条件，故需要对节点进行平衡性判断然后平衡（单旋转和双旋转）。

这里认为第一个不平衡的节点为a

单旋转的使用情况：

1.对a的左儿子的左子树进行插入；

2.对a的右儿子的右子树进行插入；

注：

单旋转需将儿子节点上浮，a和其子树的root作为其儿子，原儿子节点的另一侧子树现挂置a下方。

双旋转的使用情况：

1.对a的右儿子的左子树进行插入；

2.对a的左儿子的右子树进行插入；

注：

双旋转将子树的root上浮，a和其儿子节点作为root的儿子，原子树根root的两侧子树分别挂在a和原来的儿子节点下。

代码实现

1、实现各种旋转

/***@name Single_Rotate_left：单旋转 不平衡节点的左儿子上浮**/AvlTree Single_Rotate_left(AvlTree K2){AvlTree temp=K2->left;K2->left=temp->right;temp->right=K2;return temp;}/***@name Single_Rotate_right：单旋转 不平衡节点的右儿子上浮**/AvlTree Single_Rotate_right(AvlTree K2){AvlTree temp=K2->right;K2->right=temp->left;temp->left=K2;return temp;}/***@name Double_Rotate_left：双旋转 左儿子的右子树 **/AvlTree Double_Rotate_left(AvlTree K3){AvlTree temp=K3->left->right;K3->left->right=temp->left;temp->left=K3->left;K3->left=temp->right;temp->right=K3;return temp;}/***@name Double_Rotate_left：双旋转 右儿子的左子树**/AvlTree Double_Rotate_right(AvlTree K3){AvlTree temp=K3->right->left;K3->right->left=temp->right;temp->right=K3->right;K3->right=temp->left;temp->left=K3;return temp;}

2.实现插入

这里注意插入后，节点需要进行平衡性判断，若不平衡，再进行判断，是实现左（单/双）旋转or右（单/双）旋转。

/***@name Insert：插入一个新的树节点 *@param1 data：新的树节点的数据*@param2 T：从该树节点向下插*@ret ：返回插入完成并平衡过了的该树节点**/AvlTree Balance_BinaryTree::Insert(int data,AvlTree T){if(T==NULL)//如果递归到空节点的话 新建一个树节点后返回{AvlTree temp=new AvlNode;temp->data=data;temp->left=temp->right=NULL;temp->height=1;T=temp;}else{if(data<T->data){T->left=Insert(data,T->left);if(Height(T->left)-Height(T->right)==2)//此时左子树的高度比右子树的高度大2 需要平衡{if(data<T->left->data)//此时说明插入的位置在左儿子的左子树 进行左单旋转T=Single_Rotate_left(T);else if(data>T->left->data)//此时说明插入的位置在左儿子的右子树 进行左双旋转T=Double_Rotate_left(T);}}else if(data>T->data){T->right=Insert(data,T->right);if(Height(T->right)-Height(T->left)==2)//此时右子树的高度比左子树的高度大2 需要平衡{if(data>T->right->data)//此时说明插入的位置在右儿子的右子树 进行右单旋转T=Single_Rotate_right(T);else if(data<T->right->data)//此时说明插入的位置在右儿子的左子树 进行右双旋转T=Double_Rotate_right(T);}}else//如果插入的元素相同则报错{cout<<"already have the same element"<<endl;}T->height=Max(Height(T->left),Height(T->right))+1; //插入完成后重新计算该树节点的高度}return T;}