Last active
August 7, 2024 06:03
-
-
Save ziap/56baf02797c6037f763b3303947462dc to your computer and use it in GitHub Desktop.
AVL tree implementation in C
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 <stdlib.h> | |
| #include <stdint.h> | |
| #define MAX(a, b) (((a) > (b)) ? (a) : (b)) | |
| typedef enum { | |
| SIDE_LEFT = 0, | |
| SIDE_RIGHT, | |
| SIDE_COUNT, | |
| } AVL_Side; | |
| typedef struct AVL_Node AVL_Node; | |
| typedef int KeyType; | |
| struct AVL_Node { | |
| KeyType key; | |
| int8_t height; | |
| AVL_Node *children[SIDE_COUNT]; | |
| }; | |
| static AVL_Node NIL_NODE = { | |
| .height = 0, | |
| .children = {NULL, NULL} | |
| }; | |
| static AVL_Node *NIL = &NIL_NODE; | |
| static void AVL_update_height(AVL_Node *node) { | |
| node->height = 1 + MAX(node->children[SIDE_LEFT]->height, | |
| node->children[SIDE_RIGHT]->height); | |
| } | |
| static int8_t AVL_balance_factor(AVL_Node *node, AVL_Side side) { | |
| return node->children[side]->height - node->children[!side]->height; | |
| } | |
| static void AVL_rotate(AVL_Node **node, AVL_Side side) { | |
| AVL_Node *temp = (*node)->children[!side]; | |
| (*node)->children[!side] = temp->children[side]; | |
| AVL_update_height(*node); | |
| temp->children[side] = *node; | |
| AVL_update_height(temp); | |
| *node = temp; | |
| } | |
| static void AVL_balance(AVL_Node **node, AVL_Side side) { | |
| AVL_update_height(*node); | |
| if (AVL_balance_factor(*node, side) > 1) { | |
| AVL_Node **child = &(*node)->children[side]; | |
| if (AVL_balance_factor(*child, side) < 0) { | |
| AVL_rotate(child, side); | |
| } | |
| AVL_rotate(node, !side); | |
| } | |
| } | |
| void AVL_insert(AVL_Node **node, KeyType data) { | |
| if ((*node) == NIL) { | |
| AVL_Node *new_node = malloc(sizeof(AVL_Node)); | |
| new_node->key = data; | |
| new_node->children[SIDE_LEFT] = NIL; | |
| new_node->children[SIDE_RIGHT] = NIL; | |
| new_node->height = 1; | |
| *node = new_node; | |
| return; | |
| } | |
| if ((*node)->key == data) return; | |
| AVL_Side side = data > (*node)->key; | |
| AVL_insert(&(*node)->children[side], data); | |
| AVL_balance(node, side); | |
| } | |
| static KeyType AVL_remove_succ(AVL_Node **node) { | |
| if ((*node)->children[SIDE_LEFT] != NIL) { | |
| KeyType val = AVL_remove_succ(&(*node)->children[SIDE_LEFT]); | |
| AVL_balance(node, SIDE_RIGHT); | |
| return val; | |
| } | |
| KeyType val = (*node)->key; | |
| AVL_Node *child = (*node)->children[SIDE_RIGHT]; | |
| free(*node); | |
| *node = child; | |
| return val; | |
| } | |
| void AVL_remove(AVL_Node **node, KeyType data) { | |
| if ((*node) == NIL) { | |
| return; | |
| } | |
| if ((*node)->key == data) { | |
| if ((*node)->children[SIDE_LEFT] != NIL && (*node)->children[SIDE_RIGHT] != NIL) { | |
| (*node)->key = AVL_remove_succ(&(*node)->children[SIDE_RIGHT]); | |
| AVL_balance(node, SIDE_LEFT); | |
| return; | |
| } | |
| AVL_Node *child = (*node)->children[SIDE_LEFT]; | |
| if (child == NIL) child = (*node)->children[SIDE_RIGHT]; | |
| free(*node); | |
| *node = child; | |
| return; | |
| } | |
| AVL_Side side = data > (*node)->key; | |
| AVL_remove(&(*node)->children[side], data); | |
| AVL_balance(node, !side); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment