平衡二叉查找树是很早出现的平衡树,因为所有子树的高度差不超过1,所以操作平均为O(logN)。
平衡二叉查找树和BS树很像,插入和删除操作也基本一样,但是每个节点多了一个高度的信息,在每次插入之后都要更新树的每个节点的高度,发现不平衡之后就要进行旋转。
单旋转是碰到左左或者右右的情况下所使用的方法。
例如:
3
2
1
这种情况就需要旋转,因为3是根节点,它的左子树高度为0,右子树高度为2,相差超过1了,所以要进行旋转,而这是右右的情况,所以是单旋转。
2
/ 1 3
这样子旋转过后就可以了~
双旋转也很简单,但代码操作会稍微麻烦一点:
2
4
/
3
遇到这种情况就是双旋转,因为3是在2 4之间的。
旋转过后:
3
/ 2 4
这样子就可以了。。其实很多时候情况比这个复杂,但是本质都是这样子操作的。
// // AVL.h // AVL // // Created by Alps on 14-8-7. // Copyright (c) 2014年 chen. All rights reserved. // #ifndef AVL_AVL_h #define AVL_AVL_h #define ElementType int struct TreeNode; typedef TreeNode* AVL; typedef TreeNode* Position; Position Find(ElementType key, AVL A); Position FindMax(AVL A); Position FindMin(AVL A); AVL Insert(ElementType key, AVL A); AVL Delete(ElementType key, AVL A); struct TreeNode{ ElementType element; AVL left; AVL right; int height; }; #endif
// // main.cpp // AVL // // Created by Alps on 14-8-7. // Copyright (c) 2014年 chen. All rights reserved. // #include <iostream> #include "AVL.h" int Height(AVL A){//求节点高度 if (A == NULL) { return -1; }else{ return A->height; } } int MAX(int a, int b){//返回两数中的大数 return a>b?a:b; } AVL SingleRotateWithRight(AVL A){//右单旋转 AVL tmp = A->right; A->right = tmp->left; tmp->left = A; A->height = MAX(Height(A->left), Height(A->right))+1; tmp->height = MAX(Height(tmp->left), Height(tmp->right))+1; return tmp; } AVL DoubleRotateWithRight(AVL A){//右双旋转 AVL tmp = A->right; AVL tmp1 = tmp->left; tmp->left = tmp1->right; A->right = tmp1->left; tmp1->right = tmp; tmp1->left = A; tmp->height = MAX(Height(tmp->left), Height(tmp->right))+1; A->height = MAX(Height(A->left), Height(A->right))+1; tmp1->height = MAX(Height(tmp1->left), Height(tmp1->right))+1; return tmp1; } AVL SingleRotateWithLeft(AVL A){//左单旋转 AVL tmp = A->left; A->left = tmp->right; tmp->right = A; A->height = MAX(Height(A->left), Height(A->right))+1; tmp->height = MAX(Height(tmp->left), Height(tmp->right))+1; return tmp; } AVL DoubleRotateWithLeft(AVL A){//左双旋转 AVL tmp = A->left; AVL tmp1 = tmp->right; tmp->right = tmp1->left; A->left = tmp1->right; tmp1->left = tmp; tmp1->right = A; tmp->height = MAX(Height(tmp->left), Height(tmp->right))+1; A->height = MAX(Height(A->left), Height(A->right))+1; tmp1->height = MAX(Height(tmp1->left), Height(tmp1->right))+1; return tmp1; } AVL Insert(ElementType key, AVL A){//插入元素 if (A == NULL) { A = (AVL)malloc(sizeof(struct TreeNode)); A->element = key; A->height = 0; A->right = NULL; A->left = NULL; // return A; }else{ if (key > A->element) {//如果大于当前节点,向右子树插入 A->right = Insert(key, A->right); if (Height(A->right) - Height(A->left) == 2) { if (key > A->right->element) {//如果插入到节点的右子树的右方,右单旋转 A = SingleRotateWithRight(A); }else{ A = DoubleRotateWithRight(A);//插入到当前节点右子树的左方,右双旋转 } } }else if (key < A->element) { A->left = Insert(key, A->left); if (Height(A->left) - Height(A->right) == 2) { if (key < A->left->element) {//左单旋转 A = SingleRotateWithLeft(A); }else{ A = DoubleRotateWithLeft(A); } } } } A->height = MAX(Height(A->left), Height(A->right))+1; return A; } Position FindMax(AVL A){//找到当前树的最大值 AVL tmp = A; if (A == NULL) { return NULL; }else{ while (tmp->right != NULL) { tmp = tmp->right; } } return tmp; } Position FindMin(AVL A){//找到当前树的最小值 AVL tmp = A; if (A == NULL) { return NULL; }else{ while (tmp->left != NULL) { tmp = tmp->left; } } return tmp; } Position Find(ElementType key,AVL A){//查找节点,返回节点指针 AVL tmp = A; if (A == NULL) { return NULL; }else{ while (tmp != NULL && tmp->element != key) { if (key > tmp->element) { tmp = tmp->right; }else{ tmp = tmp->left; } } } return tmp; } AVL Delete(ElementType key, AVL A){//删除节点 if (A == NULL || Find(key, A) == NULL) { return NULL; }else{ if (key == A->element) {//如果找到了要删除的节点 AVL tmp; if (A->left && A->right) {//如果要删除的节点有左右子树 tmp = FindMin(A->left);//用当前节点左子树的最小值替换 A->element = tmp->element; A->left = Delete(A->element, A->left);//删掉左子树最小值节点 }else{ tmp = A; if (A->left) { A = A->left;//<span style="font-family: Arial, Helvetica, sans-serif;">如果只存在左子树,直接返回它的左子树节点</span> }else{ if (A->right) { A = A->right; //<span style="font-family: Arial, Helvetica, sans-serif;">如果只存在右子树,直接返回它的右子树节点</span> }else{ A = NULL;//删除的是叶子节点,直接赋值为NULL } } free(tmp); tmp = NULL; return A;//返回删除后的节点 } }else{ if (key > A->element) {//如果大于,去右子树 A->right = Delete(key, A->right); if (Height(A->left) - Height(A->right) == 2) { if (A->left->right != NULL && (Height(A->left->right) > Height(A->left->left))) {//如果当前节点不平衡,且节点左孩子存在右孩子,双旋转 A = DoubleRotateWithLeft(A); }else{ A = SingleRotateWithLeft(A);//否则单旋转 } } // A->height = MAX(Height(A->left), Height(A->right)); }else{ if (key < A->element) { A->left = Delete(key, A->left); if (Height(A->right) - Height(A->left) == 2) { if (A->right->left != NULL && (Height(A->right->left) > Height(A->right->right))) {// A = DoubleRotateWithRight(A); }else{ A = SingleRotateWithRight(A); } } // A->height = MAX(Height(A->left), Height(A->right)); } } } } A->height = MAX(Height(A->left), Height(A->right))+1; return A; } int main(int argc, const char * argv[]) { AVL A = NULL; A = Insert(3, A); printf("%d %d\n",A->element,A->height); A = Insert(2, A); printf("%d %d\n",A->left->element,A->height); A = Insert(1, A); printf("%d %d\n",A->left->element,A->left->height); A = Insert(4, A); A = Insert(5, A); printf("%d %d\n",A->right->element,A->right->height); A = Insert(6, A); printf("%d %d\n",A->element,A->height); A = Insert(7, A); A = Insert(16, A); A = Insert(15, A); printf("%d %d\n",A->right->element,A->right->height); A = Insert(14, A); printf("%d %d\n",A->right->element,A->right->height); A = Delete(16, A); printf("%d %d\n",A->right->element,A->right->height); A = Delete(6, A); A = Delete(5, A); printf("%d %d\n",A->right->element,A->right->height); return 0; }
算法学习 - 平衡二叉查找树实现(AVL树),布布扣,bubuko.com
原文:http://blog.csdn.net/alps1992/article/details/38464793