首页 > 代码库 > 【算法学习】AVL平衡二叉搜索树原理及各项操作编程实现（C语言）
【算法学习】AVL平衡二叉搜索树原理及各项操作编程实现（C语言）
#include<stdio.h>#include "fatal.h"struct AvlNode;typedef struct AvlNode *Position;typedef struct AvlNode *AvlTree;typedef int ElementType ;AvlTree MakeEmpty(AvlTree T);Position Find(ElementType X,AvlTree T);Position FindMin(AvlTree T);Position FindMax(AvlTree T);AvlTree Insert(ElementType X,AvlTree T);AvlTree Delete(ElementType X,AvlTree T);ElementType Retrieve(Position P);struct AvlNode{ ElementType Element; AvlTree left; AvlTree right; int height;};AvlTree MakeEmpty(AvlTree T){ if(T!=NULL) { MakeEmpty(T->left); MakeEmpty(T->right); free(T); } return NULL;}Position Find(ElementType X,AvlTree T){ if(T==NULL) return NULL; if(X<T->Element) return Find(X,T->left); else if(X>T->Element) return Find(X,T->right); else return T;}Position FindMin(AvlTree T){ if(T==NULL) return NULL; if(T->left==NULL) return T; else return FindMin(T->left);}Position FindMax(AvlTree T){ if(T==NULL) return NULL; if(T->right==NULL) return T; else return FindMax(T->right);}static int Height(Position P){ if(P==NULL) return -1; else return P->height;}static int Max(int Lhs,int Rhs){ return Lhs>Rhs?Lhs:Rhs;}//RR旋转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),Height(K2->right))+1; return K1;}//LL旋转static Position SingleRotateWithRight(Position K1){ Position K2; K2=K1->right; K1->right=K2->left; K2->left=K1; K1->height=Max(Height(K1->left),Height(K1->right))+1; K2->height=Max(Height(K2->right),Height(K1->left))+1; return K2;}//LR旋转static Position DoubleRotateWithLeft(Position K3){ K3->left=SingleRotateWithRight(K3->left); return SingleRotateWithLeft(K3);}//RL旋转static Position DoubleRotateWithRight(Position K3){ K3->right=SingleRotateWithLeft(K3->right); return SingleRotateWithRight(K3);}AvlTree Insert(ElementType X,AvlTree T){ if(T==NULL) { T=malloc(sizeof(struct AvlNode)); if(T==NULL) FatalError("out of space!!!"); else { T->Element=X; T->right=T->left=NULL; } } else if(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); else T=DoubleRotateWithLeft(T); } } else if(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); else T=DoubleRotateWithRight(T); } } T->height=Max(Height(T->left),Height(T->right))+1; return T;}AvlTree Delete(ElementType X,AvlTree T){ Position TmpCell; if(T==NULL) Error("Element not found"); else if(X<T->Element) { T->left=Delete(X,T->left); if(Height(T->right)-Height(T->left)==2) { if(Height(T->right->left)>Height(T->right->right)) T=DoubleRotateWithRight(T); else T=SingleRotateWithRight(T); } } else if(X>T->Element) { T->right=Delete(X,T->left); if(Height(T->left)-Heighe(T->right)==2) { if(Heighe(T->left->right)>Height(T->left->left)) T=DoubleRotateWithLeft(T); else T=SingleRotateWithLeft(T); } } //找到要删除的节点就是根节点，且根节点的左右子树都不为空 else if(T->left&&T->right) { if(Height(T->left)>Height(T->right)) { T->Element=FindMax(T->left)->Element; T->left=Delete(T->Element,T->left); } else { T->Element=FindMin(T->right)->Element; T->right=Delete(T->Element,T->right); } } //找到是根节点，但是根节点有一个或者没有子节点 else { TmpCell=T; if(T->left==NULL) T=T->right; else if(T->right==NULL) T=T->left; free(TmpCell); } T->height=Max(Height(T->left),Height(T->right))+1; return T;}ElementType Retrieve(Position P){ if(P==NULL) return -1; else return P->Element;}
fatal.h
#include <stdio.h>#include <stdlib.h>#define Error( Str ) FatalError( Str )#define FatalError( Str ) fprintf( stderr, "%s\n", Str ), exit( 1 )
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。