/*
* Copyright (c) 2006 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 binary search tree with non-unique keys
* @li Difference of heights of left and right subtree of every node is max 1.
*
* Every node has pointer to its parent which allows insertion of multiple identical keys
* into tree.
*
* Be careful of using this tree because of 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>
#include <panic.h>
#define AVLTREE_LEFT 0
#define AVLTREE_RIGHT 1
/** Search first occurence of given key in AVL tree.
*
* @param t AVL tree.
* @param key Key to be searched.
*
* @return Pointer to value 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;
}
/** 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 will contain new node.
* Last node with non-zero balance in the way to leaf is stored as top -
* it si place of possible balance failure.
*/
dpc = &t->root;
gpa = NULL;
top = t->root;
while (par = *dpc) {
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 empty tree.
*/
if (t->root == NULL) {
*dpc = newnode;
return;
}
/*
* Insert new node into previously found leaf place.
*/
*dpc = newnode;
/*
* If tree contains one node - end.
*/
if (top == NULL) return;
/*
* Store pointer of top's father which points to the node with potentialy 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 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 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 = 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 = 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 = 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 = top->balance = 0;
} else {
par->balance = 1;
top->balance = 0;
}
gpa->balance = 0;
*dpc = gpa;
}
} else {
/*
* Balance is not broken, insertion is finised.
*/
return;
}
}
/** Delete node from AVL tree.
*
* Because of allowed multiple identical keys parent pointers are essential
* during deletition.
*
* @param t AVL tree structure.
* @param node Address of 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;
uint8_t dir;
ASSERT(t);
ASSERT(node);
if (node->lft == NULL) {
if (node->rgt) {
/*
* Replace node with its only right son.
*
* Balance of right son will be repaired in balancing cycle.
*/
cur = node->rgt;
cur->par = node->par;
gpa = cur;
dir = AVLTREE_RIGHT;
cur->balance = node->balance;
} else {
if (node->par == NULL) {
/*
* Tree has only one node - it will be empty tree and balancing can end.
*/
t->root = NULL;
return;
}
/*
* Node has no child, will be deleted with no substitution.
*/
gpa = node->par;
cur = NULL;
dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT;
}
} else {
/*
* Node has left and right son. Find a node with smallest key in left subtree
* and replace deleted node with that node.
*/
for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
;
//cur obsahuje uzel, ktery vlozim misto uzlu node
if (cur != node->lft) {
/*
* The most right node of deleted node's left subtree was found. Replace
* deleted node with this node. Cutting founded node has two cases in
* dependence on its left son.
*/
if (cur->lft) {
/*
* Founded node has left son.
*/
gpa = cur->lft;
gpa->par = cur->par;
dir = AVLTREE_LEFT;
gpa->balance = cur->balance;
} else {
dir = AVLTREE_RIGHT;
gpa = cur->par;
}
cur->par->rgt = cur->lft;
cur->lft = node->lft;
cur->lft->par = cur;
} else {
/*
* Left son of node hasn't got right son. Left son will take deleted node's place.
*/
dir = AVLTREE_LEFT;
gpa = cur;
}
if (node->rgt) node->rgt->par = cur;
cur->rgt = node->rgt;
cur->balance = node->balance;
cur->par = node->par;
}
/*
* Repair parent nodes pointer which pointed previously to deleted node.
*/
if (node->par == NULL) {
t->root = cur;
} else {
if (node->par->lft == node) {
node->par->lft = cur;
} else {
node->par->rgt = cur;
}
}
/*
* Repair cycle which repairs balances of nodes in way from cutted noded down to root.
*/
for(;;) {
if (dir == AVLTREE_LEFT) {
/*
* Deletition was made in left subtree.
*/
gpa->balance++;
if (gpa->balance == +1) {
/*
* Stop balancing, tree is balanced.
*/
break;
} else if (gpa->balance == +2) {
/*
* Bad balance, heights of left and right subtrees differs more then is allowed.
*/
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 childs in dependence on
* balance factor of grand child (cur).
*/
if (cur->balance == +1) {
par->balance = 0;
gpa->balance = -1;
if (gpa->rgt) gpa->rgt->par = gpa;
par->lft->par = par;
} else if (cur->balance == 0) {
par->balance = gpa->balance = 0;
if (gpa->rgt) gpa->rgt->par = gpa;
if (par->lft) par->lft->par = par;
} else {
par->balance = +1;
gpa->balance = 0;
if (par->lft) par->lft->par = par;
gpa->rgt->par = gpa;
}
cur->balance = 0;
/*
* Repair paternity.
*/
cur->par = gpa->par;
gpa->par = cur;
par->par = cur;
/*
* Repair pointer which pointed to balanced node. If it was root then balancing
* is finished else continue in next iteration (parent node).
*/
if (cur->par == NULL) {
t->root = cur;
break;
} else
if (cur->par->lft == gpa) {
cur->par->lft = cur;
dir = AVLTREE_LEFT;
} else {
cur->par->rgt = cur;
dir = AVLTREE_RIGHT;
}
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) {
/*
* Right child of balanced node is balanced, after RR rotation is done, whole
* tree will be balanced.
*/
par->balance = -1;
gpa->balance = +1;
/*
* Repair pointer which pointed to balanced node and finish balancing.
*/
if (par->par == NULL) {
t->root = par;
} else
if (par->par->lft == gpa) {
par->par->lft = par;
} else {
par->par->rgt = par;
}
break;
} else {
par->balance = gpa->balance = 0;
/*
* Repair pointer which pointed to balanced node. If it was root then balancing
* is finished else continue in next iteration (parent node).
*/
if (par->par == NULL) {
t->root = par;
break;
} else {
if (par->par->lft == gpa) {
par->par->lft = par;
dir = AVLTREE_LEFT;
} else {
par->par->rgt = par;
dir = AVLTREE_RIGHT;
}
}
}
gpa = par->par;
}
} else {
/*
* Repair pointer which pointed to balanced node. If it was root then balancing
* is finished else continue in next iteration (parent node).
*/
if (!gpa->par) break;
if (gpa->par->lft == gpa) {
dir = AVLTREE_LEFT;
} else {
dir = AVLTREE_RIGHT;
}
gpa = gpa->par;
}
} else {
/*
* Deletition was made in right subtree.
*/
gpa->balance--;
if (gpa->balance == -1) {
/*
* Stop balancing, tree is balanced.
*/
break;
} else if (gpa->balance == -2) {
/*
* Bad balance, heights of left and right subtrees differs more then is allowed.
*/
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 childs in dependence on
* balance factor of grand child (cur).
*/
if (cur->balance == -1) {
par->balance = 0;
gpa->balance = +1;
if (gpa->lft) gpa->lft->par = gpa;
par->rgt->par = par;
} else if (cur->balance == 0) {
par->balance = gpa->balance = 0;
if (gpa->lft) gpa->lft->par = gpa;
if (par->rgt) par->rgt->par = par;
} else {
par->balance = -1;
gpa->balance = 0;
if (par->rgt) par->rgt->par = par;
gpa->lft->par = gpa;
}
cur->balance = 0;
/*
* Repair paternity.
*/
cur->par = gpa->par;
gpa->par = cur;
par->par = cur;
/*
* Repair pointer which pointed to balanced node. If it was root then balancing
* is finished else continue in next iteration (parent node).
*/
if (cur->par == NULL) {
t->root = cur;
break;
} else
if (cur->par->lft == gpa) {
cur->par->lft = cur;
dir = AVLTREE_LEFT;
} else {
cur->par->rgt = cur;
dir = AVLTREE_RIGHT;
}
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) {
/*
* Left child of balanced node is balanced, after RR rotation is done, whole
* tree will be balanced.
*/
par->balance = +1;
gpa->balance = -1;
/*
* Repair pointer which pointed to balanced node and finish balancing.
*/
if (par->par == NULL) {
t->root = par;
} else
if (par->par->lft == gpa) {
par->par->lft = par;
} else {
par->par->rgt = par;
}
break;
} else {
par->balance = gpa->balance = 0;
/*
* Repair pointer which pointed to balanced node. If it was root then balancing
* is finished else continue in next iteration (parent node).
*/
if (par->par == NULL) {
t->root = par;
break;
} else {
if (par->par->lft == gpa) { //v cyklu jsem ani jednou neskocil - cur nema praveho syna
par->par->lft = par;
dir = AVLTREE_LEFT;
} else {
par->par->rgt = par;
dir = AVLTREE_RIGHT;
}
}
}
gpa = par->par;
}
} else {
/*
* Repair pointer which pointed to balanced node. If it was root then balancing
* is finished else continue in next iteration (parent node).
*/
if (!gpa->par) break;
if (gpa->par->lft == gpa) {
dir = AVLTREE_LEFT;
} else {
dir = AVLTREE_RIGHT;
}
gpa = gpa->par;
}
}
}
}
/** Delete node from AVL tree with the smallest key and set base of tree to that key.
*
* @param t AVL tree structure.
*/
avltree_node_t *avltree_delete_min(avltree_t *t)
{
avltree_node_t *node;
uint64_t key;
/*
* Start search of smallest key in tree in the root node and
* continue in cycle to the most left node in the tree which
* must have smallest key.
*/
node = t->root;
if (!node) return false;
while (node->lft != NULL)
node = node->lft;
/*
* Store key and use avltree_delete function to delete node from tree.
*/
key = node->key;
avltree_delete(t,node);
/*
* Change base to the key of deleted node.
*/
t->base = key;
return true;
}