AVL树, 平衡二叉搜索树, 平衡二叉树
AVL树, 平衡二叉搜索树, 平衡二叉树
#include <stdio.h> #include <stdlib.h> #include <time.h> #define max(a, b) ((a) > (b) ? (a) : (b)) typedef struct Node { int key, height; struct Node *rchild, *lchild; } Node; Node __NIL; #define NIL (&__NIL) __attribute__((constructor)) void init_NIL() { NIL->height = 0, NIL->key = -1; NIL->rchild = NIL->lchild = NIL; return ; } Node *getNewNode(int k) { Node *p = (Node *)malloc(sizeof(Node)); p->key = k, p->height = 1; p->rchild = p->lchild = NIL; return p; } void update_height(Node *root) { root->height = max(root->lchild->height, root->rchild->height) + 1; return ; } Node *right_rotate(Node *root) { Node *temp = root->lchild; root->lchild = temp->rchild; temp->rchild = root; update_height(root); update_height(temp); return temp; } Node *left_rotate(Node *root) { Node *temp = root->rchild; root->rchild = temp->lchild; temp->lchild = root; update_height(root); update_height(temp); return temp; } Node *maintain(Node *root) { if (root == NIL) return root; if (abs(root->lchild->height - root->rchild->height) > 1) if (root->lchild->height > root->rchild->height) root->lchild->lchild->height < root->lchild->rchild->height && (root = left_rotate(root->lchild)), root = right_rotate(root); else root->rchild->rchild->height < root->rchild->lchild->height && (root = right_rotate(root->rchild)), root = left_rotate(root); return root; } Node *insert(Node *root, int k) { if (root == NIL) return getNewNode(k); if (root->key == k) return root; k > root->key && (root->rchild = insert(root->rchild, k), 1) || (root->lchild = insert(root->lchild, k)); update_height(root); return maintain(root); } void clear(Node *root) { if (root == NIL) return ; clear(root->lchild); clear(root->rchild); free(root); return ; } Node *predecessor(Node *root) { root = root->lchild; while (root->rchild != NIL) root = root->rchild; return root; } Node *erase(Node *root, int k) { if (root == NIL) return root; root->key > k && (root->lchild = erase(root->lchild, k)); root->key < k && (root->rchild = erase(root->rchild, k)); if (root->key == k) { if (root->rchild == NIL || root->lchild == NIL) { Node *p = root->rchild == NIL ? root->lchild : root->rchild; free(root); return p; } else { Node *p = predecessor(root); root->key = p->key; root->lchild = erase(root->lchild, p->key); } } update_height(root); return maintain(root); } void output(Node *root) { if (root == NIL) return ; printf("%d(%d, %d)\n", root->key, root->lchild->key, root->rchild->key); output(root->lchild); output(root->rchild); return ; } int main() { srand(time(0)); int ans; scanf("%d", &ans); Node *root = NIL; for (int i = 0; i < ans; i++) { root = insert(root, rand() % 100); } output(root); int s = rand() % 100; printf("%d erase\n", s); erase(root, s); output(root); return 0; }
AVL树, 平衡二叉搜索树, 平衡二叉树
原文:https://www.cnblogs.com/hhhahh/p/14815628.html