From 1fdac316bde6e192a6ebf51148af0ee66a6ae831 Mon Sep 17 00:00:00 2001 From: mo khan Date: Sun, 27 Sep 2020 12:38:47 -0600 Subject: docs: Add documentation for AVL tree --- src/03/avl_tree.c | 120 +++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 119 insertions(+), 1 deletion(-) (limited to 'src') diff --git a/src/03/avl_tree.c b/src/03/avl_tree.c index 30f51c0..40d5d36 100644 --- a/src/03/avl_tree.c +++ b/src/03/avl_tree.c @@ -2,6 +2,12 @@ #include #include +/** + * Print a visual representation of an AVL Tree. + * + * @param tree The subtree to print + * @param level The level in the tree that this subtree is in + */ static void print_tree(AVLTree *tree, int level) { for (int i = 0; i < level; i++) printf(" "); @@ -18,10 +24,30 @@ static void print_tree(AVLTree *tree, int level) { } } +/* + * Determines if a integer value is evenly divisibly by 2. + * + * @param value The integer to check + * @return true when the value is even otherwise false + */ static bool is_even(int value) { return value % 2 == 0; } +/* + * Determines if a integer value is an odd number + * + * @param value The integer to check + * @return true when the value is odd otherwise false + */ static bool is_odd(int value) { return !is_even(value); } +/** + * Converts an AVL tree to a Red Black tree with all + * nodes in the tree coloured black. + * + * @param tree The AVL subtree to convert + * @param parent The parent node of the current subtree. Use NULL for the root. + * @return The converted Red Black tree + */ static RBTree *to_rb_tree(AVLTree *tree, AVLTree *parent) { if (!tree) return NULL; @@ -38,6 +64,12 @@ static RBTree *to_rb_tree(AVLTree *tree, AVLTree *parent) { return rb_tree; } +/** + * Applies the correct colouring to each descendant node in a Red Black tree. + * + * @param tree The Red Black subtree to colour + * @param colour The colour to apply to the provided subtree node. + */ static void change_colour(RBTree *tree, enum Colour colour) { if (!tree) return; @@ -50,19 +82,44 @@ static void change_colour(RBTree *tree, enum Colour colour) { change_colour(tree->right, r < l || is_odd(r) ? black : red); } +/** + * Returns the larger integer between the two provided as arguments. + * + * @param a An integer value to compare + * @param b Another integer value to compare + * @return Returns the larger value + */ static int max(int a, int b) { return (a > b) ? a : b; } +/** + * Returns the height of an AVL subtree. + * + * @param tree The subtree to interrogate. + * @return The height of the subtree + */ static int height_of(AVLTree *tree) { return tree == NULL ? 0 : tree->height; } +/** + * Returns the smallest value stored in the AVL tree. + * + * @param tree The subtree to traverse to find the smallest value. + * @return The subtree node containing the smallest value in the tree. + */ static AVLTree *smallest(AVLTree *tree) { AVLTree *current = tree; - while (current->left != NULL) + while (current && current->left != NULL) current = current->left; return current; } +/** + * Performs a right rotation on an AVL subtree + * + * @param y The subtree to perform the rotation on + * @return The new root after the rotation is performed. + */ static AVLTree *rotate_right(AVLTree *y) { AVLTree *x = y->left; AVLTree *t = x->right; @@ -76,6 +133,12 @@ static AVLTree *rotate_right(AVLTree *y) { return x; } +/** + * Performs a left rotation on an AVL subtree + * + * @param x The subtree to perform the rotation on + * @return The new root after the rotation is performed. + */ static AVLTree *rotate_left(AVLTree *x) { AVLTree *y = x->right; AVLTree *t = y->left; @@ -89,12 +152,35 @@ static AVLTree *rotate_left(AVLTree *x) { return y; } +/** + * Calculates the balance of a subtree by taking the difference + * of the height of the left subtree and the right subtree. + * + * @param tree The tree to investigate. + * @return The balace + */ static int balance_of(AVLTree *tree) { return (tree == NULL) ? 0 : height_of(tree->left) - height_of(tree->right); } +/** + * Compares two integers and returns -1, 0, 1. + * If a is equal to b then 0 is returned. + * If a is greater than b then 1 is returned. + * If a is less than b then -1 is returned. + * + * @param a An integer + * @param b Another integer + * @return Returns 0, 1, or -1. + */ static int compare(int a, int b) { return (a < b) ? -1 : ((a > b) ? 1 : 0); } +/** + * Initializes an instance of an AVL tree. + * + * @param value The value to assign to the new node in the tree. + * @return Returns the new AVL tree node instance. + */ AVLTree *avl_tree_initialize(int value) { AVLTree *tree = malloc(sizeof(AVLTree)); tree->value = value; @@ -104,6 +190,12 @@ AVLTree *avl_tree_initialize(int value) { return tree; } +/** + * Computes the # of nodes stored in an AVL subtree. + * + * @param tree The subtree to investigate. + * @return Returns the # of descendant nodes found in the subtree. + */ int avl_tree_size(AVLTree *tree) { int total = 0; if (tree == NULL) @@ -115,6 +207,13 @@ int avl_tree_size(AVLTree *tree) { return total + 1; } +/** + * Inserts a new value into an AVL subtree. + * + * @param tree The subtree to attempt to insert a new value into. + * @param value The value to insert. + * @return Returns the new root of the subtree. + */ AVLTree *avl_tree_insert(AVLTree *tree, int value) { if (tree == NULL) return avl_tree_initialize(value); @@ -152,6 +251,13 @@ AVLTree *avl_tree_insert(AVLTree *tree, int value) { return tree; } +/** + * Deletes a value from an AVL subtree. + * + * @param tree The subtree to search to find the value to delete. + * @param value The value to search for. + * @return Returns the new root of the subtree. + */ AVLTree *avl_tree_delete(AVLTree *tree, int value) { if (tree == NULL) return tree; @@ -204,6 +310,12 @@ AVLTree *avl_tree_delete(AVLTree *tree, int value) { return tree; } +/** + * Converts an AVL tree to a Red Black tree. + * + * @param tree The AVL tree to convert. + * @return Returns a new Red Black tree. + */ RBTree *avl_tree_to_rb_tree(AVLTree *tree) { if (!tree) return NULL; @@ -213,4 +325,10 @@ RBTree *avl_tree_to_rb_tree(AVLTree *tree) { return rb_tree; } +/** + * Prints a visual inspection of + * an AVL tree for debugging purposes to stdout. + * + * @param tree The tree to visualize + */ void avl_tree_inspect(AVLTree *tree) { print_tree(tree, 0); } -- cgit v1.2.3