2 * Copyright (c) 2007 Vojtech Mencl
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 /** @addtogroup genericadt
35 * @brief AVL tree implementation.
37 * This file implements AVL tree type and operations.
39 * Implemented AVL tree has the following properties:
40 * @li It is a binary search tree with non-unique keys.
41 * @li Difference of heights of the left and the right subtree of every node is
44 * Every node has a pointer to its parent which allows insertion of multiple
45 * identical keys into the tree.
47 * Be careful when using this tree because of the base atribute which is added
48 * to every inserted node key. There is no rule in which order nodes with the
49 * same key are visited.
58 /** Search for the first occurence of the given key in an AVL tree.
61 * @param key Key to be searched.
63 * @return Pointer to a node or NULL if there is no such key.
65 avltree_node_t
*avltree_search(avltree_t
*t
, avltree_key_t key
)
70 * Iteratively descend to the leaf that can contain the searched key.
76 else if (p
->key
< key
)
85 /** Find the node with the smallest key in an AVL tree.
89 * @return Pointer to a node or NULL if there is no node in the tree.
91 avltree_node_t
*avltree_find_min(avltree_t
*t
)
93 avltree_node_t
*p
= t
->root
;
96 * Check whether the tree is empty.
102 * Iteratively descend to the leftmost leaf in the tree.
104 while (p
->lft
!= NULL
)
110 #define REBALANCE_INSERT_XX(DIR1, DIR2) \
111 top->DIR1 = par->DIR2; \
112 if (top->DIR1 != NULL) \
113 top->DIR1->par = top; \
114 par->par = top->par; \
121 #define REBALANCE_INSERT_LL() REBALANCE_INSERT_XX(lft, rgt)
122 #define REBALANCE_INSERT_RR() REBALANCE_INSERT_XX(rgt, lft)
124 #define REBALANCE_INSERT_XY(DIR1, DIR2, SGN) \
126 par->DIR2 = gpa->DIR1; \
127 if (gpa->DIR1 != NULL) \
128 gpa->DIR1->par = par; \
131 top->DIR1 = gpa->DIR2; \
132 if (gpa->DIR2 != NULL) \
133 gpa->DIR2->par = top; \
135 gpa->par = top->par; \
138 if (gpa->balance == -1 * SGN) { \
140 top->balance = 1 * SGN; \
141 } else if (gpa->balance == 0) { \
145 par->balance = -1 * SGN; \
151 #define REBALANCE_INSERT_LR() REBALANCE_INSERT_XY(lft, rgt, 1)
152 #define REBALANCE_INSERT_RL() REBALANCE_INSERT_XY(rgt, lft, -1)
154 /** Insert new node into AVL tree.
157 * @param newnode New node to be inserted.
159 void avltree_insert(avltree_t
*t
, avltree_node_t
*newnode
)
164 avltree_node_t
**dpc
;
171 * Creating absolute key.
173 key
= newnode
->key
+ t
->base
;
176 * Iteratively descend to the leaf that can contain the new node.
177 * Last node with non-zero balance in the way to leaf is stored as top -
178 * it is a place of possible inbalance.
183 while ((par
= (*dpc
)) != NULL
) {
184 if (par
->balance
!= 0) {
188 dpc
= par
->key
> key
? &par
->lft
: &par
->rgt
;
192 * Initialize the new node.
198 newnode
->balance
= 0;
201 * Insert first node into the empty tree.
203 if (t
->root
== NULL
) {
209 * Insert the new node into the previously found leaf position.
214 * If the tree contains one node - end.
220 * Store pointer of top's father which points to the node with
221 * potentially broken balance (top).
223 if (top
->par
== NULL
) {
226 if (top
->par
->lft
== top
)
227 dpc
= &top
->par
->lft
;
229 dpc
= &top
->par
->rgt
;
233 * Repair all balances on the way from top node to the newly inserted
237 while (par
!= newnode
) {
238 if (par
->key
> key
) {
248 * To balance the tree, we must check and balance top node.
250 if (top
->balance
== -2) {
252 if (par
->balance
== -1) {
256 REBALANCE_INSERT_LL();
261 assert(par
->balance
== 1);
263 REBALANCE_INSERT_LR();
265 } else if (top
->balance
== 2) {
267 if (par
->balance
== 1) {
271 REBALANCE_INSERT_RR();
276 assert(par
->balance
== -1);
278 REBALANCE_INSERT_RL();
282 * Balance is not broken, insertion is finised.
289 /** Repair the tree after reparenting node u.
291 * If node u has no parent, mark it as the root of the whole tree. Otherwise
292 * node v represents stale address of one of the children of node u's parent.
293 * Replace v with w as node u parent's child (for most uses, u and w will be the
297 * @param u Node whose new parent has a stale child pointer.
298 * @param v Stale child of node u's new parent.
299 * @param w New child of node u's new parent.
300 * @param dir If not NULL, address of the variable where to store information
301 * about whether w replaced v in the left or the right subtree of
303 * @param ro Read only operation; do not modify any tree pointers. This is
304 * useful for tracking direction via the dir pointer.
306 * @return Zero if w became the new root of the tree, otherwise return
310 repair(avltree_t
*t
, avltree_node_t
*u
, avltree_node_t
*v
, avltree_node_t
*w
,
313 if (u
->par
== NULL
) {
318 if (u
->par
->lft
== v
) {
324 assert(u
->par
->rgt
== v
);
334 #define REBALANCE_DELETE(DIR1, DIR2, SIGN) \
335 if (cur->balance == -1 * SIGN) { \
337 gpa->balance = 1 * SIGN; \
339 gpa->DIR1->par = gpa; \
340 par->DIR2->par = par; \
341 } else if (cur->balance == 0) { \
345 gpa->DIR1->par = gpa; \
347 par->DIR2->par = par; \
349 par->balance = -1 * SIGN; \
352 par->DIR2->par = par; \
353 gpa->DIR1->par = gpa; \
357 #define REBALANCE_DELETE_LR() REBALANCE_DELETE(lft, rgt, 1)
358 #define REBALANCE_DELETE_RL() REBALANCE_DELETE(rgt, lft, -1)
360 /** Delete a node from the AVL tree.
362 * Because multiple identical keys are allowed, the parent pointers are
363 * essential during deletion.
365 * @param t AVL tree structure.
366 * @param node Address of the node which will be deleted.
368 void avltree_delete(avltree_t
*t
, avltree_node_t
*node
)
378 if (node
->lft
== NULL
) {
381 * Replace the node with its only right son.
383 * Balance of the right son will be repaired in the
387 cur
->par
= node
->par
;
390 cur
->balance
= node
->balance
;
392 if (node
->par
== NULL
) {
394 * The tree has only one node - it will become
395 * an empty tree and the balancing can end.
401 * The node has no child, it will be deleted with no
406 dir
= (gpa
->lft
== node
) ? LEFT
: RIGHT
;
410 * The node has the left son. Find a node with the smallest key
411 * in the left subtree and replace the deleted node with that
415 while (cur
->rgt
!= NULL
)
418 if (cur
!= node
->lft
) {
420 * The rightmost node of the deleted node's left subtree
421 * was found. Replace the deleted node with this node.
422 * Cutting off of the found node has two cases that
423 * depend on its left son.
427 * The found node has a left son.
432 gpa
->balance
= cur
->balance
;
437 cur
->par
->rgt
= cur
->lft
;
438 cur
->lft
= node
->lft
;
442 * The left son of the node hasn't got a right son. The
443 * left son will take the deleted node's place.
449 node
->rgt
->par
= cur
;
450 cur
->rgt
= node
->rgt
;
451 cur
->balance
= node
->balance
;
452 cur
->par
= node
->par
;
456 * Repair the parent node's pointer which pointed previously to the
459 (void) repair(t
, node
, node
, cur
, NULL
, false);
462 * Repair cycle which repairs balances of nodes on the way from from the
463 * cut-off node up to the root.
468 * Deletion was made in the left subtree.
471 if (gpa
->balance
== 1) {
473 * Stop balancing, the tree is balanced.
476 } else if (gpa
->balance
== 2) {
478 * Bad balance, heights of left and right
479 * subtrees differ more than by one.
483 if (par
->balance
== -1) {
495 * Repair balances and paternity of
496 * children, depending on the balance
497 * factor of the grand child (cur).
499 REBALANCE_DELETE_RL();
508 if (!repair(t
, cur
, gpa
, cur
, &dir
,
528 if (par
->balance
== 0) {
530 * The right child of the
531 * balanced node is balanced,
532 * after RR rotation is done,
533 * the whole tree will be
539 (void) repair(t
, par
, gpa
, par
,
545 if (!repair(t
, par
, gpa
, par
,
553 * Repair the pointer which pointed to the
554 * balanced node. If it was root then balancing
555 * is finished else continue with the next
556 * iteration (parent node).
558 if (!repair(t
, gpa
, gpa
, NULL
, &dir
, true))
564 * Deletion was made in the right subtree.
567 if (gpa
->balance
== -1) {
569 * Stop balancing, the tree is balanced.
572 } else if (gpa
->balance
== -2) {
574 * Bad balance, heights of left and right
575 * subtrees differ more than by one.
579 if (par
->balance
== 1) {
591 * Repair balances and paternity of
592 * children, depending on the balance
593 * factor of the grand child (cur).
595 REBALANCE_DELETE_LR();
604 if (!repair(t
, cur
, gpa
, cur
, &dir
,
623 if (par
->balance
== 0) {
625 * The left child of the
626 * balanced node is balanced,
627 * after LL rotation is done,
628 * the whole tree will be
634 (void) repair(t
, par
, gpa
, par
,
641 if (!repair(t
, par
, gpa
, par
,
649 * Repair the pointer which pointed to the
650 * balanced node. If it was root then balancing
651 * is finished. Otherwise continue with the next
652 * iteration (parent node).
654 if (!repair(t
, gpa
, gpa
, NULL
, &dir
, true))
663 /** Delete a node with the smallest key from the AVL tree.
665 * @param t AVL tree structure.
667 bool avltree_delete_min(avltree_t
*t
)
669 avltree_node_t
*node
;
672 * Start searching for the smallest key in the tree starting in the root
673 * node and continue in cycle to the leftmost node in the tree (which
674 * must have the smallest key).
681 while (node
->lft
!= NULL
)
684 avltree_delete(t
, node
);
689 /** Walk a subtree of an AVL tree in-order and apply a supplied walker on each
692 * @param node Node representing the root of an AVL subtree to be
694 * @param walker Walker function that will be appliad on each visited
696 * @param arg Argument for the walker.
698 * @return Zero if the walk should stop or non-zero otherwise.
700 static bool _avltree_walk(avltree_node_t
*node
, avltree_walker_t walker
,
704 if (!_avltree_walk(node
->lft
, walker
, arg
))
707 if (!walker(node
, arg
))
710 if (!_avltree_walk(node
->rgt
, walker
, arg
))
716 /** Walk the AVL tree in-order and apply the walker function on each visited
719 * @param t AVL tree to be walked.
720 * @param walker Walker function that will be called on each visited
722 * @param arg Argument for the walker.
724 void avltree_walk(avltree_t
*t
, avltree_walker_t walker
, void *arg
)
727 _avltree_walk(t
->root
, walker
, arg
);