8000 AVL tree: Remove debugging functions, fix bug with parent references · fragglet/c-algorithms@adc9bf6 · GitHub
[go: up one dir, main page]
Skip to content

Commit adc9bf6

Browse files
fraggletfragglet
committed
AVL tree: Remove debugging functions, fix bug with parent references
not updated on rotate. Add "remove" function and test cases.
1 parent 40936c7 commit adc9bf6

File tree

4 files changed

+476
-92
lines changed

4 files changed

+476
-92
lines changed

‎src/avltree.c

Lines changed: 232 additions & 91 deletions
Original file line numberDiff line numberDiff line change
@@ -64,7 +64,7 @@ AVLTree *avltree_new(AVLTreeCompareFunc compare_func)
6464
return new_tree;
6565
}
6666

67-
static int avltree_subtree_height(AVLTreeNode *node)
67+
int avltree_subtree_height(AVLTreeNode *node)
6868
{
6969
if (node == < 10000 span class=pl-c1>NULL) {
7070
return 0;
@@ -147,6 +147,14 @@ static void avltree_rotate_left(AVLTree *tree, AVLTreeNode *node)
147147
node->right_child = new_root->left_child;
148148
new_root->left_child = node;
149149

150+
/* Update parent references */
151+
152+
node->parent = new_root;
153+
154+
if (node->right_child != NULL) {
155+
node->right_child->parent = node;
156+
}
157+
150158
/* Update heights of the affected nodes */
151159

152160
avltree_update_height(new_root);
@@ -209,20 +217,99 @@ static void avltree_rotate_right(AVLTree *tree, AVLTreeNode *node)
209217
node->left_child = new_root->right_child;
210218
new_root->right_child = node;
211219

220+
/* Update parent references */
221+
222+
node->parent = new_root;
223+
224+
if (node->left_child != NULL) {
225+
node->left_child->parent = node;
226+
}
227+
212228
/* Update heights of the affected nodes */
213229

214230
avltree_update_height(new_root);
215231
avltree_update_height(node);
216232
}
217233

234+
/* Balance a particular tree node.
235+
*
236+
* Returns the root node of the new subtree which is replacing the
237+
* old one. */
238+
239+
static AVLTreeNode *avltree_node_balance(AVLTree *tree, AVLTreeNode *node)
240+
{
241+
AVLTreeNode *new_root;
242+
int diff;
243+
244+
/* Check the heights of the child trees. If there is an unbalance
245+
* (difference between left and right > 2), then rotate nodes
246+
* around to fix it */
247+
248+
diff = avltree_subtree_height(node->right_child)
249+
- avltree_subtree_height(node->left_child);
250+
251+
if (diff >= 2) {
252+
253+
/* Biased toward the right side too much. */
254+
255+
if (avltree_subtree_height(node->right_child->right_child)
256+
<= avltree_subtree_height(node->right_child->left_child)) {
257+
258+
/* If the right child is biased toward the left
259+
* side, it must be rotated right first (double
260+
* rotation) */
261+
262+
avltree_rotate_right(tree, node->right_child);
263+
}
264+
265+
/* Perform a left rotation. After this, the right child will
266+
* take the place of this node. Store a pointer to the right
267+
* child so that we can continue where we left off. */
268+
269+
new_root = node->right_child;
270+
271+
avltree_rotate_left(tree, node);
272+
273+
node = new_root;
274+
275+
} else if (diff <= -2) {
276+
277+
/* Biased toward the left side too much. */
278+
279+
if (avltree_subtree_height(node->left_child->left_child)
280+
<= avltree_subtree_height(node->left_child->right_child)) {
281+
282+
/* If the left child is biased toward the right
283+
* side, it must be rotated right left (double
284+
* rotation) */
285+
286+
avltree_rotate_left(tree, node->left_child);
287+
}
288+
289+
/* Perform a right rotation. After this, the left child
290+
* will take the place of this node. Store a pointer to the
291+
* left child so that we can continue where we left off. */
292+
293+
new_root = node->left_child;
294+
295+
avltree_rotate_right(tree, node);
296+
297+
node = new_root;
298+
}
299+
300+
/* Update the height of this node */
301+
302+
avltree_update_height(node);
303+
304+
return node;
305+
}
306+
218307
AVLTreeNode *avltree_insert(AVLTree *tree, void *key, void *value)
219308
{
220309
AVLTreeNode **rover;
221310
AVLTreeNode *new_node;
222311
AVLTreeNode *previous_node;
223312
AVLTreeNode *node;
224-
AVLTreeNode *new_root;
225-
int diff;
226313

227314
/* Walk down the tree until we reach a NULL pointer */
228315

@@ -258,68 +345,167 @@ AVLTreeNode *avltree_insert(AVLTree *tree, void *key, void *value)
258345

259346
while (node != NULL) {
260347

261-
/* Check the heights of the child trees. If there is an unbalance
262-
* (difference between left and right > 2), then rotate nodes
263-
* around to fix it */
348+
/* Balance this node if necessary */
264349

265-
diff = avltree_subtree_height(node->right_child)
266-
- avltree_subtree_height(node->left_child);
350+
node = avltree_node_balance(tree, node);
267351

268-
if (diff >= 2) {
269-
270-
/* Biased toward the right side too much. */
352+
/* Go to this node's parent */
271353

272-
if (tree->compare_func(key, node->right_child->key) <= 0) {
354+
node = node->parent;
355+
}
273356

274-
/* If this was added to the left of the right child,
275-
* rotate the right child right first (double rotation) */
357+
return new_node;
358+
}
276359

277-
avltree_rotate_right(tree, node->right_child);
278-
}
360+
/* Remove a node from a tree */
279361

280-
/* Perform a left rotation. After this, the right child will
281-
* take the place of this node. Store a pointer to the right
282-
* child so that we can continue where we left off. */
362+
void avltree_remove_node(AVLTree *tree, AVLTreeNode *node)
363+
{
364+
AVLTreeNode *swap_node;
365+
AVLTreeNode *rover;
366+
AVLTreeNode *balance_startpoint;
283367

284-
new_root = node->right_child;
285-
286-
avltree_rotate_left(tree, node);
368+
/* The node to be removed must be swapped with an "adjacent"
369+
* node, ie. one which has the closest key to this one. Find
370+
* a node to swap with. */
371+
372+
if (node->left_child != NULL) {
287373

288-
node = new_root;
374+
/* Search for the right-most node in the left subtree, ie.
375+
* the greatest value. */
289376

290-
} else if (diff <= -2) {
377+
swap_node = node->left_child;
378+
379+
while (swap_node->right_child != NULL) {
380+
swap_node = swap_node->right_child;
381+
}
291382

292-
/* Biased toward the left side too much. */
383+
/* Unlink the swap node, move the swap node's left
384+
* child tree in to replace it */
10662 293385

294-
if (tree->compare_func(key, node->left_child->key) >= 0) {
386+
if (swap_node->parent->right_child == swap_node) {
387+
swap_node->parent->right_child
388+
= swap_node->left_child;
389+
} else {
390+
swap_node->parent->left_child
391+
= swap_node->left_child;
392+
}
393+
394+
if (swap_node->left_child != NULL) {
395+
swap_node->left_child->parent = swap_node->parent;
396+
}
295397

296-
/* If this was added to the right of the left child,
297-
* rotate the left child left first (double rotation) */
398+
} else if (node->right_child != NULL) {
399+
400+
/* Search for the left-most node in the right subtree, ie.
401+
* the least value. */
402+
403+
swap_node = node->right_child;
404+
405+
while (swap_node->left_child != NULL) {
406+
swap_node = swap_node->left_child;
407+
}
408+
409+
/* Unlink the swap node, move the swap node's right
410+
* child tree in to replace it */
411+
412+
if (swap_node->parent->left_child == swap_node) {
413+
swap_node->parent->left_child
414+
= swap_node->right_child;
415+
} else {
416+
swap_node->parent->right_child
417+
= swap_node->right_child;
418+
}
298419

299-
avltree_rotate_left(tree, node->left_child);
420+
if (swap_node->right_child != NULL) {
421+
swap_node->right_child->parent = swap_node->parent;
422+
}
423+
424+
} else {
425+
/* This is a leaf node and has no children, therefore
426+
* it can be immediately removed. */
427+
428+
/* Unlink this node from its parent */
429+
430+
if (node->parent != NULL) {
431+
if (node->parent->left_child == node) {
432+
node->parent->left_child = NULL;
433+
} else {
434+
node->parent->right_child = NULL;
300435
}
436+
} else {
437+
/* Root node */
438+
439+
tree->root_node = NULL;
440+
}
441+
442+
/* "swap" stage is skipped. */
301443

302-
/* Perform a right rotation. After this, the left child
303-
* will take the place of this node. Store a pointer to the
304-
* left child so that we can continue where we left off. */
444+
swap_node = NULL;
305445

306-
new_root = node->left_child;
446+
/* Start balancing from the node's parent */
307447

308-
avltree_rotate_right(tree, node);
448+
balance_startpoint = node->parent;
449+
}
450+
451+
/* Link the "swap" node into the tree, at the position where
452+
* "node" previously was. */
453+
454+
if (swap_node != NULL) {
455+
456+
/* Copy references in the node into the swap node */
457+
458+
swap_node->left_child = node->left_child;
459+
swap_node->right_child = node->right_child;
460+
swap_node->parent = node->parent;
461+
462+
/* Link the parent's reference to this node */
463+
464+
if (node->parent != NULL) {
465+
if (node->parent->left_child == node) {
466+
node->parent->left_child = swap_node;
467+
} else {
468+
node->parent->right_child = swap_node;
469+
}
470+
} else {
471+
/* Root of the tree */
309472

310-
node = new_root;
473+
tree->root_node = swap_node;
311474
}
312475

313-
/* Update the height of this node */
476+
/* Fix the "parent" references of child nodes */
314477

315-
avltree_update_height(node);
478+
if (node->left_child != NULL) {
479+
node->left_child->parent = swap_node;
480+
}
481+
482+
if (node->right_child != NULL) {
483+
node->right_child->parent = swap_node;
484+
}
316485

317-
/* Go to this node's parent */
486+
/* Start balancing from the swap node's former parent */
318487

319-
node = node->parent;
488+
balance_startpoint = swap_node->parent;
320489
}
321490

322-
return new_node;
491+
/* Destroy the node */
492+
493+
free(node);
494+
495+
/* Rebalance the tree */
496+
497+
rover = balance_startpoint;
498+
499+
while (rover != NULL) {
500+
501+
/* Possibly rebalance this subtree */
502+
503+
rover = avltree_node_balance(tree, rover);
504+
505+
/* Go to the node's parent */
506+
507+
rover = rover->parent;
508+
}
323509
}
324510

325511
AVLTreeNode *avltree_lookup_node(AVLTree *tree, void *key)
@@ -369,6 +555,12 @@ void *avltree_lookup(AVLTree *tree, void *key)
369555
}
370556
}
371557

558+
AVLTreeNode *avltree_root_node(AVLTree *tree)
559+
{
560+
return tree->root_node;
561+
}
562+
563+
372564
void *avltree_node_key(AVLTreeNode *node)
373565
{
374566
return node->key;
@@ -394,54 +586,3 @@ AVLTreeNode *avltree_node_parent(AVLTreeNode *node)
394586
return node->parent;
395587
}
396588

397-
/* !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */
398-
399-
/* The following all needs to be removed eventually */
400-
401-
static void avltree_print_tree_node(AVLTreeNode *node, int indent)
402-
{
403-
int i;
404-
405-
if (node == NULL) {
406-
return;
407-
}
408-
409-
for (i=0; i<indent; ++i) {
410-
putchar(' ');
411-
}
412-
413-
printf("node:\n");
414-
415-
avltree_print_tree_node(node->left_child, indent + 2);
416-
avltree_print_tree_node(node->right_child, indent + 2);
417-
}
418 DEC7 -
419-
void avltree_print_tree(AVLTree *tree)
420-
{
421-
avltree_print_tree_node(tree->root_node, 0);
422-
}
423-
424-
static int avltree_check_node_balanced(AVLTreeNode *node)
425-
{
426-
int diff;
427-
428-
if (node == NULL) {
429-
return 1;
430-
}
431-
432-
avltree_check_node_balanced(node->left_child);
433-
avltree_check_node_balanced(node->right_child);
434-
435-
avltree_update_height(node);
436-
437-
diff = avltree_subtree_height(node->left_child)
438-
- avltree_subtree_height(node->right_child);
439-
440-
return diff > -2 && diff < 2;
441-
}
442-
443-
int avltree_check_balanced(AVLTree *tree)
444-
{
445-
return avltree_check_node_balanced(tree->root_node);
446-
}
447-

0 commit comments

Comments
 (0)
0