|
cur; if (cur->bf == EH) { parent->bf = EH; child->bf = EH; } else if (cur->bf == LH) { parent->bf = EH; child->bf = RH; } else { parent->bf = LH; child->bf = EH; } cur->bf = EH; } /* RR */ else { child->parent = parent->parent; parent->rchild = child->lchild; if (child->lchild != NULL) child->lchild->parent = parent; child->lchild = parent; if (parent->parent != NULL) { if (parent->parent->lchild == parent) { parent->parent->lchild = child; } else { parent->parent->rchild = child; } } else { root = child; } parent->parent = child; /* when insert */ if (child->bf == RH) { child->bf = EH; parent->bf = EH; } /* when delete*/ else { child->bf = LH; parent->bf = RH; } } return root; } BSTNode* insertNode(ElemType key, BSTNode* root) { BSTNode *parent = NULL, *cur = NULL, *child = NULL; assert (root != NULL); /* node exists*/ if (searchAVL(root,key,&parent)) { return root; } cur = (BSTNode*)malloc(sizeof(BSTNode)); cur->parent = parent; cur->key = key; cur->lchild = NULL; cur->rchild = NULL; cur->bf = EH; if (key
key) { parent->lchild = cur; child = parent->lchild; } else { parent->rchild = cur; child = parent->rchild; } /*get the minimax tree needed to be adjusted*/ while ((parent != NULL)) { if (child == parent->lchild) { if (parent->bf == RH) { parent->bf = EH; return root; } else if (parent->bf == EH) { root = leftbalance(root, parent, child); break; } else { parent->bf = LH; child = parent; parent = parent->parent; } } else { if (parent->bf == LH) //是右孩子，不会引起不平衡 { parent->bf = EH; return root; } else if (parent->bf == RH) //是右孩子，并且引起parent的不平衡 { root = rightbalance(root, parent, child); break; } else //是右孩子，并且可能引起parent的parent的不平衡 { parent->bf = RH; child = parent; parent = parent->parent; } } } return root; } BSTNode* deleteNode(ElemType key, BSTNode* root) { BSTNode *dNode=NULL, *parent=NULL, *child = NULL; ElemType temp; assert(root!=NULL); if (!searchAVL(root,key,&parent)) { return root; } if (parent == NULL) { dNode = root; } else if ((parent->lchild!=NULL)&&(parent->lchild->key==key)) { dNode = parent->lchild; } else { dNode = parent->rchild; } child = dNode; while ((child->lchild!=NULL)||(child->rchild!=NULL)) //确定需要删除的结点 { if (child->bf == LH) { child = preNode(dNode); } else { child = nextNode(dNode); } temp = child->key; child->key = dNode->key; dNode->key = temp; dNode = child; } child = dNode; parent = dNode->parent; while ((parent != NULL)) //查找需要调整的最小子树 { if (child == parent->lchild) { if (parent->bf == LH) { parent->bf = EH; child = parent; parent = parent->parent; } else if (parent->bf == RH) { child = parent->rchild; root = rightbalance(root, parent, child); break; } else { parent->bf = RH; break; } } else { if (parent->bf == RH) { parent->bf = EH; child = parent; parent = parent->parent; } else if (parent->bf == LH) { child = parent->lchild; root = leftbalance(root, parent, child); break; } else { parent->bf = LH; break; } } } if (dNode->parent != NULL) { if (dNode == dNode->parent->lchild) { dNode->parent->lchild = NULL; } else { dNode->parent->rchild = NULL; } } free(dNode); dNode = NULL; if (root == dNode) { root = NULL; //root被删除, 避免野指针 } return root; } BSTNode* createAVL(int *data, int size) { int i, j; BSTNode *root; if (size<1) { return NULL; } root = (BSTNode*)malloc(sizeof(BSTNode)); root->parent = NULL; root->lchild = NULL; root->rchild = NULL; root->key = data[0]; root->bf = 0; for(i=1;i
lchild); destroyAVL(root->rchild); free(root); root=NULL; } } void InOrderTraverse(BSTree root) { if(NULL != root) { InOrderTraverse(root->lchild); printf("%d\t",root->key); InOrderTraverse(root->rchild); } } void PreOrderTraverse(BSTree root) |