1.AvlTree的定义
N）。最简单的想法是要求左右子树具有相同的高度。
2.插入操作的问题
2.1.四种情况，两种分类处理
根据树型结构的不同，，我们将分成四种情况来进行旋转处理。
进行旋转处理的时候分成两种大类处理：单旋转和双旋转。
另一种情况的单旋转：
下面我们可以看到另一种情况的双旋转
2.2.旋转操作中的本质
1 k2
3.具体实现代码
#include <stdio.h>#include <stdlib.h>#define Max( a , b ) ( (a) > (b) ? (a) : (b) )typedef int ElementType;struct AvlNode;typedef struct AvlNode *Position;typedef struct AvlNode *AvlTree;struct AvlNode{ElementType Element;AvlTree Left;AvlTree Right;intHeight;};static int Height( Position P ){if ( P == NULL )return -1;elsereturn P->Height;}/*This function can be called only if k2 has a left child*//*Perform a rotate between a node (k2) and its left child*//*Update heights , then return new root*/static Position SingleRotateWithLeft( Position k2 ){Position k1;k1 = k2->Left;k2->Left = k1->Right;k1->Right = k2;k2->Height = Max( Height( k2->Left) , Height( k2->Right ) ) + 1;k1->Height = Max( Height( k1->Left) , k2->Height ) + 1;return k1; //new root}static Position SingleRotateWithRight( Position k2 ){Position k1;k1 = k2->Right;k2->Right = k1->Left;k1->Left = k2;k2->Height = Max( Height( k2->Left ) , Height( k2->Right ) ) + 1;k1->Height = Max( Height( k1->Right ) , k2->Height ) + 1;return k1;}/*This function can be called only if k3 has a left*//*child and k3’s left child has a right child*//*Do the left-right double rotation*//*Update heights,then return new root*/static Position DoubleRotateWithLeft( Position k3 ){/*Rotate between k1 and k2*/k3->Left = SingleRotateWithRight( k3->Left );/*Rotate between k3 and k2*/return SingleRotateWithLeft( k3 );}static Position DoubleRotateWithRight( Position k3 ){/*Rotate between k1 and k2*/k3->Right = SingleRotateWithLeft( k3->Right );/*Rotate between k3 and k2*/return SingleRotateWithRight( k3 );}AvlTree Insert( ElementType X , AvlTree T ){if ( T == NULL ){/*Create and return a one-node tree */T = ( AvlTree )malloc (sizeof( struct AvlNode ));if ( T == NULL )printf("Out of space!!!\n");else{T->Element = X ; T->Height = 0 ; //The height of the leef is 0 !!! Different from the normal tree!T->Left = T->Right = NULL;}}elseif ( X < T->Element ){T->Left = Insert ( X , T->Left );if( Height(T->Left) – Height( T->Right) == 2 )if ( X < T->Left->Element )T = SingleRotateWithLeft( T );elseT = DoubleRotateWithLeft( T );}elseif ( X > T->Element ){T->Right = Insert( X , T->Right );if( Height(T->Right) – Height(T->Left) == 2 )if( X > T->Right->Element )T = SingleRotateWithRight( T );elseT = DoubleRotateWithRight( T );}/* Else X is in the tree already; we’ll do nothing!*/T->Height = Max( Height( T->Left) , Height( T->Right ) ) + 1;return T;}AvlTree Init_AvlTree(AvlTree T, ElementType *ElementArry,int length){int i;//逐个插入查找二叉树中T->Element = ElementArry[0]; //在初始化的过程中直接把第一个点作为根节点。for(i=1;i<length;i++)Insert(ElementArry[i],T);return T;}int main(int argc, char const *argv[]){// 初始化指针AvlTree T = ( AvlTree )malloc(sizeof( struct AvlNode ));T->Left = NULL;T->Right = NULL;Position Temp;ElementType ElementArry[11]= {15,6,18,3,7,17,20,2,4,13,9};/*Initialize the AvlTree*/T = Init_AvlTree( T , ElementArry , 11 );printf("%d\n", T->Left->Right->Left->Element );return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
好好扮演自己的角色，做自己该做的事
