| 0,0 → 1,712 |
|---|
| /* |
| * Copyright (c) 2007 Vojtech Mencl |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * |
| * - Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * - Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * - The name of the author may not be used to endorse or promote products |
| * derived from this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
| * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
| * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
| * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
| * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| /** @addtogroup genericadt |
| * @{ |
| */ |
| |
| /** |
| * @file |
| * @brief AVL tree implementation. |
| * |
| * This file implements AVL tree type and operations. |
| * |
| * Implemented AVL tree has the following properties: |
| * @li It is a binary search tree with non-unique keys. |
| * @li Difference of heights of the left and the right subtree of every node is |
| * one at maximum. |
| * |
| * Every node has a pointer to its parent which allows insertion of multiple |
| * identical keys into the tree. |
| * |
| * Be careful when using this tree because of the base atribute which is added |
| * to every inserted node key. There is no rule in which order nodes with the |
| * same key are visited. |
| */ |
| |
| #include <adt/avl.h> |
| #include <debug.h> |
| |
| |
| #define LEFT 0 |
| #define RIGHT 1 |
| |
| |
| /** Search for the first occurence of the given key in an AVL tree. |
| * |
| * @param t AVL tree. |
| * @param key Key to be searched. |
| * |
| * @return Pointer to a node or NULL if there is no such key. |
| */ |
| avltree_node_t *avltree_search(avltree_t *t, uint64_t key) |
| { |
| avltree_node_t *p; |
| |
| /* |
| * Iteratively descend to the leaf that can contain the searched key. |
| */ |
| p = t->root; |
| while (p != NULL) { |
| if (p->key > key) |
| p = p->lft; |
| else if (p->key < key) |
| p = p->rgt; |
| else |
| return p; |
| } |
| return NULL; |
| } |
| |
| |
| /** Find the node with the smallest key in an AVL tree. |
| * |
| * @param t AVL tree. |
| * |
| * @return Pointer to a node or NULL if there is no node in the tree. |
| */ |
| avltree_node_t *avltree_find_min(avltree_t *t) |
| { |
| avltree_node_t *p = t->root; |
| |
| /* |
| * Check whether the tree is empty. |
| */ |
| if (!p) |
| return NULL; |
| |
| /* |
| * Iteratively descend to the leftmost leaf in the tree. |
| */ |
| while (p->lft != NULL) |
| p = p->lft; |
| |
| return p; |
| } |
| |
| /** Insert new node into AVL tree. |
| * |
| * @param t AVL tree. |
| * @param newnode New node to be inserted. |
| */ |
| void avltree_insert(avltree_t *t, avltree_node_t *newnode) |
| { |
| avltree_node_t *par; |
| avltree_node_t *gpa; |
| avltree_node_t *top; |
| avltree_node_t **dpc; |
| uint64_t key; |
| |
| ASSERT(t); |
| ASSERT(newnode); |
| |
| /* |
| * Creating absolute key. |
| */ |
| key = newnode->key + t->base; |
| |
| /* |
| * Iteratively descend to the leaf that can contain the new node. |
| * Last node with non-zero balance in the way to leaf is stored as top - |
| * it is a place of possible inbalance. |
| */ |
| dpc = &t->root; |
| gpa = NULL; |
| top = t->root; |
| while ((par = (*dpc)) != NULL) { |
| if (par->balance != 0) { |
| top = par; |
| } |
| gpa = par; |
| dpc = par->key > key ? &par->lft: &par->rgt; |
| } |
| |
| /* |
| * Initialize new node. |
| */ |
| newnode->key = key; |
| newnode->lft = NULL; |
| newnode->rgt = NULL; |
| newnode->par = gpa; |
| newnode->balance = 0; |
| |
| /* |
| * Insert first node into the empty tree. |
| */ |
| if (t->root == NULL) { |
| *dpc = newnode; |
| return; |
| } |
| |
| /* |
| * Insert new node into previously found leaf place. |
| */ |
| *dpc = newnode; |
| |
| /* |
| * If the tree contains one node - end. |
| */ |
| if (top == NULL) |
| return; |
| |
| /* |
| * Store pointer of top's father which points to the node with |
| * potentially broken balance (top). |
| */ |
| if (top->par == NULL) { |
| dpc = &t->root; |
| } else { |
| if (top->par->lft == top) |
| dpc = &top->par->lft; |
| else |
| dpc = &top->par->rgt; |
| } |
| |
| /* |
| * Repair all balances on the way from top node to the newly inserted |
| * node. |
| */ |
| par = top; |
| while (par != newnode) { |
| if (par->key > key) { |
| par->balance--; |
| par = par->lft; |
| } else { |
| par->balance++; |
| par = par->rgt; |
| } |
| } |
| |
| /* |
| * To balance the tree, we must check and balance top node. |
| */ |
| if (top->balance == -2) { |
| par = top->lft; |
| if (par->balance == -1) { |
| /* |
| * LL rotation. |
| */ |
| top->lft = par->rgt; |
| if (top->lft != NULL) |
| top->lft->par = top; |
| par->par = top->par; |
| top->par = par; |
| par->rgt = top; |
| par->balance = 0; |
| top->balance = 0; |
| *dpc = par; |
| } else { |
| /* |
| * LR rotation. |
| */ |
| ASSERT(par->balance == 1); |
| |
| gpa = par->rgt; |
| par->rgt = gpa->lft; |
| if (gpa->lft != NULL) |
| gpa->lft->par = par; |
| gpa->lft = par; |
| par->par = gpa; |
| top->lft = gpa->rgt; |
| if (gpa->rgt != NULL) |
| gpa->rgt->par = top; |
| gpa->rgt = top; |
| gpa->par = top->par; |
| top->par = gpa; |
| |
| if (gpa->balance == -1) { |
| par->balance = 0; |
| top->balance = 1; |
| } else if (gpa->balance == 0) { |
| par->balance = 0; |
| top->balance = 0; |
| } else { |
| par->balance = -1; |
| top->balance = 0; |
| } |
| gpa->balance = 0; |
| *dpc = gpa; |
| } |
| } else if (top->balance == 2) { |
| par = top->rgt; |
| if (par->balance == 1) { |
| /* |
| * RR rotation. |
| */ |
| top->rgt = par->lft; |
| if (top->rgt != NULL) |
| top->rgt->par = top; |
| par->par = top->par; |
| top->par = par; |
| par->lft = top; |
| par->balance = 0; |
| top->balance = 0; |
| *dpc = par; |
| } else { |
| /* |
| * RL rotation. |
| */ |
| ASSERT(par->balance == -1); |
| |
| gpa = par->lft; |
| par->lft = gpa->rgt; |
| if (gpa->rgt != NULL) |
| gpa->rgt->par = par; |
| gpa->rgt = par; |
| par->par = gpa; |
| top->rgt = gpa->lft; |
| if (gpa->lft != NULL) |
| gpa->lft->par = top; |
| gpa->lft = top; |
| gpa->par = top->par; |
| top->par = gpa; |
| |
| if (gpa->balance == 1) { |
| par->balance = 0; |
| top->balance = -1; |
| } else if (gpa->balance == 0) { |
| par->balance = 0; |
| top->balance = 0; |
| } else { |
| par->balance = 1; |
| top->balance = 0; |
| } |
| gpa->balance = 0; |
| *dpc = gpa; |
| } |
| } else { |
| /* |
| * Balance is not broken, insertion is finised. |
| */ |
| return; |
| } |
| |
| } |
| |
| /** Repair the tree after reparenting node u. |
| * |
| * If node u has no parent, mark it as the root of the whole tree. Otherwise |
| * node v represents stale address of one of the children of node u's parent. |
| * Replace v with w as node u parent's child (for most uses, u and w will be the |
| * same). |
| * |
| * @param t AVL tree. |
| * @param u Node whose new parent has a stale child pointer. |
| * @param v Stale child of node u's new parent. |
| * @param w New child of node u's new parent. |
| * @param dir If not NULL, address of the variable where to store information |
| * about whether w replaced v in the left or the right subtree of |
| * u's new parent. |
| * @param ro Read only operation; do not modify any tree pointers. This is |
| * useful for tracking direction via the dir pointer. |
| * |
| * @return Zero if w became the new root of the tree, otherwise return |
| * non-zero. |
| */ |
| static int |
| repair(avltree_t *t, avltree_node_t *u, avltree_node_t *v, avltree_node_t *w, |
| int *dir, int ro) |
| { |
| if (u->par == NULL) { |
| if (!ro) |
| t->root = w; |
| return 0; |
| } else { |
| if (u->par->lft == v) { |
| if (!ro) |
| u->par->lft = w; |
| if (dir) |
| *dir = LEFT; |
| } else { |
| ASSERT(u->par->rgt == v); |
| if (!ro) |
| u->par->rgt = w; |
| if (dir) |
| *dir = RIGHT; |
| } |
| } |
| return 1; |
| } |
| |
| #define REBALANCE(DIR1, DIR2, SIGN) \ |
| if (cur->balance == -1 * SIGN) { \ |
| par->balance = 0; \ |
| gpa->balance = 1 * SIGN; \ |
| if (gpa->DIR1) \ |
| gpa->DIR1->par = gpa; \ |
| par->DIR2->par = par; \ |
| } else if (cur->balance == 0) { \ |
| par->balance = 0; \ |
| gpa->balance = 0; \ |
| if (gpa->DIR1) \ |
| gpa->DIR1->par = gpa; \ |
| if (par->DIR2) \ |
| par->DIR2->par = par; \ |
| } else { \ |
| par->balance = -1 * SIGN; \ |
| gpa->balance = 0; \ |
| if (par->DIR2) \ |
| par->DIR2->par = par; \ |
| gpa->DIR1->par = gpa; \ |
| } \ |
| cur->balance = 0; |
| |
| #define REBALANCE_LR() REBALANCE(lft, rgt, 1) |
| #define REBALANCE_RL() REBALANCE(rgt, lft, -1) |
| |
| /** Delete a node from the AVL tree. |
| * |
| * Because multiple identical keys are allowed, the parent pointers are |
| * essential during deletion. |
| * |
| * @param t AVL tree structure. |
| * @param node Address of the node which will be deleted. |
| */ |
| void avltree_delete(avltree_t *t, avltree_node_t *node) |
| { |
| avltree_node_t *cur; |
| avltree_node_t *par; |
| avltree_node_t *gpa; |
| int dir; |
| |
| ASSERT(t); |
| ASSERT(node); |
| |
| if (node->lft == NULL) { |
| if (node->rgt) { |
| /* |
| * Replace the node with its only right son. |
| * |
| * Balance of the right son will be repaired in the |
| * balancing cycle. |
| */ |
| cur = node->rgt; |
| cur->par = node->par; |
| gpa = cur; |
| dir = RIGHT; |
| cur->balance = node->balance; |
| } else { |
| if (node->par == NULL) { |
| /* |
| * The tree has only one node - it will become |
| * an empty tree and the balancing can end. |
| */ |
| t->root = NULL; |
| return; |
| } |
| /* |
| * The node has no child, it will be deleted with no |
| * substitution. |
| */ |
| gpa = node->par; |
| cur = NULL; |
| dir = (gpa->lft == node) ? LEFT: RIGHT; |
| } |
| } else { |
| /* |
| * The node has the left son. Find a node with the smallest key |
| * in the left subtree and replace the deleted node with that |
| * node. |
| */ |
| for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt) |
| ; |
| |
| if (cur != node->lft) { |
| /* |
| * The rightmost node of the deleted node's left subtree |
| * was found. Replace the deleted node with this node. |
| * Cutting off of the found node has two cases that |
| * depend on its left son. |
| */ |
| if (cur->lft) { |
| /* |
| * The found node has a left son. |
| */ |
| gpa = cur->lft; |
| gpa->par = cur->par; |
| dir = LEFT; |
| gpa->balance = cur->balance; |
| } else { |
| dir = RIGHT; |
| gpa = cur->par; |
| } |
| cur->par->rgt = cur->lft; |
| cur->lft = node->lft; |
| cur->lft->par = cur; |
| } else { |
| /* |
| * The left son of the node hasn't got a right son. The |
| * left son will take the deleted node's place. |
| */ |
| dir = LEFT; |
| gpa = cur; |
| } |
| if (node->rgt) |
| node->rgt->par = cur; |
| cur->rgt = node->rgt; |
| cur->balance = node->balance; |
| cur->par = node->par; |
| } |
| |
| /* |
| * Repair the parent node's pointer which pointed previously to the |
| * deleted node. |
| */ |
| (void) repair(t, node, node, cur, NULL, false); |
| |
| /* |
| * Repair cycle which repairs balances of nodes on the way from from the |
| * cut-off node up to the root. |
| */ |
| for (;;) { |
| if (dir == LEFT) { |
| /* |
| * Deletion was made in the left subtree. |
| */ |
| gpa->balance++; |
| if (gpa->balance == 1) { |
| /* |
| * Stop balancing, the tree is balanced. |
| */ |
| break; |
| } else if (gpa->balance == 2) { |
| /* |
| * Bad balance, heights of left and right |
| * subtrees differ more than by one. |
| */ |
| par = gpa->rgt; |
| |
| if (par->balance == -1) { |
| /* |
| * RL rotation. |
| */ |
| |
| cur = par->lft; |
| par->lft = cur->rgt; |
| cur->rgt = par; |
| gpa->rgt = cur->lft; |
| cur->lft = gpa; |
| |
| /* |
| * Repair balances and paternity of |
| * children, depending on the balance |
| * factor of the grand child (cur). |
| */ |
| REBALANCE_RL(); |
| |
| /* |
| * Repair paternity. |
| */ |
| cur->par = gpa->par; |
| gpa->par = cur; |
| par->par = cur; |
| |
| if (!repair(t, cur, gpa, cur, &dir, |
| false)) |
| break; |
| gpa = cur->par; |
| } else { |
| /* |
| * RR rotation. |
| */ |
| |
| gpa->rgt = par->lft; |
| if (par->lft) |
| par->lft->par = gpa; |
| par->lft = gpa; |
| |
| /* |
| * Repair paternity. |
| */ |
| par->par = gpa->par; |
| gpa->par = par; |
| |
| if (par->balance == 0) { |
| /* |
| * The right child of the |
| * balanced node is balanced, |
| * after RR rotation is done, |
| * the whole tree will be |
| * balanced. |
| */ |
| par->balance = -1; |
| gpa->balance = 1; |
| |
| (void) repair(t, par, gpa, par, |
| NULL, false); |
| break; |
| } else { |
| par->balance = 0; |
| gpa->balance = 0; |
| if (!repair(t, par, gpa, par, |
| &dir, false)) |
| break; |
| } |
| gpa = par->par; |
| } |
| } else { |
| /* |
| * Repair the pointer which pointed to the |
| * balanced node. If it was root then balancing |
| * is finished else continue with the next |
| * iteration (parent node). |
| */ |
| if (!repair(t, gpa, gpa, NULL, &dir, true)) |
| break; |
| gpa = gpa->par; |
| } |
| } else { |
| /* |
| * Deletion was made in the right subtree. |
| */ |
| gpa->balance--; |
| if (gpa->balance == -1) { |
| /* |
| * Stop balancing, the tree is balanced. |
| */ |
| break; |
| } else if (gpa->balance == -2) { |
| /* |
| * Bad balance, heights of left and right |
| * subtrees differ more than by one. |
| */ |
| par = gpa->lft; |
| |
| if (par->balance == 1) { |
| /* |
| * LR rotation. |
| */ |
| |
| cur = par->rgt; |
| par->rgt = cur->lft; |
| cur->lft = par; |
| gpa->lft = cur->rgt; |
| cur->rgt = gpa; |
| |
| /* |
| * Repair balances and paternity of |
| * children, depending on the balance |
| * factor of the grand child (cur). |
| */ |
| REBALANCE_LR(); |
| |
| /* |
| * Repair paternity. |
| */ |
| cur->par = gpa->par; |
| gpa->par = cur; |
| par->par = cur; |
| |
| if (!repair(t, cur, gpa, cur, &dir, |
| false)) |
| break; |
| gpa = cur->par; |
| } else { |
| /* |
| * LL rotation. |
| */ |
| |
| gpa->lft = par->rgt; |
| if (par->rgt) |
| par->rgt->par = gpa; |
| par->rgt = gpa; |
| /* |
| * Repair paternity. |
| */ |
| par->par = gpa->par; |
| gpa->par = par; |
| |
| if (par->balance == 0) { |
| /* |
| * The left child of the |
| * balanced node is balanced, |
| * after LL rotation is done, |
| * the whole tree will be |
| * balanced. |
| */ |
| par->balance = 1; |
| gpa->balance = -1; |
| |
| (void) repair(t, par, gpa, par, |
| NULL, false); |
| break; |
| } else { |
| par->balance = 0; |
| gpa->balance = 0; |
| |
| if (!repair(t, par, gpa, par, |
| &dir, false)) |
| break; |
| } |
| gpa = par->par; |
| } |
| } else { |
| /* |
| * Repair the pointer which pointed to the |
| * balanced node. If it was root then balancing |
| * is finished. Otherwise continue with the next |
| * iteration (parent node). |
| */ |
| if (!repair(t, gpa, gpa, NULL, &dir, true)) |
| break; |
| gpa = gpa->par; |
| } |
| } |
| } |
| } |
| |
| |
| /** Delete a node with the smallest key from the AVL tree. |
| * |
| * @param t AVL tree structure. |
| */ |
| bool avltree_delete_min(avltree_t *t) |
| { |
| avltree_node_t *node; |
| |
| /* |
| * Start searching for the smallest key in the tree starting in the root |
| * node and continue in cycle to the leftmost node in the tree (which |
| * must have the smallest key). |
| */ |
| |
| node = t->root; |
| if (!node) |
| return false; |
| |
| while (node->lft != NULL) |
| node = node->lft; |
| |
| avltree_delete(t, node); |
| |
| return true; |
| } |
| |
| /** @} |
| */ |
| |