37,14 → 37,16 |
* 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. |
* @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 pointer to its parent which allows insertion of multiple identical keys |
* into tree. |
* Every node has a pointer to its parent which allows insertion of multiple |
* identical keys into the 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. |
* 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> |
51,16 → 53,16 |
#include <debug.h> |
|
|
#define AVLTREE_LEFT 0 |
#define AVLTREE_RIGHT 1 |
#define LEFT 0 |
#define RIGHT 1 |
|
|
/** Search first occurence of given key in AVL tree. |
/** 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 node or NULL if there is no such key. |
* @return Pointer to a node or NULL if there is no such key. |
*/ |
avltree_node_t *avltree_search(avltree_t *t, uint64_t key) |
{ |
75,19 → 77,18 |
p = p->lft; |
else if (p->key < key) |
p = p->rgt; |
else { |
else |
return p; |
} |
} |
return NULL; |
} |
|
|
/** Find node with smallest key in AVL tree. |
/** Find the node with the smallest key in an AVL tree. |
* |
* @param t AVL tree. |
* |
* @return Pointer to node or NULL if there is no node in the 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) |
{ |
94,9 → 95,10 |
avltree_node_t *p = t->root; |
|
/* |
* Check whether tree is empty. |
* Check whether the tree is empty. |
*/ |
if (!p) return NULL; |
if (!p) |
return NULL; |
|
/* |
* Iteratively descend to the leftmost leaf in the tree. |
128,11 → 130,10 |
*/ |
key = newnode->key + t->base; |
|
|
/* |
* Iteratively descend to the leaf that can contain new node. |
* 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 si place of possible balance fault. |
* it is a place of possible inbalance. |
*/ |
dpc = &t->root; |
gpa = NULL; |
155,7 → 156,7 |
newnode->balance = 0; |
|
/* |
* Insert first node into empty tree. |
* Insert first node into the empty tree. |
*/ |
if (t->root == NULL) { |
*dpc = newnode; |
168,24 → 169,27 |
*dpc = newnode; |
|
/* |
* If tree contains one node - end. |
* If the tree contains one node - end. |
*/ |
if (top == NULL) return; |
if (top == NULL) |
return; |
|
/* |
* Store pointer of top's father which points to the node with potentialy broken |
* balance (top). |
* Store pointer of top's father which points to the node with |
* potentially broken balance (top). |
*/ |
if (top->par == NULL) |
if (top->par == NULL) { |
dpc = &t->root; |
else |
} else { |
if (top->par->lft == top) |
dpc = &(top->par->lft); |
dpc = &top->par->lft; |
else |
dpc = &(top->par->rgt); |
dpc = &top->par->rgt; |
} |
|
/* |
* Repair all balances on the way from top node to newly inserted node. |
* Repair all balances on the way from top node to the newly inserted |
* node. |
*/ |
par = top; |
while (par != newnode) { |
199,7 → 203,7 |
} |
|
/* |
* To balance tree we must check and balance top node. |
* To balance the tree, we must check and balance top node. |
*/ |
if (top->balance == -2) { |
par = top->lft; |
208,7 → 212,8 |
* LL rotation. |
*/ |
top->lft = par->rgt; |
if (top->lft != NULL) top->lft->par = top; |
if (top->lft != NULL) |
top->lft->par = top; |
par->par = top->par; |
top->par = par; |
par->rgt = top; |
222,11 → 227,13 |
|
gpa = par->rgt; |
par->rgt = gpa->lft; |
if (gpa->lft != NULL) gpa->lft->par = par; |
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; |
if (gpa->rgt != NULL) |
gpa->rgt->par = top; |
gpa->rgt = top; |
gpa->par = top->par; |
top->par = gpa; |
250,7 → 257,8 |
* RR rotation. |
*/ |
top->rgt = par->lft; |
if (top->rgt != NULL) top->rgt->par = top; |
if (top->rgt != NULL) |
top->rgt->par = top; |
par->par = top->par; |
top->par = par; |
par->lft = top; |
264,11 → 272,13 |
|
gpa = par->lft; |
par->lft = gpa->rgt; |
if (gpa->rgt != NULL) gpa->rgt->par = par; |
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; |
if (gpa->lft != NULL) |
gpa->lft->par = top; |
gpa->lft = top; |
gpa->par = top->par; |
top->par = gpa; |
294,13 → 304,13 |
|
} |
|
/** Delete node from AVL tree. |
/** Delete a node from the AVL tree. |
* |
* Because of allowed multiple identical keys parent pointers are essential |
* during deletition. |
* Because multiple identical keys are allowed, the parent pointers are |
* essential during deletion. |
* |
* @param t AVL tree structure. |
* @param node Address of node which will be deleted. |
* @param node Address of the node which will be deleted. |
*/ |
void avltree_delete(avltree_t *t, avltree_node_t *node) |
{ |
312,60 → 322,62 |
ASSERT(t); |
ASSERT(node); |
|
|
if (node->lft == NULL) { |
if (node->rgt) { |
/* |
* Replace node with its only right son. |
* Replace the node with its only right son. |
* |
* Balance of right son will be repaired in balancing cycle. |
* Balance of the right son will be repaired in the |
* balancing cycle. |
*/ |
cur = node->rgt; |
cur->par = node->par; |
gpa = cur; |
dir = AVLTREE_RIGHT; |
dir = RIGHT; |
cur->balance = node->balance; |
} else { |
if (node->par == NULL) { |
/* |
* Tree has only one node - it will be empty tree and balancing can end. |
* The tree has only one node - it will become |
* an empty tree and the balancing can end. |
*/ |
t->root = NULL; |
return; |
} |
/* |
* Node has no child, will be deleted with no substitution. |
* The node has no child, it will be deleted with no |
* substitution. |
*/ |
gpa = node->par; |
cur = NULL; |
dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT; |
dir = (gpa->lft == node) ? LEFT: RIGHT; |
} |
} else { |
/* |
* Node has left and right son. Find a node with smallest key in left subtree |
* and replace deleted node with that node. |
* The node has left and right 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) |
; |
|
//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. |
* 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) { |
/* |
* Founded node has left son. |
* The found node has a left son. |
*/ |
gpa = cur->lft; |
gpa->par = cur->par; |
dir = AVLTREE_LEFT; |
dir = LEFT; |
gpa->balance = cur->balance; |
} else { |
dir = AVLTREE_RIGHT; |
dir = RIGHT; |
gpa = cur->par; |
} |
cur->par->rgt = cur->lft; |
373,12 → 385,14 |
cur->lft->par = cur; |
} else { |
/* |
* Left son of node hasn't got right son. Left son will take deleted node's place. |
* The left son of the node hasn't got a right son. The |
* left son will take the deleted node's place. |
*/ |
dir = AVLTREE_LEFT; |
dir = LEFT; |
gpa = cur; |
} |
if (node->rgt) node->rgt->par = cur; |
if (node->rgt) |
node->rgt->par = cur; |
cur->rgt = node->rgt; |
cur->balance = node->balance; |
cur->par = node->par; |
385,7 → 399,8 |
} |
|
/* |
* Repair parent nodes pointer which pointed previously to deleted node. |
* Repair the parent node's pointer which pointed previously to the |
* deleted node. |
*/ |
if (node->par == NULL) { |
t->root = cur; |
398,22 → 413,24 |
} |
|
/* |
* Repair cycle which repairs balances of nodes in way from cutted noded down to root. |
* Repair cycle which repairs balances of nodes on the way from from the |
* cut-off node up to the root. |
*/ |
for(;;) { |
if (dir == AVLTREE_LEFT) { |
if (dir == LEFT) { |
/* |
* Deletition was made in left subtree. |
* Deletion was made in the left subtree. |
*/ |
gpa->balance++; |
if (gpa->balance == +1) { |
if (gpa->balance == 1) { |
/* |
* Stop balancing, tree is balanced. |
* Stop balancing, the tree is balanced. |
*/ |
break; |
} else if (gpa->balance == +2) { |
} else if (gpa->balance == 2) { |
/* |
* Bad balance, heights of left and right subtrees differs more then is allowed. |
* Bad balance, heights of left and right |
* subtrees differ more than by one. |
*/ |
par = gpa->rgt; |
|
429,22 → 446,27 |
cur->lft = gpa; |
|
/* |
* Repair balances and paternity of childs in dependence on |
* balance factor of grand child (cur). |
* Repair balances and paternity of |
* children, depending on the balance |
* factor of the grand child (cur). |
*/ |
if (cur->balance == +1) { |
if (cur->balance == 1) { |
par->balance = 0; |
gpa->balance = -1; |
if (gpa->rgt) gpa->rgt->par = gpa; |
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; |
if (gpa->rgt) |
gpa->rgt->par = gpa; |
if (par->lft) |
par->lft->par = par; |
} else { |
par->balance = +1; |
par->balance = 1; |
gpa->balance = 0; |
if (par->lft) par->lft->par = par; |
if (par->lft) |
par->lft->par = par; |
gpa->rgt->par = gpa; |
} |
cur->balance = 0; |
457,20 → 479,24 |
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). |
* Repair the pointer which pointed to |
* the balanced node. If it was root |
* then the balancing is finished. |
* Otherwise continue with the next |
* iteration (parent node). |
*/ |
if (cur->par == NULL) { |
t->root = cur; |
break; |
} else |
} else { |
if (cur->par->lft == gpa) { |
cur->par->lft = cur; |
dir = AVLTREE_LEFT; |
dir = LEFT; |
} else { |
cur->par->rgt = cur; |
dir = AVLTREE_RIGHT; |
dir = RIGHT; |
} |
} |
gpa = cur->par; |
} else { |
/* |
478,7 → 504,8 |
*/ |
|
gpa->rgt = par->lft; |
if (par->lft) par->lft->par = gpa; |
if (par->lft) |
par->lft->par = gpa; |
par->lft = gpa; |
|
/* |
489,41 → 516,56 |
|
if (par->balance == 0) { |
/* |
* Right child of balanced node is balanced, after RR rotation is done, whole |
* tree will be balanced. |
* 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; |
gpa->balance = 1; |
|
/* |
* Repair pointer which pointed to balanced node and finish balancing. |
* Repair the pointer which |
* pointed to the 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; |
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). |
* 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 (par->par == NULL) { |
t->root = par; |
break; |
} else { |
|
if (par->par->lft == gpa) { |
par->par->lft = par; |
dir = AVLTREE_LEFT; |
if (par->par->lft == |
gpa) { |
par->par->lft = |
par; |
dir = LEFT; |
} else { |
par->par->rgt = par; |
dir = AVLTREE_RIGHT; |
par->par->rgt = |
par; |
dir = RIGHT; |
} |
} |
} |
531,35 → 573,39 |
} |
} else { |
/* |
* Repair pointer which pointed to balanced node. If it was root then balancing |
* is finished else continue in next iteration (parent node). |
* 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 (!gpa->par) break; |
if (!gpa->par) |
break; |
|
if (gpa->par->lft == gpa) { |
dir = AVLTREE_LEFT; |
dir = LEFT; |
} else { |
dir = AVLTREE_RIGHT; |
dir = RIGHT; |
} |
gpa = gpa->par; |
} |
} else { |
/* |
* Deletition was made in right subtree. |
* Deletion was made in the right subtree. |
*/ |
gpa->balance--; |
if (gpa->balance == -1) { |
/* |
* Stop balancing, tree is balanced. |
* Stop balancing, the tree is balanced. |
*/ |
break; |
} else if (gpa->balance == -2) { |
/* |
* Bad balance, heights of left and right subtrees differs more then is allowed. |
* Bad balance, heights of left and right |
* subtrees differ more than by one. |
*/ |
par = gpa->lft; |
|
if (par->balance == +1) { |
if (par->balance == 1) { |
/* |
* LR rotation. |
*/ |
571,22 → 617,27 |
cur->rgt = gpa; |
|
/* |
* Repair balances and paternity of childs in dependence on |
* balance factor of grand child (cur). |
* Repair balances and paternity of |
* children, depending on the balance |
* factor of the grand child (cur). |
*/ |
if (cur->balance == -1) { |
par->balance = 0; |
gpa->balance = +1; |
if (gpa->lft) gpa->lft->par = gpa; |
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; |
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; |
if (par->rgt) |
par->rgt->par = par; |
gpa->lft->par = gpa; |
} |
cur->balance = 0; |
599,20 → 650,24 |
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). |
* 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 (cur->par == NULL) { |
t->root = cur; |
break; |
} else |
} else { |
if (cur->par->lft == gpa) { |
cur->par->lft = cur; |
dir = AVLTREE_LEFT; |
dir = LEFT; |
} else { |
cur->par->rgt = cur; |
dir = AVLTREE_RIGHT; |
dir = RIGHT; |
} |
} |
gpa = cur->par; |
} else { |
/* |
620,7 → 675,8 |
*/ |
|
gpa->lft = par->rgt; |
if (par->rgt) par->rgt->par = gpa; |
if (par->rgt) |
par->rgt->par = gpa; |
par->rgt = gpa; |
/* |
* Repair paternity. |
630,41 → 686,57 |
|
if (par->balance == 0) { |
/* |
* Left child of balanced node is balanced, after RR rotation is done, whole |
* tree will be balanced. |
* The left child of the |
* balanced node is balanced, |
* after LL rotation is done, |
* the whole tree will be |
* balanced. |
*/ |
par->balance = +1; |
par->balance = 1; |
gpa->balance = -1; |
|
/* |
* Repair pointer which pointed to balanced node and finish balancing. |
* Repair the pointer which |
* pointed to the 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; |
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). |
* 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 (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; |
if (par->par->lft == |
gpa) { |
par->par->lft = |
par; |
dir = LEFT; |
} else { |
par->par->rgt = par; |
dir = AVLTREE_RIGHT; |
par->par->rgt = |
par; |
dir = RIGHT; |
} |
} |
} |
672,15 → 744,18 |
} |
} else { |
/* |
* Repair pointer which pointed to balanced node. If it was root then balancing |
* is finished else continue in next iteration (parent node). |
* 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 (!gpa->par) break; |
if (!gpa->par) |
break; |
|
if (gpa->par->lft == gpa) { |
dir = AVLTREE_LEFT; |
dir = LEFT; |
} else { |
dir = AVLTREE_RIGHT; |
dir = RIGHT; |
} |
gpa = gpa->par; |
} |
689,7 → 764,7 |
} |
|
|
/** Delete node from AVL tree with the smallest key. |
/** Delete a node with the smallest key from the AVL tree. |
* |
* @param t AVL tree structure. |
*/ |
698,20 → 773,22 |
avltree_node_t *node; |
|
/* |
* 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. |
* 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; |
if (!node) |
return false; |
|
while (node->lft != NULL) |
node = node->lft; |
|
/* |
* Use avltree_delete function to delete node from tree. |
*/ |
avltree_delete(t,node); |
|
return true; |
} |
|
/** @} |
*/ |