0,0 → 1,1029 |
/* |
* 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 Extended AVL tree with relative keys implementation. |
* |
* This file implements Extended AVL tree with relative keys type and operations. |
* |
* Extended AVL tree with relative keys (ExtAvlrel tree) has the following properties: |
* @li it is binary search tree with unique real keys |
* @li right subtree of every node is Avl tree |
* @li height of left subtree of every node is not greater then height of right subtree + 1 |
* @li nodes with the same real keys are linked to the tree nodes of the same key, they are not tree nodes |
* @li every node is part of doubly linked list with head |
* @li nodes are connected in the list ascendentaly according to their real keys, node key is |
* only difference between previous real node's key and its real node's key |
* @li real key is either equal node key if node is leftmost node in tree or sum of all |
* node keys with smaller real key |
* |
* Be careful of using this tree because node keys are not equal real keys (except leftmost node). |
*/ |
|
#include <adt/extavlrel.h> |
#include <debug.h> |
#include <panic.h> |
|
|
#define AVLTREE_LEFT 0 |
#define AVLTREE_RIGHT 1 |
|
|
/* Returns height of tree -1 */ |
#define extavlreltree_tree_height(node) ((node) == NULL) ? (-1) : max(((node)->lft_height),((node)->rgt_height)) |
|
/** Search first occurence (oldest node with this real key) of given key in ExtAVLrel tree. |
* |
* @param t ExtAVLrel tree. |
* @param key Key to be searched. |
* |
* @return Pointer to value or NULL if there is no such key. |
*/ |
extavlreltree_node_t *extavlreltree_search(extavlreltree_t t, uint64_t key) |
{ |
extavlreltree_node_t *cur; |
uint64_t sum, s; |
|
/* |
* Find right subtree in way up to the root where can be node with given key. |
* Root node is the last node in the way up, when we reach root, it means, |
* that searched node belongs to the right subtree of root. |
*/ |
sum = 0; |
cur = t->head.next; |
while (1) { |
sum += cur->key + cur->rgt_sum; |
if ((key <= sum) || (cur == t->root)) |
break; |
else |
cur = cur->par; |
} |
|
/* |
* Sorting for cycle. |
* Search for key in choosen subtree. Searching start at cur node which we have found |
* in previous step. It is common search algorithm for binary search tree. |
*/ |
while (cur != NULL) { |
s = sum - cur->rgt_sum; |
if (key < s) { |
/* |
* Left subtree. Find max value in left subtree of cur. |
*/ |
sum -= cur->key + cur->rgt_sum; |
cur = cur->lft; |
} else if (key > s) { |
/* |
* Right subtree. sum has still max value in the right subtree of cur. |
*/ |
cur = cur->rgt; |
} else { |
/* |
* Equal values. We have found node with given key. |
*/ |
return cur; |
} |
} |
return NULL; |
} |
|
|
/** Insert new node into ExtAVL tree. |
* |
* New node's key must be set. |
* |
* @param t ExtAVL tree structure. |
* @param newnode New node to be inserted. |
*/ |
void extavlreltree_insert(extavlreltree_t *t, extavlreltree_node_t *newnode) |
{ |
extavlreltree_node_t *cur; |
extavlreltree_node_t *son; |
extavlreltree_node_t *gpa; |
extavlreltree_node_t *par; |
uint64_t sum, s; |
uint8_t dir; |
/* |
* Condition var - all rgt_sums in the way down to root must be repaired in condition |
* that we came there from right and on the way from repaired node to new node we |
* never turn to the left. Reparation is done in the reparation cycle. |
*/ |
bool repair_rgt_sum; |
|
ASSERT(t); |
ASSERT(newnode); |
|
/* |
* Insert first node into empty tree. Key is left without change (according to definition). |
*/ |
cur = t->head.next; |
if (cur == &t->head) { |
newnode->lft = NULL; |
newnode->rgt = NULL; |
newnode->lft_height = 0; |
newnode->rgt_height = 0; |
newnode->par = NULL; |
newnode->next = &t->head; |
newnode->prev = &t->head; |
newnode->rgt_sum = 0; |
|
t->head.prev = newnode; |
t->head.next = newnode; |
t->root = newnode; |
return; |
} |
|
/* |
* Find right subtree in way up to the root where newnode will be placed. |
* Root node is the last node in the way up, when we reach root, it means, |
* that newnode belongs to the right subtree of root. |
* |
* When max key of cur's right subtree is inserted, while cycle overjumps |
* right node and stops. But in the next sorting for cycle is this situation |
* solved (for cycle jumps back to the left child). |
*/ |
sum = 0; |
while (1) { |
sum += cur->key + cur->rgt_sum; |
if ((newnode->key <= sum) || (cur == t->root)) |
break; |
else |
cur = cur->par; |
} |
|
|
/* |
* Sorting for cycle. |
* Find a place for newnode. Searching start at cur node which we have found |
* in previous step. It is common search algorithm for binary search tree. |
*/ |
for (;;) { |
s = sum - cur->rgt_sum; |
if (newnode->key < s) { |
/* |
* Left subtree. Find max value in left subtree of cur. |
*/ |
sum -= cur->key + cur->rgt_sum; |
|
if (!cur->lft) { |
/* |
* Insert new node to the left. |
*/ |
cur->lft = newnode; |
|
newnode->lft = NULL; |
newnode->rgt = NULL; |
newnode->lft_height = 0; |
newnode->rgt_height = 0; |
newnode->par = cur; |
/* |
* Insert newnode to list. |
*/ |
newnode->next = cur; |
newnode->prev = cur->prev; |
cur->prev->next = newnode; |
cur->prev = newnode; |
|
newnode->key -= sum; |
newnode->rgt_sum = 0; |
/* |
* Repair key of next value (next node always exists). newnode->key |
* has been already set. Needn't check whether newnode->next is head |
* beacause newnode is left child (next node is his father). |
*/ |
newnode->next->key -= newnode->key; |
|
repair_rgt_sum = false; |
dir = AVLTREE_LEFT; |
break; |
} |
cur = cur->lft; |
} else if (newnode->key > s) { |
/* |
* Right subtree. sum has still max value in the right subtree of cur. |
*/ |
|
if (!cur->rgt) { |
cur->rgt = newnode; |
|
newnode->lft = NULL; |
newnode->rgt = NULL; |
newnode->lft_height = 0; |
newnode->rgt_height = 0; |
newnode->par = cur; |
|
/* |
* Find last node in the chain with the same key as cur node. |
*/ |
gpa = cur->next; |
while (gpa != &t->head && gpa->key == 0) |
gpa = gpa->next; |
|
/* |
* Insert new node to list. Right place in the list was found in |
* previous cycle. |
*/ |
newnode->prev = gpa->prev; |
newnode->next = gpa; |
gpa->prev->next = newnode; |
gpa->prev = newnode; |
|
newnode->key -= sum; |
newnode->rgt_sum = 0; |
/* |
* Repair key of next value (next node always exists). newnode->key |
* has been already set. |
*/ |
if (newnode->next != &t->head) |
newnode->next->key -= newnode->key; |
/* |
* All rgt_sums in the way down to root must be repaired in condition |
* that we came there from right and on the way from node to new node we |
* never turn left. |
*/ |
repair_rgt_sum = true; |
dir = AVLTREE_RIGHT; |
break; |
} |
cur = cur->rgt; |
|
} else { |
/* |
* Equal values. Give newnode to the last position of chain with the cur head and |
* end insertion. |
*/ |
gpa = cur->next; |
while (gpa != &t->head && gpa->key == 0) |
gpa = gpa->next; |
/* |
* Insert new node to list in right place. |
*/ |
newnode->prev = gpa->prev; |
newnode->next = gpa; |
gpa->prev->next = newnode; |
gpa->prev = newnode; |
|
newnode->par = NULL; |
newnode->lft = NULL; |
newnode->rgt = NULL; |
newnode->lft_height = 0; |
newnode->rgt_height = 0; |
|
/* |
* Nodes in chains has key equal 0, because difference between previous node and them is 0. |
*/ |
newnode->key = 0; |
newnode->rgt_sum = 0; |
return; |
} |
} |
|
/* |
* Balancing all nodes from newnode's parent down to root. |
*/ |
cur = newnode->par; |
while (true) { |
if (dir == AVLTREE_LEFT) { |
/* |
* Insertion was made in the left subtree - repair left height, stop |
* repairing rgt_sum and check balance of current node. |
*/ |
cur->lft_height = extavlreltree_tree_height(cur->lft) + 1; |
|
repair_rgt_sum = false; |
|
if ((cur->rgt_height - cur->lft_height) <= -2) { |
/* |
* Balance was corrupted, must be repaired through LL or LR rotation. |
*/ |
par = cur->par; |
son = cur->lft; |
if ((son->rgt_height - son->lft_height) != 1) { |
/* |
* LL rotation. |
*/ |
gpa = son; |
cur->lft = son->rgt; |
if (cur->lft != NULL) cur->lft->par = cur; |
cur->par = son; |
son->rgt = cur; |
/* |
* Repair heights. |
*/ |
cur->lft_height = son->rgt_height; |
son->rgt_height = extavlreltree_tree_height(cur) + 1; |
/* |
* Repair rgt_sum. |
*/ |
son->rgt_sum += cur->key + cur->rgt_sum; |
} else { |
/* |
* LR rotation. |
*/ |
gpa = son->rgt; |
son->rgt = gpa->lft; |
if (gpa->lft != NULL) gpa->lft->par = son; |
gpa->lft = son; |
son->par = gpa; |
cur->lft = gpa->rgt; |
if (gpa->rgt != NULL) gpa->rgt->par = cur; |
gpa->rgt = cur; |
cur->par = gpa; |
/* |
* Repair heights. |
*/ |
cur->lft_height = gpa->rgt_height; |
son->rgt_height = gpa->lft_height; |
gpa->rgt_height = extavlreltree_tree_height(cur) + 1; |
gpa->lft_height = extavlreltree_tree_height(son) + 1; |
/* |
* Repair rgt_sums. |
*/ |
son->rgt_sum -= gpa->key + gpa->rgt_sum; |
gpa->rgt_sum += cur->key + cur->rgt_sum; |
} |
/* |
* Repair parent of current node. |
*/ |
gpa->par = par; |
} else { |
/* |
* Balance is correct, continue balancing at parent node. |
*/ |
par = cur->par; |
gpa = cur; |
} |
} else { |
/* |
* Insertion was made in the right subtree - repair right height, try to |
* repair rgt_sum and check balance of current node. |
*/ |
cur->rgt_height = extavlreltree_tree_height(cur->rgt) + 1; |
|
if (repair_rgt_sum) { |
cur->rgt_sum += newnode->key; |
} |
|
if ((cur->rgt_height - cur->lft_height) >= 2) { |
/* |
* Balance was corrupted, must be repaired through RL or RR rotation. |
*/ |
par = cur->par; |
son = cur->rgt; |
if ((son->rgt_height - son->lft_height) != -1) { |
/* |
* RR rotation. |
*/ |
gpa = son; |
cur->rgt = son->lft; |
if (cur->rgt != NULL) cur->rgt->par = cur; |
cur->par = son; |
son->lft = cur; |
/* |
* Repair heights. |
*/ |
cur->rgt_height = son->lft_height; |
son->lft_height = extavlreltree_tree_height(cur) + 1; |
/* |
* Repair rgt_sum. |
*/ |
cur->rgt_sum -= son->rgt_sum + son->key; |
} else { |
/* |
* RL rotation. |
*/ |
gpa = son->lft; |
son->lft = gpa->rgt; |
if (gpa->rgt != NULL) gpa->rgt->par = son; |
gpa->rgt = son; |
son->par = gpa; |
cur->rgt = gpa->lft; |
if (gpa->lft != NULL) gpa->lft->par = cur; |
gpa->lft = cur; |
cur->par = gpa; |
/* |
* Repair heights. |
*/ |
cur->rgt_height = gpa->lft_height; |
son->lft_height = gpa->rgt_height; |
gpa->lft_height = extavlreltree_tree_height(cur) + 1; |
gpa->rgt_height = extavlreltree_tree_height(son) + 1; |
/* |
* Repair rgt_sums. |
*/ |
cur->rgt_sum -= son->key + son->rgt_sum + gpa->key + gpa->rgt_sum; |
gpa->rgt_sum += son->key + son->rgt_sum; |
} |
|
/* |
* Repair parent of current node. |
*/ |
gpa->par = par; |
} else { |
/* |
* Balance is correct, continue balancing at parent node. |
*/ |
par = cur->par; |
gpa = cur; |
} |
} |
/* |
* Change parent pointers, set direction where is newnode and |
* continue balancing at parent node or if current node |
* is root then change root atribute pointer and stop |
*/ |
if (par) { |
if (par->lft == cur) { |
par->lft = gpa; |
dir = AVLTREE_LEFT; |
} else { |
par->rgt = gpa; |
dir = AVLTREE_RIGHT; |
} |
} else { |
t->root = gpa; |
break; |
} |
cur = par; |
} |
} |
|
|
/** Delete node from ExtAVLrel tree. |
* |
* @param t ExtAVLrel tree structure. |
* @param node Address of node which will be deleted. |
*/ |
void extavlreltree_delete(extavlreltree_t *t, extavlreltree_node_t *node) |
{ |
extavlreltree_node_t **gpapar; |
extavlreltree_node_t *cur; |
extavlreltree_node_t *par; |
extavlreltree_node_t *gpa; |
int8_t dir; |
int8_t dir2=0; |
uint64_t key; |
int16_t balance; |
/* |
* Condition var - if true then all rgt_sums in the way down to root must be repaired in condition |
* that we came there from right and on the way from repaired node to new node we |
* never turn to the left. Reparation is done in the reparation cycle. |
*/ |
bool repair_rgt_sum; |
|
|
ASSERT(t); |
ASSERT(node); |
|
/* |
* Delete node from list. |
*/ |
node->next->prev = node->prev; |
node->prev->next = node->next; |
|
if (!node->par) { |
if (t->root != node) { |
/* |
* It is list node (not a tree node). Needn't repair tree or anything else. |
*/ |
return; |
} |
repair_rgt_sum = false; |
gpapar = &(t->root); |
} else { |
/* |
* Find tree pointer which points to node. |
*/ |
if (node->par->lft == node) { |
gpapar = &(node->par->lft); |
repair_rgt_sum = false; |
} else { |
gpapar = &(node->par->rgt); |
/* |
* Node is right child - rgt_sum might be repaired. |
*/ |
repair_rgt_sum = true; |
} |
} |
|
|
if (&t->head != node->next && node->next->key == 0) { |
/* |
* Deleted node has at least one node node with the same key which is closest next |
* neighbor in the list, copy node atributes into next node and end. |
*/ |
cur = node->next; |
cur->lft = node->lft; |
cur->rgt = node->rgt; |
cur->par = node->par; |
cur->lft_height = node->lft_height; |
cur->rgt_height = node->rgt_height; |
*gpapar = cur; |
|
if (node->lft) node->lft->par = cur; |
if (node->rgt) node->rgt->par = cur; |
|
cur->key = node->key; |
cur->rgt_sum = node->rgt_sum; |
return; |
} |
|
/* |
* Repair next node's key (it must be difference between previous key and its key). |
*/ |
if (node->next != &t->head) { |
node->next->key += node->key; |
} |
|
/* |
* Check situation in the tree around deleted node. |
*/ |
if (!node->lft) { |
/* |
* Deleted node has not left son. Right son will take deleted node's place. |
*/ |
gpa = node->par; |
if (node->rgt) { |
/* |
* rgt_sum is not corrupted because the biggest key is in right subtree of node |
*/ |
node->rgt->par = gpa; |
repair_rgt_sum = false; |
} else { |
/* |
* node is the biggest key and rgt_sum might be repaired according to which |
* child is node. |
*/ |
key = node->key; |
} |
|
if (!gpa) { |
/* |
* Deleted node is root node. Balancing is finished, change only |
* root pointer in extavltree structure. |
*/ |
*gpapar = node->rgt; |
return; |
} |
dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT; |
|
*gpapar = node->rgt; |
} else { |
/* |
* Node has left son. |
*/ |
cur = node->lft; |
if (!cur->rgt) { |
/* |
* Left son of node hasn't got right son. Left son will take deleted node's place. |
*/ |
*gpapar = cur; |
cur->par = node->par; |
dir = AVLTREE_LEFT; |
cur->rgt = node->rgt; |
if (node->rgt) node->rgt->par = cur; |
gpa = cur; |
cur->rgt_height = node->rgt_height; |
cur->lft_height = node->lft_height; |
/* |
* cur->lft_height will be decreased in repair cycle. |
*/ |
|
if (repair_rgt_sum == false && node->rgt_sum == 0) { |
/* |
* node hasn't got right son so right sum is 0. |
*/ |
cur->rgt_sum = 0; |
} else { |
cur->rgt_sum = node->rgt_sum + node->key; //pri node->rgt_sum == 0 bude opraveno v cyklu |
if (repair_rgt_sum == true && node->rgt_sum != 0) { |
/* |
* node has got right son so node's key is not the biggest key in any subtree. |
*/ |
repair_rgt_sum = false; |
} else { |
/* |
* node is the biggest key and predecessors might be repaired. |
*/ |
key = node->key; |
} |
} |
} else { |
/* |
* Node has left and right son. Find a node with smallest key in left subtree |
* and change that node with deleted node. |
*/ |
while (cur->rgt != NULL) |
cur = cur->rgt; |
|
*gpapar = cur; |
cur->rgt = node->rgt; |
if (node->rgt) node->rgt->par = cur; |
gpa = cur->par; |
gpa->rgt = cur->lft; |
if (cur->lft) cur->lft->par = gpa; |
cur->lft = node->lft; |
cur->lft->par = cur; |
cur->par = node->par; |
dir = AVLTREE_RIGHT; |
cur->lft_height = node->lft_height; |
cur->rgt_height = node->rgt_height; |
/* |
* gpa->rgt_height and cur->lft_height will be repaired in repair cycle. |
*/ |
|
/* |
* node must have always rgt child otherwise its malfunction of extavltree definition |
* so we can add node->key. If it was to the contrary, we wouldn't know where |
*/ |
cur->rgt_sum = node->rgt_sum + node->key; |
/* |
* The biggest key in at least one subtree was changed - rgt_sum must be repaired. |
*/ |
repair_rgt_sum = true; |
key = cur->key; |
} |
/* |
* Deleted node is root node. Balancing is finished. |
*/ |
if (!gpa) return; |
} |
|
/* |
* Repair cycle which goes from gpa node down to root. |
*/ |
for(;;) { |
if (repair_rgt_sum) { |
/* |
* The biggest key in right subtree was deleted so rgt_sum must be changed. |
*/ |
gpa->rgt_sum -= key; |
} |
|
/* |
* Find tree pointer which points to the currently balanced node. When balanced |
* node is root, root pointer from extavltree structure is taken. |
*/ |
if (!gpa->par) |
gpapar = &(t->root); |
else { |
if (gpa->par->lft == gpa) { |
gpapar = &(gpa->par->lft); |
dir2 = AVLTREE_LEFT; |
repair_rgt_sum = falsi; |
} else { |
gpapar = &(gpa->par->rgt); |
dir2 = AVLTREE_RIGHT; |
} |
} |
|
if (dir == AVLTREE_LEFT) { |
/* |
* Deletition was made in left subtree. |
*/ |
gpa->lft_height--; |
balance = gpa->rgt_height - gpa->lft_height; |
if (balance == 1) { |
/* |
* Stop balancing, tree is balanced. |
*/ |
break; |
} else if (balance == 2) { |
/* |
* Bad balance, heights of left and right subtrees differs more then is allowed. |
*/ |
par = gpa->rgt; |
|
if ((par->rgt_height - par->lft_height) == -1) { |
/* |
* RL rotation |
*/ |
|
cur = par->lft; |
par->lft = cur->rgt; |
cur->rgt = par; |
gpa->rgt = cur->lft; |
cur->lft = gpa; |
|
/* |
* Repair balances. |
*/ |
par->lft_height = cur->rgt_height; |
gpa->rgt_height = cur->lft_height; |
cur->lft_height = extavlreltree_tree_height(gpa) + 1; |
cur->rgt_height = par->rgt_height + 1; |
|
/* |
* Repair paternity. |
*/ |
if (gpa->rgt) gpa->rgt->par = gpa; |
if (par->lft) par->lft->par = par; |
cur->par = gpa->par; |
gpa->par = cur; |
par->par = cur; |
|
/* |
* Repair tree pointer which points to the current node. |
*/ |
*gpapar = cur; |
|
/* |
* Repair rgt_sums after rotation was done. |
*/ |
gpa->rgt_sum -= par->key + par->rgt_sum + cur->key + cur->rgt_sum; |
cur->rgt_sum += par->key + par->rgt_sum; |
|
/* |
* Next balancing at parent node. |
*/ |
gpa = cur->par; |
} else { |
/* |
* RR rotation |
*/ |
gpa->rgt = par->lft; |
gpa->rgt_height = par->lft_height; |
if (par->lft) par->lft->par = gpa; |
par->lft = gpa; |
|
/* |
* Repair paternity. |
*/ |
par->par = gpa->par; |
gpa->par = par; |
|
/* |
* Repair heights and tree pointer which points to the current node. |
*/ |
balance = par->rgt_height - par->lft_height; |
par->lft_height++; |
*gpapar = par; |
|
/* |
* Repair rgt_sums after rotation was done. |
*/ |
gpa->rgt_sum -= par->key + par->rgt_sum; |
|
/* |
* Ends when tree is balanced or do the next step. |
*/ |
if (balance == 0) return; |
gpa = par->par; |
} |
} else { |
/* |
* Current node is balanced - perform balance check of its parent. |
*/ |
gpa = gpa->par; |
} |
} else { |
/* |
* Balance right son. |
*/ |
gpa->rgt_height--; |
balance = gpa->rgt_height - gpa->lft_height; |
if (balance == -1) { |
/* |
* Stop balancing, tree might be balanced or not, whole tree is repaired only during insertion. |
*/ |
break; |
} else if (balance == -2) { |
/* |
* Balance was corrupted - must be repaired. |
*/ |
par = gpa->lft; |
|
if ((par->rgt_height - par->lft_height) >= +1) { |
/* |
* If balance is -2 then par node always exists. |
*/ |
if ((gpa->lft_height - (extavlreltree_tree_height(par))) == 1) { |
/* |
* LR rotation. Height of par subtree is not decreased due to timeout operation. |
*/ |
|
cur = par->rgt; |
par->rgt = cur->lft; |
cur->lft = par; |
gpa->lft = cur->rgt; |
cur->rgt = gpa; |
|
/* |
* Repair balances. |
*/ |
par->rgt_height = cur->lft_height; |
gpa->lft_height = cur->rgt_height; |
cur->rgt_height = gpa->rgt_height + 1; |
cur->lft_height = extavlreltree_tree_height(par) + 1; |
|
/* |
* Repair paternity. |
*/ |
if (gpa->lft) gpa->lft->par = gpa; |
if (par->rgt) par->rgt->par = par; |
cur->par = gpa->par; |
gpa->par = cur; |
par->par = cur; |
|
/* |
* Repair tree pointer which points to the current node. |
*/ |
*gpapar = cur; |
|
/* |
* Repair rgt_sums after rotation was done. |
*/ |
par->rgt_sum -= cur->key + cur->rgt_sum; |
cur->rgt_sum += gpa->key + gpa->rgt_sum; |
|
/* |
* Next balancing at parent node. |
*/ |
gpa = cur->par; |
} else { |
/* |
* Left subtree of cur has been already decreased by timeout operation. |
*/ |
gpa = gpa->par; |
} |
} else { |
/* |
* LL rotation. |
*/ |
|
int prevlftheight = gpa->lft_height; |
gpa->lft = par->rgt; |
gpa->lft_height = par->rgt_height; |
if (par->rgt) par->rgt->par = gpa; |
par->rgt = gpa; |
|
/* |
* Repair paternity. |
*/ |
par->par = gpa->par; |
gpa->par = par; |
|
/* |
* Repair heights and tree pointer which points to the current node. |
*/ |
balance = par->rgt_height - par->lft_height; |
par->rgt_height = extavlreltree_tree_height(gpa) + 1; |
*gpapar = par; |
|
/* |
* Repair rgt_sums after rotation was done. |
*/ |
par->rgt_sum += gpa->key + gpa->rgt_sum; |
|
/* |
* Ends balancing when heights in par nodes are balanced and height |
* of par subtree wasn't decreased due to timeout operation or do |
* the next step. |
*/ |
if (balance == 0 && par->rgt_height == prevlftheight) { |
gpa = par; |
break; |
} |
gpa = par->par; |
} |
} else { |
/* |
* Current node is balanced - perform balance check of its parent. |
*/ |
gpa = gpa->par; |
} |
} |
/* |
* When root is reached then end balancing. |
*/ |
if (!gpa) return; |
|
dir = dir2; |
} |
|
/* |
* End balancing. We must continue in repairing rgt_sum until we |
* reach first left child. |
*/ |
if (repair_rgt_sum) { |
cur = gpa; |
gpa = gpa->par; |
while (gpa) { |
if (gpa->lft == cur) |
break; |
gpa->rgt_sum -= key; |
cur = gpa; |
gpa = gpa->par; |
} |
} |
} |
|
|
/** Delete node from ExtAVLirel tree with the smallest key. |
* |
* Be careful deleted node must have key equal 0 to perform regular timeout. |
* |
* @param t ExtAVLrel tree structure. |
*/ |
bool extavlreltree_delete_min(extavlreltree_t *t) |
{ |
extavlreltree_node_t *expnode; |
extavlreltree_node_t *nextnode; |
|
ASSERT(t); |
|
expnode = t->head.next; |
nextnode = expnode->next; |
|
if (&t->head == expnode) return false; |
|
if (nextnode != &t->head) { |
/* |
* Only first node in the list can be tree node and its key can be 0 (nextnode is the second). |
*/ |
if (nextnode->key == 0) { |
/* |
* Next node of expnode is its chain node. Copy expnode into nextnode. |
*/ |
|
nextnode->lft = expnode->lft; |
nextnode->rgt = expnode->rgt; |
nextnode->par = expnode->par; |
nextnode->lft_height = expnode->lft_height; |
nextnode->rgt_height = expnode->rgt_height; |
if (t->root == expnode) |
t->root = nextnode; |
else |
if (expnode->par->lft == expnode) |
expnode->par->lft = nextnode; |
else |
expnode->par->rgt = nextnode; |
|
if (expnode->lft) expnode->lft->par = nextnode; |
if (expnode->rgt) expnode->rgt->par = nextnode; |
|
nextnode->rgt_sum = expnode->rgt_sum; |
} else if (!expnode->par) { |
/* |
* Delete root node which musn't have left son. |
*/ |
|
t->root = expnode->rgt; |
if (expnode->rgt) expnode->rgt->par = NULL; |
} else if (expnode->rgt) { |
/* |
* Always delete parent of left son. |
*/ |
|
expnode->rgt->par = expnode->par; |
expnode->par->lft = expnode->rgt; |
expnode->par->lft_height = expnode->rgt_height; |
} else { |
/* |
* Deleted node doesn't have right son. |
*/ |
|
expnode->par->lft = NULL; |
expnode->par->lft_height = 0; |
} |
nextnode->key += expnode->key; |
} |
|
/* |
* Delete node from the list. |
*/ |
t->head.next = nextnode; |
nextnode->prev = &t->head; |
|
return true; |
} |