首页 > 代码库 > AVL平衡树的插入例程
AVL平衡树的插入例程
/* **AVL平衡树插入例程 **2014-5-30 11:44:50 */ avlTree insert(elementType X, avlTree T){ if(T == NULL){ T = malloc(sizeof(struct avlTree)); if(T == NULL) fatalError("Out of space!!!"); T->element = X; T->height = 0; T->left = T->right = 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); } } /*--如果X已经存在,那么啥都不用做--*/ T->height = max(height(T->left), height(T->right)) + 1; return T; } static position singleRotateWithLeft(position k2){ position 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; } /*双右左旋就是先对T的右子树左单旋再对T本身右单旋*/ static position
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。