数据结构-AVL树

AVL树：带有平衡条件的二叉查找树，要求每个节点的左子树和右子树的高度最多差1。

通常，AVL树通过旋转操作保持平衡条件。

不平衡的可能情况：

节点a的左儿子左子树进行插入节点a的右儿子右子树进行插入节点a的左儿子右子树进行插入节点a的右儿子左子树进行插入

其中情况1、2都是通过单旋转就可以解决了，而情况3、4需要通过双旋转来解决。

AVL树的声明：

struct avlNode; typedef struct avlNode* position; typedef struct avlNode* avlTree; struct avlNode { int element; avlTree left; avlTree right; int height; }; int max(int i, int j); position singleRotateWithLeft(position k2); position singleRotateWithRight(position k2); position doubleRotateWithLeft(position k3); position doubleRotateWithRight(position k3); avlTree Insert(int x, avlTree t); void printTree(avlTree t); 单旋转的实现：

position singleRotateWithLeft(position k2){ position k1; k1 = k2->left; k2->left = k1->right; k1->right = k2; if ((k2->left == NULL) && (k2->right == NULL)) k2->height = 0; else if (k2->left == NULL) k2->height = k2->right->height + 1; else if (k2->right == NULL) k2->height = k2->left->height + 1; else k2->height = max(k2->left->height, k2->right->height) + 1; k1->height = max(k1->right->height, k2->height) + 1; return k1; }//对应情况1 position singleRotateWithRight(position k2){ position k1; k1=k2->right; k2->right = k1->left; k1->left = k2; if ((k2->left == NULL) && (k2->right == NULL)) k2->height = 0; else if (k2->left == NULL) k2->height = k2->right->height + 1; else if (k2->right == NULL) k2->height = k2->left->height + 1; else k2->height = max(k2->left->height, k2->right->height) + 1; k1->height = max(k1->right->height, k2->height) + 1; return k1; }//对应情况2 其中，我对单旋转的理解就是沿着树倾斜的角度小的方向向下掰就可以了。

双旋转的实现：

position doubleRotateWithLeft(position k3){ k3->left = singleRotateWithRight(k3->right); return singleRotateWithLeft(k3); }//对应情况3 position doubleRotateWithRight(position k3){ k3->right = singleRotateWithLeft(k3->right); return singleRotateWithRight(k3); }//对应情况4 双旋转就是进行两次旋转

AVL的插入操作的实现：

avlTree Insert(int x, avlTree t){ if (t==NULL) { t = (struct avlNode *)malloc(sizeof(struct avlNode)); if (t == NULL) cout << "Out of space!!!" << endl; else { t->element = x; t->height = 0; t->left = t->right = NULL; } } else if (x<t->element) { t->left = Insert(x, t->left); if (t->right==NULL) { if (t->left->height == 1) { if (x < t->left->element) t = singleRotateWithLeft(t); else t = doubleRotateWithLeft(t); } } else if (t->left->height - t->right->height == 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 (t->left == NULL) { if (t->right->height == 1) { if (x < t->right->element) t = singleRotateWithLeft(t); else t = doubleRotateWithLeft(t); } } else if (t->right->height-t->left->height==2) { if (x > t->right->element) t = singleRotateWithRight(t); else t = doubleRotateWithRight(t); } } return t; } 打印树的实现：

void printTree(avlTree t){ if (t==NULL) { cout << " "; } else { printTree(t->left); cout << t->element; printTree(t->right); } } max函数的实现：

int max(int i, int j){ if (i > j) return i; else return j; } 伸展树（splay tree）：伸展树保证从空树开始任意连续M次对树的操作最多花费O(M㏒N)时间。

基本想法为：当一个树被访问后，它就要经过一系列AVL树的旋转被放到根上。如果一个节点很深，那么其路径上就存在许多的节点也相对较深，通过重新构造可以使所有这些节点的进一步访问所花费的时间变少。

伸展（splaying）：

若x的父节点是树根，那么我们只需要旋转x和树根；若x有父亲节点和祖父节点，则分为“之”字形和“一”字形两种情况。