0,0 → 1,723 |
/* |
* 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 Fast AVL tree implementation. |
* |
* This file implements Fast AVL tree type and operations. |
* |
* Implemented Fast 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. Every FAVL tree has pointer to its node with smallest key that allows |
* search and delete of node with smallest key in constant time. |
* |
* 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/favl.h> |
#include <debug.h> |
|
|
#define AVLTREE_LEFT 0 |
#define AVLTREE_RIGHT 1 |
|
|
/** Search first occurence of given key in FAVL tree. |
* |
* @param t FAVL tree. |
* @param key Key to be searched. |
* |
* @return Pointer to node or NULL if there is no such key. |
*/ |
favltree_node_t *favltree_search(favltree_t *t, uint64_t key) |
{ |
favltree_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 FAVL tree. |
* |
* @param t FAVL tree. |
* @param newnode New node to be inserted. |
*/ |
void favltree_insert(favltree_t *t, favltree_node_t *newnode) |
{ |
favltree_node_t *par; |
favltree_node_t *gpa; |
favltree_node_t *top; |
favltree_node_t **dpc; |
uint64_t key; |
bool leftmost; |
|
ASSERT(t); |
ASSERT(newnode); |
|
/* |
* Creating absolute key. |
*/ |
key = newnode->key + t->base; |
|
/* |
* Iteratively descend to the leaf that can contain new node. |
* Last node with non-zero balance in the way to leaf is stored as top - |
* it si place of possible balance fault. Remember if there was any right child |
* on the way to leaf. |
*/ |
dpc = &t->root; |
gpa = NULL; |
top = t->root; |
leftmost = true; |
while ((par = (*dpc)) != NULL) { |
if (par->balance != 0) { |
top = par; |
} |
gpa = par; |
if (par->key > key) { |
dpc = &par->lft; |
} else { |
dpc = &par->rgt; |
leftmost = false; |
} |
} |
|
/* |
* Initialize new node. |
*/ |
newnode->key = key; |
newnode->lft = NULL; |
newnode->rgt = NULL; |
newnode->par = gpa; |
newnode->balance = 0; |
|
/* |
* Change pointer to node with minimal key if newnode was smaller then every |
* key in tree. |
*/ |
if (leftmost) { |
t->first = newnode; |
} |
|
/* |
* 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 FAVL tree. |
* |
* Because of allowed multiple identical keys parent pointers are essential |
* during deletition. |
* |
* @param t FAVL tree structure. |
* @param node Address of node which will be deleted. |
*/ |
void favltree_delete(favltree_t *t, favltree_node_t *node) |
{ |
favltree_node_t *cur; |
favltree_node_t *par; |
favltree_node_t *gpa; |
uint8_t dir; |
|
ASSERT(t); |
ASSERT(node); |
|
/* |
* If deleted node is node with minimal key then find new minimal key. |
*/ |
if (node == t->first) { |
if (node->rgt) { |
/* |
* Deleted node has right child, find minimal key in right child's left |
* subtree. |
*/ |
cur = node->rgt; |
while (cur->lft) |
cur = cur->lft; |
t->first = cur; |
} else if (node->par) { |
/* |
* Node doesn't have any child but has parent, new minimal key |
* has deleted node's parent. |
*/ |
t->first = node->par; |
} else { |
/* |
* Deleted node is only node in tree then there will be no minimal key. |
*/ |
t->first = NULL; |
} |
} |
|
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 FAVL tree with the smallest key. |
* |
* @param t FAVL tree structure. |
*/ |
bool favltree_delete_min(favltree_t *t) |
{ |
/* |
* Use favltree_delete function to delete node from tree. |
*/ |
favltree_delete(t,t->first); |
|
return true; |
} |