-
-
Save lsem/db90894a73bdb7a53333 to your computer and use it in GitHub Desktop.
AVL Tree. Just for execrcise.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <cstdlib> | |
#include <cstdio> | |
#include <cassert> | |
#include <utility> | |
#include <algorithm> | |
struct AVLTreeNode | |
{ | |
int height; | |
AVLTreeNode *left; | |
AVLTreeNode *right; | |
int key; | |
}; | |
AVLTreeNode *avl_create_new_node(int key, AVLTreeNode *left, AVLTreeNode *right) | |
{ | |
AVLTreeNode *result = new AVLTreeNode {}; | |
result->key = key; | |
result->left = left; | |
result->right = right; | |
result->height = 1; | |
return result; | |
} | |
struct AVLTree | |
{ | |
AVLTreeNode *rootNode; | |
}; | |
void avl_init(AVLTree **self) | |
{ | |
*self = new AVLTree {}; | |
(*self)->rootNode = nullptr; | |
} | |
void avl_free(AVLTree **self) | |
{ | |
// ... (free all nodes) | |
// delete (*self)->rootNode; | |
delete *self; | |
*self = nullptr; | |
} | |
int avl_node_height(AVLTreeNode *node) | |
{ | |
if (!node) | |
return 0; | |
return node->height; | |
} | |
AVLTreeNode *avl_insert_node(AVLTreeNode *tree, int key); | |
void avl_insert(AVLTree *self, int key) | |
{ | |
self->rootNode = avl_insert_node(self->rootNode, key); | |
} | |
int get_balance_factor(AVLTreeNode *tree) | |
{ | |
if (tree == nullptr) | |
return 0; | |
return avl_node_height(tree->left) - avl_node_height(tree->right); | |
} | |
AVLTreeNode *avl_rotate_ll(AVLTreeNode *node_to_rotate); | |
AVLTreeNode *avl_rotate_lr(AVLTreeNode *node_to_rotate); | |
AVLTreeNode *avl_rotate_rr(AVLTreeNode *node_to_rotate); | |
AVLTreeNode *avl_rotate_rl(AVLTreeNode *node_to_rotate); | |
AVLTreeNode *avl_insert_node(AVLTreeNode *tree, int key) | |
{ | |
if (tree == nullptr) | |
{ | |
printf("created new node with key %d\n", key); | |
return avl_create_new_node(key, nullptr, nullptr); | |
} | |
if (key < tree->key) | |
tree->left = avl_insert_node(tree->left, key); | |
else | |
tree->right = avl_insert_node(tree->right, key); | |
// Update height of this node | |
tree->height = std::max(avl_node_height(tree->left), avl_node_height(tree->right)) + 1; | |
// printf("new height %d\n", tree->height); | |
// Check balancing | |
int balance_factor = get_balance_factor(tree); | |
std::printf("after insertion %d key, balance factor of node %d is: %d\n", key, tree->key, balance_factor); | |
// Find out what case from four possible: ll, rr, lr, rl. | |
assert(balance_factor > -3 && balance_factor < 3); // -2..2 should be a vaild range | |
enum UnbalanceKind { UK_Unknown, UK_LL, UK_LR, UK_RR, UK_RL, UK__END }; | |
const char *UnbalanceKindNames[UK__END] = {"UNKNOWN", "LL", "LR", "RR", "RL"}; | |
unsigned unbalance_kind_happened = UK_Unknown; | |
if (balance_factor == -2) | |
{ | |
// right subtree has grown up | |
if (key < tree->right->key) | |
{ | |
unbalance_kind_happened = UK_RL; | |
} | |
else | |
{ | |
unbalance_kind_happened = UK_RR; | |
} | |
} | |
else if (balance_factor == +2) | |
{ | |
if (key > tree->left->key) | |
{ | |
unbalance_kind_happened = UK_LR; | |
} | |
else | |
{ | |
unbalance_kind_happened = UK_LL; | |
} | |
} | |
if (unbalance_kind_happened == UK_Unknown) | |
{ | |
// No balance needed | |
return tree; | |
} | |
// std::printf("Unbalancing kind happened: %s\n", UnbalanceKindNames[unbalance_kind_happened]); | |
switch(unbalance_kind_happened) | |
{ | |
case UK_LL: | |
{ | |
tree = avl_rotate_ll(tree); | |
break; | |
} | |
case UK_LR: | |
{ | |
tree = avl_rotate_lr(tree); | |
tree = avl_rotate_ll(tree); | |
break; | |
} | |
case UK_RR: | |
{ | |
tree = avl_rotate_rr(tree); | |
break; | |
} | |
case UK_RL: | |
{ | |
tree = avl_rotate_rl(tree); | |
tree = avl_rotate_rr(tree); | |
break; | |
} | |
default: assert(false); // logic error | |
} | |
return tree; | |
} | |
AVLTreeNode *avl_rotate_ll(AVLTreeNode *node_to_rotate) | |
{ | |
auto *intermediate = node_to_rotate->left; | |
printf("**rotating LL**\n"); | |
AVLTreeNode *c_saved = intermediate->right; | |
intermediate->right = node_to_rotate; | |
node_to_rotate->left = c_saved; | |
node_to_rotate->height = std::max(avl_node_height(node_to_rotate->left), | |
avl_node_height(node_to_rotate->right)) + 1; | |
intermediate->height = std::max(avl_node_height(intermediate->left), | |
avl_node_height(intermediate->right)) + 1; | |
// Now should be balanced with new head *intermediate* | |
return intermediate; | |
} | |
AVLTreeNode *avl_rotate_lr(AVLTreeNode *node_to_rotate) | |
{ | |
// In this kind of rotation, *node_to_rotate* is not changed | |
printf("**rotating LR**\n"); | |
auto *saved_intermediate = node_to_rotate->left; | |
node_to_rotate->left = saved_intermediate->right; | |
saved_intermediate->right = node_to_rotate->left->left; | |
node_to_rotate->left->left = saved_intermediate; | |
saved_intermediate->height = std::max(avl_node_height(saved_intermediate->left), | |
avl_node_height(saved_intermediate->right)) + 1; | |
auto *new_intermediate = saved_intermediate->left; | |
node_to_rotate->left->height = std::max(avl_node_height(new_intermediate->left), | |
avl_node_height(new_intermediate->right)) + 1; | |
node_to_rotate->height = std::max(avl_node_height(node_to_rotate->left), | |
avl_node_height(node_to_rotate->right)) + 1; | |
// now it should be in LL state | |
return node_to_rotate; | |
} | |
AVLTreeNode *avl_rotate_rr(AVLTreeNode *node_to_rotate) | |
{ | |
printf("**rotating RR**\n"); | |
auto *intermediate = node_to_rotate->right; | |
auto *c_saved = intermediate->left; | |
intermediate->left = node_to_rotate; | |
node_to_rotate->right = c_saved; | |
// btw, node_to_rotate becomes new intermediate awhile itermediate becomes new parent | |
node_to_rotate->height = std::max(avl_node_height(node_to_rotate->left), | |
avl_node_height(node_to_rotate->right)) + 1; | |
intermediate->height = std::max(avl_node_height(intermediate->left), | |
avl_node_height(intermediate->right)) + 1; | |
// Now should be balanced with new head *intermediate* | |
return intermediate; | |
} | |
AVLTreeNode *avl_rotate_rl(AVLTreeNode *node_to_rotate) | |
{ | |
// In this kind of rotation, *node_to_rotate* is not changed | |
printf("**rotating RL**\n"); | |
auto *saved_intermediate = node_to_rotate->right; | |
node_to_rotate->right = saved_intermediate->left; | |
saved_intermediate->left = node_to_rotate->right->right; | |
node_to_rotate->right->right = saved_intermediate; | |
// now it should be in RR state | |
saved_intermediate->height = std::max(avl_node_height(saved_intermediate->left), | |
avl_node_height(saved_intermediate->right)) + 1; | |
auto *new_intermediate = saved_intermediate->right; | |
node_to_rotate->right->height = std::max(avl_node_height(new_intermediate->left), | |
avl_node_height(new_intermediate->right)) + 1; | |
node_to_rotate->height = std::max(avl_node_height(node_to_rotate->left), | |
avl_node_height(node_to_rotate->right)) + 1; | |
return node_to_rotate; | |
} | |
void avL_visit_preorder(AVLTreeNode *root) | |
{ | |
if(root != NULL) | |
{ | |
printf("%d ", root->key); | |
avL_visit_preorder(root->left); | |
avL_visit_preorder(root->right); | |
} | |
} | |
void avl_print_tree_preorder(AVLTree *tree) | |
{ | |
avL_visit_preorder(tree->rootNode); | |
printf("\n"); | |
} | |
int main(int argc, char const *argv[]) | |
{ | |
AVLTree *tree; | |
avl_init(&tree); | |
avl_insert(tree, 10); | |
avl_insert(tree, 20); | |
avl_insert(tree, 30); | |
avl_insert(tree, 40); | |
avl_insert(tree, 50); | |
avl_insert(tree, 25); | |
avl_print_tree_preorder(tree); | |
avl_free(&tree); | |
return 0; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Output:
created new node with key 10
created new node with key 20
after insertion 20 key, balance factor of node 10 is: -1
created new node with key 30
after insertion 30 key, balance factor of node 20 is: -1
after insertion 30 key, balance factor of node 10 is: -2
rotating RR
created new node with key 40
after insertion 40 key, balance factor of node 30 is: -1
after insertion 40 key, balance factor of node 20 is: -1
created new node with key 50
after insertion 50 key, balance factor of node 40 is: -1
after insertion 50 key, balance factor of node 30 is: -2
rotating RR
after insertion 50 key, balance factor of node 20 is: -1
created new node with key 25
after insertion 25 key, balance factor of node 30 is: 1
after insertion 25 key, balance factor of node 40 is: 1
after insertion 25 key, balance factor of node 20 is: -2
rotating RL
rotating RR
30 20 10 25 40 50