217,7 → 217,8 |
par->par = top->par; |
top->par = par; |
par->rgt = top; |
par->balance = top->balance = 0; |
par->balance = 0; |
top->balance = 0; |
*dpc = par; |
} else { |
/* |
242,7 → 243,8 |
par->balance = 0; |
top->balance = 1; |
} else if (gpa->balance == 0) { |
par->balance = top->balance = 0; |
par->balance = 0; |
top->balance = 0; |
} else { |
par->balance = -1; |
top->balance = 0; |
262,7 → 264,8 |
par->par = top->par; |
top->par = par; |
par->lft = top; |
par->balance = top->balance = 0; |
par->balance = 0; |
top->balance = 0; |
*dpc = par; |
} else { |
/* |
287,7 → 290,8 |
par->balance = 0; |
top->balance = -1; |
} else if (gpa->balance == 0) { |
par->balance = top->balance = 0; |
par->balance = 0; |
top->balance = 0; |
} else { |
par->balance = 1; |
top->balance = 0; |
304,6 → 308,77 |
|
} |
|
/** 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 |
317,12 → 392,12 |
avltree_node_t *cur; |
avltree_node_t *par; |
avltree_node_t *gpa; |
uint8_t dir; |
int dir; |
|
ASSERT(t); |
ASSERT(node); |
|
if (node->lft == NULL) { |
if (node->lft == NULL) { |
if (node->rgt) { |
/* |
* Replace the node with its only right son. |
354,9 → 429,9 |
} |
} else { |
/* |
* 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. |
* 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) |
; |
402,15 → 477,7 |
* Repair the parent node's pointer which pointed previously to the |
* deleted node. |
*/ |
if (node->par == NULL) { |
t->root = cur; |
} else { |
if (node->par->lft == node) { |
node->par->lft = cur; |
} else { |
node->par->rgt = cur; |
} |
} |
(void) repair(t, node, node, cur, NULL, false); |
|
/* |
* Repair cycle which repairs balances of nodes on the way from from the |
450,26 → 517,7 |
* children, depending on the balance |
* factor of the 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; |
REBALANCE_RL(); |
|
/* |
* Repair paternity. |
478,25 → 526,9 |
gpa->par = cur; |
par->par = cur; |
|
/* |
* 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; |
if (!repair(t, cur, gpa, cur, &dir, |
false)) |
break; |
} else { |
if (cur->par->lft == gpa) { |
cur->par->lft = cur; |
dir = LEFT; |
} else { |
cur->par->rgt = cur; |
dir = RIGHT; |
} |
} |
gpa = cur->par; |
} else { |
/* |
525,49 → 557,15 |
par->balance = -1; |
gpa->balance = 1; |
|
/* |
* 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; |
} |
} |
(void) repair(t, par, gpa, par, |
NULL, false); |
break; |
} else { |
par->balance = gpa->balance = 0; |
/* |
* 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; |
par->balance = 0; |
gpa->balance = 0; |
if (!repair(t, par, gpa, par, |
&dir, false)) |
break; |
} else { |
if (par->par->lft == |
gpa) { |
par->par->lft = |
par; |
dir = LEFT; |
} else { |
par->par->rgt = |
par; |
dir = RIGHT; |
} |
} |
} |
gpa = par->par; |
} |
578,14 → 576,8 |
* is finished else continue with the next |
* iteration (parent node). |
*/ |
if (!gpa->par) |
if (!repair(t, gpa, gpa, NULL, &dir, true)) |
break; |
|
if (gpa->par->lft == gpa) { |
dir = LEFT; |
} else { |
dir = RIGHT; |
} |
gpa = gpa->par; |
} |
} else { |
621,26 → 613,7 |
* 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; |
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; |
REBALANCE_LR(); |
|
/* |
* Repair paternity. |
649,31 → 622,15 |
gpa->par = cur; |
par->par = cur; |
|
/* |
* 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 { |
if (cur->par->lft == gpa) { |
cur->par->lft = cur; |
dir = LEFT; |
} else { |
cur->par->rgt = cur; |
dir = RIGHT; |
} |
} |
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; |
695,50 → 652,16 |
par->balance = 1; |
gpa->balance = -1; |
|
/* |
* 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; |
} |
} |
(void) repair(t, par, gpa, par, |
NULL, false); |
break; |
} else { |
par->balance = gpa->balance = 0; |
par->balance = 0; |
gpa->balance = 0; |
|
/* |
* 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; |
if (!repair(t, par, gpa, par, |
&dir, false)) |
break; |
} else { |
if (par->par->lft == |
gpa) { |
par->par->lft = |
par; |
dir = LEFT; |
} else { |
par->par->rgt = |
par; |
dir = RIGHT; |
} |
} |
} |
gpa = par->par; |
} |
749,14 → 672,8 |
* is finished. Otherwise continue with the next |
* iteration (parent node). |
*/ |
if (!gpa->par) |
if (!repair(t, gpa, gpa, NULL, &dir, true)) |
break; |
|
if (gpa->par->lft == gpa) { |
dir = LEFT; |
} else { |
dir = RIGHT; |
} |
gpa = gpa->par; |
} |
} |
792,3 → 709,4 |
|
/** @} |
*/ |
|