平衡树
作者:
若雨
,
2024-10-29 19:16:08
,
所有人可见
,
阅读 2
typedef struct Node
{
int key;
struct Node *left;
struct Node *right;
int height;
} Node;
int max(int a, int b)
{
return a > b ? a : b;
}
int height(Node *root)
{
if (root == NULL)
return 0;
return 1 + max(height(root->left), height(root->right));
}
Node *newNode(int key)
{
Node *node = (Node *)malloc(sizeof(Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 0;
return node;
}
int getBalanceFactor(Node *node)
{
if (node == NULL)
return 0;
return height(node->left) - height(node->right);
}
Node *rightRotate(Node *y)
{
Node *x = y->left;
Node *xr = x->right;
x->right = y;
y->left = xr;
x->height = height(x);
y->height = height(y);
return x;
}
Node *leftRotate(Node *y)
{
Node *x = y->right;
Node *xl = x->left;
x->left = y;
y->right = xl;
x->height = height(x);
y->height = height(y);
return x;
}
Node *insert(Node *node, int key)
{
if (node == NULL)
return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else
return node;
node->height = height(node);
int bf = getBalanceFactor(node);
if (bf > 1 && key < node->left->key)
return rightRotate(node);
if (bf < -1 && key > node->right->key)
return leftRotate(node);
if (bf > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (bf < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
void preOrder(Node *root)
{
if (root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
int main(int argc, char const *argv[])
{
struct Node *root = NULL;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
printf("Preorder traversal of the constructed AVL tree is \n");
preOrder(root);
putchar('\n');
return 0;
}