Chapter 13 |
![]() ![]() ![]() ![]() ![]() ![]() ![]() |
1. No. It would work, except for the important special case where q is the pseudo-root but p->pbst_parent is NULL.
681. <PBST balance function, with integrated parent updates 681> = <BST to vine function; bst => pbst 90> <Vine to balanced PBST function, with parent updates 682> void
pbst_balance (struct pbst_table *tree)
{ assert (tree != NULL); tree_to_vine (tree); vine_to_tree (tree); }
682. <Vine to balanced PBST function, with parent updates 682> = <PBST compression function 684> static void
vine_to_tree (struct pbst_table *tree)
{ unsigned long vine; /* Number of nodes in main vine. */ unsigned long leaves; /* Nodes in incomplete bottom level, if any. */ int height; /* Height of produced balanced tree. */ struct pbst_node *p, *q; /* Current visited node and its parent. */ <Calculate leaves; bst => pbst 92> <Reduce vine general case to special case; bst => pbst 93> <Make special case vine into balanced tree and count height; bst => pbst 94> <Set parents of main vine 683> }
This code is included in 681.
683. <Set parents of main vine 683> = for (q = NULL, p = tree->pbst_root; p != NULL; q = p, p = p->pbst_link[0]) p->pbst_parent = q;
This code is included in 682.
684. <PBST compression function 684> = static void
compress (struct pbst_node *root, unsigned long count)
{ assert (root != NULL); while (count--)
{ struct pbst_node *red = root->pbst_link[0]; struct pbst_node *black = red->pbst_link[0]; root->pbst_link[0] = black; red->pbst_link[0] = black->pbst_link[1]; black->pbst_link[1] = red; red->pbst_parent = black; if (red->pbst_link[0] != NULL) red->pbst_link[0]->pbst_parent = red; root = black; } }
This code is included in 682.