trunk/src/lib/util/simple_set.h
| r242452 | r242453 | |
|---|
| 103 | 103 | // See if it's a leaf |
| 104 | 104 | if (currNode->isLeaf()) |
| 105 | 105 | { |
| 106 | // Get the parent object |
| 107 | tree_node* parentNode = currNode->parent; |
| 108 | |
| 106 | 109 | // If we're a leaf and we have no parent, then the tree will be emptied |
| 107 | 110 | if (!currNode->parent) |
| 108 | 111 | { |
| r242452 | r242453 | |
|---|
| 112 | 115 | // If it's a leaf node, simply remove it |
| 113 | 116 | removeNode(currNode); |
| 114 | 117 | global_free(currNode); |
| 118 | |
| 119 | // Update the balance of the parent of |
| 120 | // currentNode after having disconnected |
| 121 | // it |
| 122 | if (parentNode) |
| 123 | parentNode->calcHeights(); |
| 115 | 124 | } |
| 116 | 125 | else |
| 117 | 126 | { |
| r242452 | r242453 | |
|---|
| 129 | 138 | replaceNode = findMax(currNode->left); |
| 130 | 139 | } |
| 131 | 140 | |
| 141 | tree_node* parentReplaceNode = replaceNode->parent; |
| 142 | |
| 132 | 143 | // Disconnect the replacement node's branch |
| 133 | 144 | removeNode(replaceNode); |
| 134 | 145 | |
| 146 | // Update the balance of the parent of |
| 147 | // replaceNode after having disconnected |
| 148 | // it |
| 149 | if (parentReplaceNode) |
| 150 | parentReplaceNode->calcHeights(); |
| 151 | |
| 135 | 152 | // Disconnect the current node |
| 136 | 153 | removeNode(currNode); |
| 137 | 154 | |
| r242452 | r242453 | |
|---|
| 286 | 303 | if (retVal) |
| 287 | 304 | { |
| 288 | 305 | t->left->setParent(t); |
| 306 | t->calcHeights(); |
| 307 | |
| 289 | 308 | if(t->balanceFactor() < -1) |
| 290 | 309 | { |
| 291 | 310 | // See if it went left of the left |
| r242452 | r242453 | |
|---|
| 311 | 330 | if (retVal) |
| 312 | 331 | { |
| 313 | 332 | t->right->setParent(t); |
| 333 | t->calcHeights(); |
| 314 | 334 | |
| 315 | 335 | if (t->balanceFactor() > 1) |
| 316 | 336 | { |
| r242452 | r242453 | |
|---|
| 389 | 409 | if (retVal && !t->left->parent) |
| 390 | 410 | { |
| 391 | 411 | t->left->setParent(t); |
| 412 | t->calcHeights(); |
| 392 | 413 | } |
| 393 | 414 | } |
| 394 | 415 | else if (t->element < b->element) |
| r242452 | r242453 | |
|---|
| 399 | 420 | if (retVal && !t->right->parent) |
| 400 | 421 | { |
| 401 | 422 | t->right->setParent(t); |
| 423 | t->calcHeights(); |
| 402 | 424 | } |
| 403 | 425 | |
| 404 | 426 | return retVal; |
| r242452 | r242453 | |
|---|
| 502 | 524 | |
| 503 | 525 | k2 = k1; |
| 504 | 526 | k2->setParent(k2Parent); |
| 527 | |
| 528 | k2->right->calcHeights(); |
| 529 | |
| 505 | 530 | } |
| 506 | 531 | |
| 507 | 532 | |
| r242452 | r242453 | |
|---|
| 520 | 545 | |
| 521 | 546 | k1 = k2; |
| 522 | 547 | k1->setParent(k1Parent); |
| 548 | |
| 549 | k1->left->calcHeights(); |
| 550 | |
| 523 | 551 | } |
| 524 | 552 | |
| 525 | 553 | |
| r242452 | r242453 | |
|---|
| 722 | 750 | { |
| 723 | 751 | // Set our new parent |
| 724 | 752 | parent = p; |
| 725 | | |
| 726 | | // If we have a valid parent, set its height |
| 727 | | if (parent) |
| 728 | | { |
| 729 | | // Set the parent's height to include this tree. If the parent |
| 730 | | // already has a tree that is taller than the one we're attaching |
| 731 | | // then the parent's height remains unchanged |
| 732 | | int rightHeight = (parent->right ? parent->right->m_height : 0); |
| 733 | | int leftHeight = (parent->left ? parent->left->m_height : 0); |
| 734 | | |
| 735 | | // The height of the tallest branch + 1 |
| 736 | | parent->m_height = maxInt(rightHeight, leftHeight) + 1; |
| 737 | | |
| 738 | | // Also set the balance factor |
| 739 | | parent->m_balanceFactor = rightHeight - leftHeight; |
| 740 | | } |
| 741 | 753 | } |
| 742 | 754 | |
| 743 | 755 | |
| r242452 | r242453 | |
|---|
| 746 | 758 | { |
| 747 | 759 | // Set our new left node |
| 748 | 760 | left = l; |
| 749 | | |
| 750 | | // Set the height and balance factor |
| 751 | | int rightHeight = (right ? right->m_height : 0); |
| 752 | | int leftHeight = (left ? left->m_height : 0); |
| 753 | | |
| 754 | | m_height = maxInt(rightHeight, leftHeight) + 1; |
| 755 | | m_balanceFactor = (right ? right->m_height : 0) - (left ? left->m_height : 0); |
| 756 | 761 | } |
| 757 | 762 | |
| 758 | 763 | |
| r242452 | r242453 | |
|---|
| 761 | 766 | { |
| 762 | 767 | // Set our new right node |
| 763 | 768 | right = r; |
| 764 | | |
| 765 | | // Set the height and balance factor |
| 766 | | int rightHeight = (right ? right->m_height : 0); |
| 767 | | int leftHeight = (left ? left->m_height : 0); |
| 768 | | |
| 769 | | m_height = maxInt(rightHeight, leftHeight) + 1; |
| 770 | | m_balanceFactor = (right ? right->m_height : 0) - (left ? left->m_height : 0); |
| 771 | 769 | } |
| 772 | 770 | |
| 773 | 771 | |
| r242452 | r242453 | |
|---|
| 799 | 797 | // Calculates all of the heights for this node and its ancestors -- O(log n). |
| 800 | 798 | void calcHeights() |
| 801 | 799 | { |
| 802 | | // Calculate our own height -- O(1) |
| 803 | | m_height = maxInt(left ? left->m_height : 0, right ? right->m_height : 0) + 1; |
| 800 | int rightHeight = (right ? right->m_height : 0); |
| 801 | int leftHeight = (left ? left->m_height : 0); |
| 804 | 802 | |
| 805 | | // And our parent's height (and recurse) -- O(log n) |
| 803 | // Calculate our own height and balance factor -- O(1) |
| 804 | m_height = maxInt(rightHeight, leftHeight) + 1; |
| 805 | m_balanceFactor = (rightHeight - leftHeight); |
| 806 | |
| 807 | // And our parent's height and balance factor (and recurse) -- O(log n) |
| 806 | 808 | if (parent) |
| 807 | 809 | { |
| 808 | 810 | parent->calcHeights(); |