《软件开发设计avl树源代码》由会员分享，可在线阅读，更多相关《软件开发设计avl树源代码（12页珍藏版）》请在金锄头文库上搜索。
1、#include #include #define N 15typedef int ElementType;typedef struct AvlNode / AVL 树的节点ElementType data;struct AvlNode *left; / 左孩子struct AvlNode *right; / 右孩子int Height;*Position,*AvlTree;AvlTree MakeEmpty(AvlTree T);Position Find(ElementType x,AvlTree T);Position FindMin(AvlTree T);Position FindMa
2、x(AvlTree T);AvlTree Insert(ElementType x,AvlTree T);AvlTree Delete(ElementType x,AvlTree T);ElementType Retrieve(Position P);void Display(AvlTree T);AvlTree MakeEmpty(AvlTree T)if( T != NULL)MakeEmpty(T-left); MakeEmpty(T-right);free(T);return NULL;/* 查找 可以像普通二叉查找树一样的进行，所以耗费 O(log n)时间，因为 AVL 树总是保持
3、平衡的。* 不需要特殊的准备，树的结构不会由于查找而改变。 （这是与伸展树查找相对立的，它会因为查找而变更树结构。 ）*/Position Find(ElementType x,AvlTree T)if(T = NULL)printf(NOT FOUND! n);return NULL;if(x data)return Find(x,T-left);else if(x T-data)return Find(x,T-right);elseprintf(FOUND!n); return T;/* FindMax， FindMin 查找最大和最小值，*/Position FindMin(AvlTre
4、e T)if(T = NULL)return NULL;if( T-left = NULL)return T;elsereturn FindMin(T-left);Position FindMax(AvlTree T)if(T != NULL)while(T-right != NULL)T=T-right;return T;/* 返回节点的高度*/static int Height(Position P)if(P = NULL)return -1;elsereturn P-Height;static int Max(int h1,int h2)return h1 h2 ?h1:h2;/* 此函
5、数用于 k2 只有一个左孩子的单旋转，* 在 K2 和它的左孩子之间旋转，* 更新高度，返回新的根节点*/static Position SingleRotateWithLeft(Position k2) / LL 旋转Position k1;k1=k2-left;k2-left=k1-right;k1-right=k2;/ 因为比较的是左右孩子的高度，所以求父节点的高度要加 1k2-Height=Max(Height(k2-left),Height(k2-right) + 1;k1-Height=Max(Height(k1-left),Height(k2-right) + 1; return
6、 k1;/* 此函数用于 k1 只有一个右孩子的单旋转，* 在 K1 和它的右孩子之间旋转，* 更新高度，返回新的根节点*/static Position SingleRotateWithRight(Position k1) / RR 旋转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-left),Height(k2-right) + 1;retu
7、rn k2;/* 此函数用于当 如果 k3 有一个左孩子，以及* 它的左孩子又有右孩子，执行这个双旋转* 更新高度，返回新的根节点*/static Position DoubleRotateLeft(Position k3) / LR 旋转逆时针顺时针 /在 k3 的左孩子，执行右侧单旋转k3-left=SingleRotateWithRight(k3-left);/ 再对 k3 进行 左侧单旋转return SingleRotateWithLeft(k3);/* 此函数用于当 如果 k4 有一个右孩子，以及* 它的右孩子又有左孩子，执行这个双旋转* 更新高度，返回新的根节点*/static
8、Position DoubleRotateRight(Position k4) / RL 旋转/在 k4 的右孩子，执行左侧单旋转k4-right = SingleRotateWithLeft(k4-right);/ 再对 k4 进行 右侧单旋转return SingleRotateWithRight(k4);/* 向 AVL 树插入可以通过如同它是未平衡的二叉查找树一样把给定的值插入树中，* 接着自底向上向根节点折回，于在插入期间成为不平衡的所有节点上进行旋转来完成。* 因为折回到根节点的路途上最多有 1.5 乘 log n 个节点，而每次 AVL 旋转都耗费恒定的时间，* 插入处理在整体上
9、耗费 O(log n) 时间。*/AvlTree Insert(ElementType x,AvlTree T)/如果 T 不存在，则创建一个节点树if(T = NULL)T = (AvlTree)malloc(sizeof(struct AvlNode);T-data = x;T-Height = 0;T-left = T-right = NULL;/ 如果要插入的元素小于当前元素else if(x data)/递归插入T-left=Insert(x,T-left);/插入元素之后，若 T 的左子树比右子树高度 之差是 2，即不满足 AVL 平衡特性，需要调整if(Height(T-left
10、) - Height(T-right) = 2)/把 x 插入到了 T-left 的左侧，只需 左侧单旋转if(x left-data)T = SingleRotateWithLeft(T); / LL 旋转else/ x 插入到了 T-left 的右侧，需要左侧双旋转 T = DoubleRotateLeft(T); / LR 旋转/ 如果要插入的元素大于当前元素else if(x T-data)T-right=Insert(x,T-right);if(Height(T-right) - Height(T-left) = 2)if(x T-right-data)T = SingleRotat
11、eWithRight(T); /RR 旋转elseT = DoubleRotateRight(T); /RL 旋转T-Height=Max(Height(T-left),Height(T-right) + 1;return T;/* 对单个节点进行的 AVL 调整*/AvlTree Rotate(AvlTree T)if(Height(T-left) - Height(T-right) = 2) if(Height(T-left-left) = Height(T-left-right)T = SingleRotateWithLeft(T); / LL 旋转elseT = DoubleRotat
12、eLeft(T); / LR 旋转if(Height(T-right) - Height(T-left) = 2)if(Height(T-right-right) = Height(T-right-left)T = SingleRotateWithRight(T); / RR 旋转elseT = DoubleRotateRight(T); / RL 旋转return T;/* 首先定位要删除的节点，然后用该节点的右孩子的最左孩子替换该节点，* 并重新调整以该节点为根的子树为 AVL 树，具体调整方法跟插入数据类似* 删除处理在整体上耗费 O(log n) 时间。*/AvlTree Delete
13、(ElementType x,AvlTree T)if(T = NULL)return NULL;if(T-data = x) / 要删除的 x 等于当前节点元素 if(T-right = NULL ) / 若所要删除的节点 T 的右孩子为空,则直接删除AvlTree tmp = T;T = T-left;free(tmp);else /* 否则找到 T-right 的最左儿子代替 T */AvlTree tmp = T-right;while(tmp-left)tmp=tmp-left;T-data = tmp-data;/* 对于替代后的 T 即其字节点进行调整*/T-right = De
14、lete(T-data,T-right);T-Height = Max(Height(T-left),Height(T-right)+1;return T;else if(x T-data) / 要删除的 x 大于当前节点元素，在 T的右子树中查找删除T-right=Delete(x,T-right);else / 要删除的 x 小于当前节点元素，在 T 的左子树中查找删除 T-left=Delete(x,T-left);/* 当删除元素后调整平衡*/T-Height=Max(Height(T-left),Height(T-right) + 1;if(T-left != NULL)T-left = Rotate(T-left);if(T-right != NULL)T-right = Rotate(T-right);if(T)T=Rotate(T);return T;/* 返回当前位置的元素*/ElementType Retrieve(Position P)return P-data;/* 遍历输出*/void Display(AvlTree T)static int n=0;if(NULL != T)Display(T-left);printf(%d ndata=%d n,+n,T-dat
