From e4a56e626030b728a7dcada8e84a77d1da3b00ae Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Wed, 8 Jul 2020 22:05:12 -0400 Subject: Add rebalance function for map trees --- collections/map/map.c | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+) (limited to 'collections/map') diff --git a/collections/map/map.c b/collections/map/map.c index 021743d..cbb3b79 100644 --- a/collections/map/map.c +++ b/collections/map/map.c @@ -63,6 +63,33 @@ struct map_node **node; return; } +void map_rebal_tree(root) +struct map_node **root; +{ + struct map_node *tmp; + + if(! *root) + return; + + if (map_height((*root)->left) > map_height((*root)->right)) { + if(map_bal_factor((*root)->left) >= 0) { + map_rotate_left(root); + } else { + map_rotate_left(root); + map_rotate_right(root); + } + } else { + if (map_bal_factor((*root)->right) >= 0) { + map_rotate_right(root); + } else { + map_rotate_right(root); + map_rotate_left(root); + } + } + + return; +} + map* map_new(cmp) cmp_func cmp; { -- cgit v1.1