#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef struct Node{ Node *l, *r; int v; Node(){l = NULL; r = NULL;} }*tree, Node; tree build(tree p, int v){ if(p == NULL){ p = new Node(); p->v = v; return p; } if(v < p->v) p->l = build(p->l, v); else if(v > p->v) p->r = build(p->r, v); else return p; return p; } void Delete(tree &T, int k){ Node *p = T; Node *q, *s, *f; f = NULL; while(p){ if(p->v == k){ break; } f = p; if(k < p->v){ p = p->l; } else{ p = p->r; } } q = p; if(!p)return; if(p->l && p->r){ p = p->l; while(p->r){ s = p; p = p->r; } q->v = p->v; s->r = p->l; delete(p); return; } else if(p->l){ q = p; p = p->l; } else{ q = p; p = p->r; } //cout << "*" << endl; if(!f)T = p; else if(q == f->l)f->l = p; else f->r = p; delete(q); } void InOrder(tree p){ if(p == NULL)return; InOrder(p->l); printf("%d ", p->v); InOrder(p->r); } int main(){ int N; while(~scanf("%d", &N)){ tree p; p = NULL; int v; for(int i = 0; i < N; i++){ scanf("%d", &v); p = build(p, v); } InOrder(p); int m; scanf("%d", &m); for(int i = 0; i < m; i++){ scanf("%d", &v); Delete(p, v); InOrder(p); } } return 0; }
1） 对α的左儿子的左子树进行一次插入（左旋）
其中D是新插入的节点，红色节点K2是失去平衡的节点。需要对K1和K2进行左旋调整即将K1作为根，将K2作为K1的左子树，K1的右子树调整为K2的左子树。如下图所示
2）对α的右儿子的右子树进行一次插入（右旋）
将K2的右子树更改为K1的左子树，K1的左子树更改为K2即完成的右旋，如下图所示
3）对α的左儿子的右子树进行一次插入（左右双旋）
左右双旋这里的左右指的是对α的左儿子的右子树进行插入时需要旋转。先对K1和K2进行右旋（跟第四种情况类似），然后再对K3和K2进行左旋，最终实现平衡。如下图所示
4）对α的右儿子的左子树进行一次插入（右左双旋）
右左双旋：先对K1和K2进行左旋，然后在对K2和K3进行右旋，最终实现平衡。如下图所示
平衡树：
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; struct TreeNode{ int v; int H; struct TreeNode *l; struct TreeNode *r; }; typedef struct TreeNode *AvlTree, *Position; AvlTree FreeTree(AvlTree T){ if(T != NULL){ FreeTree(T->l); FreeTree(T->r); delete(T); } return NULL; } int Height(Position p){ if(p == NULL) return -1; return p->H; } void pushup(Position &K){ K->H = max(Height(K->l), Height(K->r)) + 1; } Position SingleRotateWithLeft(Position K2){ Position K1 = K2->l; K2->l = K1->r; K1->r = K2; pushup(K1); pushup(K2); return K1; } Position SingleRotateWithRight(Position K2){ Position K1 = K2->r; K2->r = K1->l; K1->l = K2; pushup(K1); pushup(K2); return K1; } Position DoubleRotateWithLeft(Position K3){ K3->l = SingleRotateWithRight(K3->l); K3 = SingleRotateWithLeft(K3); } Position DoubleRotateWithRight(Position K3){ K3->r = SingleRotateWithLeft(K3->r); K3 = SingleRotateWithRight(K3); } AvlTree insert(int x, AvlTree T){ if(T == NULL){ T = new TreeNode(); T->v = x; T->H = 0; T->l = T->r = NULL; } else if(x < T->v){ T->l = insert(x, T->l); if(Height(T->l) - Height(T->r) == 2){ if(x < T->l->v) T = SingleRotateWithLeft(T); else T = DoubleRotateWithLeft(T); } } else if(x > T->v){ T->r = insert(x, T->r); if(Height(T->r) - Height(T->l) == 2){ if(x > T->r->v) T = SingleRotateWithRight(T); else T = DoubleRotateWithRight(T); } } pushup(T); return T; } AvlTree Visit(int X, AvlTree T){ if(T == NULL) return NULL; if(X < T->v) return Visit(X, T->l); if(X > T->v) return Visit(X, T->r); return T; } void PreVisit(AvlTree T){ if(T == NULL) return; printf("%d ", T->v); PreVisit(T->l); PreVisit(T->r); } void InVisit(AvlTree T){ if(T == NULL) return; InVisit(T->l); printf("%d ", T->v); InVisit(T->r); } int main(){ AvlTree T = FreeTree(NULL); // puts("**"); int i; for(i = 1; i <= 7; i++) T = insert(i, T); for(i = 16; i >= 10; i--) T = insert(i, T); T = insert(8, T); T = insert(9, T); printf("InOrder: "); InVisit(T); printf(" PreOrder: "); PreVisit(T); putchar(' '); return 0; }
参考博客：http://blog.csdn.net/zitong_ccnu/article/details/11097663#