环境
$ cat /proc/version
Linux version 6.8.0-45-generic (buildd@lcy02-amd64-115) (x86_64-linux-gnu-gcc-13 (Ubuntu 13.2.0-23ubuntu4) 13.2.0, GNU ld (GNU Binutils for Ubuntu) 2.42) #45-Ubuntu SMP PREEMPT_DYNAMIC Fri Aug 30 12:02:04 UTC 2024
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
struct node
{
int key;
int height;
struct node *left;
struct node *right;
};
int height(struct node *node)
{
if(node == NULL)
{
return 0;
}
return node->height;
}
int max(int a, int b)
{
return a > b ? a : b;
}
struct node *leftRotate(struct node *node)
{
/*
1
\
3
/
2
3
/
1
\
2
*/
struct node *root = node->right;
node->right = root->left;
root->left = node;
node->height = max(height(node->left), height(node->right)) + 1;
root->height = max(height(root->left), height(root->right)) + 1 ;
return root;
}
/*
3
/
1
\
2
1
\
3
/
2
*/
struct node *rightRotate(struct node *node)
{
struct node *root = node->left;
node->left = root->right;
root->right = node;
node->height = max(height(node->left), height(node->right)) + 1;
root->height = max(height(root->left), height(root->right)) + 1 ;
return root;
}
int getBalance(struct node *node)
{
return height(node->left) - height(node->right);
}
struct node *insertNode(struct node *root, int key)
{
if(root == NULL)
{
root = malloc(sizeof(*root));
root->key = key;
root->height = 1;
root->left = NULL;
root->right = NULL;
return root;
}
else if(key < root->key)
{
root->left = insertNode(root->left, key);
}
else if(key > root->key)
{
root->right = insertNode(root->right, key);
}
else
{
assert(0);
return root;
}
root->height = max(height(root->left), height(root->right)) + 1;
int bf = getBalance(root);
/*
3 3 2
/ / / \
2 2 1 3
/ /
1 1
*/
if(bf > 1 && key < root->left->key)
{
return rightRotate(root);
}
/*
1 1 2
\ \ / \
2 2 1 3
\ \
3 3
*/
else if(bf < -1 && key > root->right->key)
{
return leftRotate(root);
}
/*
3 3 2
/ / / \
1 2 1 3
\ /
2 1
*/
else if(bf > 1 && key > root->left->key)
{
root->left = leftRotate(root->left);
return rightRotate(root);
}
/*
1 1 2
\ \ / \
3 2 1 3
/ \
2 3
*/
else if(bf < -1 && key < root->right->key)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}
else
{}
return root;
}
struct node *getMinValueNode(struct node *node)
{
struct node *tmp = node;
while(1)
{
if(tmp->left == NULL)
{
break;
}
else
{
tmp = tmp->left;
}
}
return tmp;
}
void inOrder(struct node *node)
{
if(node == NULL)
{
return;
}
inOrder(node->left);
printf("%d ", node->key);
inOrder(node->right);
}
int main(int argc, char *argv[])
{
struct node *root = NULL;
root = insertNode(root, 0);
assert(root->key == 0);
assert(root->left == NULL);
assert(root->right == NULL);
root = insertNode(root, 1);
assert(root->height == 2);
assert(root->key == 0);
assert(root->left == NULL);
assert(root->right->key == 1);
/*
0
\
1
*/
root = insertNode(root, 3);
assert(root->height == 2);
assert(root->key == 1);
assert(root->left->key == 0);
assert(root->right->key == 3);
/*
0 0 1
\ \ / \
1 1 0 3
\
3
*/
root = insertNode(root, 9);
assert(root->height == 3);
assert(root->key == 1);
assert(root->left->key == 0);
assert(root->right->key == 3);
assert(root->right->right->key == 9);
/*
0 0 1 1
\ \ / \ / \
1 1 0 3 0 3
\ \
3 9
*/
root = insertNode(root, 2);
assert(root->height == 3);
assert(root->key == 1);
assert(root->left->key == 0);
assert(root->right->key == 3);
assert(root->right->left->key == 2);
assert(root->right->right->key == 9);
/*
0 0 1 1 1
\ \ / \ / \ / \
1 1 0 3 0 3 0 3
\ \ / \
3 9 2 9
*/
root = insertNode(root, 8);
assert(root->height == 3);
assert(root->key == 3);
assert(root->left->key == 1);
assert(root->left->left->key == 0);
assert(root->left->right->key == 2);
assert(root->right->key == 9);
assert(root->right->left->key == 8);
/*
0 0 1 1 1 1 3
\ \ / \ / \ / \ / \ / \
1 1 0 3 0 3 0 3 0 3 1 9
\ \ / \ / \ / \ /
3 9 2 9 2 9 0 2 8
/
8
*/
inOrder(root);
printf("\n");
return 0;
}
<完>