Changeset 196 for trunk/src/helpers/tree.c
- Timestamp:
- Aug 9, 2002, 12:35:28 AM (23 years ago)
- File:
-
- 1 edited
-
trunk/src/helpers/tree.c (modified) (17 diffs)
Legend:
- Unmodified
- Added
- Removed
-
trunk/src/helpers/tree.c
r116 r196 312 312 if (ul1 < ul2) 313 313 return -1; 314 314 315 if (ul1 > ul2) 315 316 return +1; 316 return (0); 317 318 return 0; 317 319 } 318 320 … … 336 338 { 337 339 int i = strcmp(p1, p2); 338 if (i < 0) return (-1); 339 if (i > 0) return (+1); 340 if (i < 0) 341 return -1; 342 if (i > 0) 343 return +1; 340 344 } 341 345 else if (p1) 342 346 // but p2 is NULL: p1 greater than p2 then 343 return (+1);347 return +1; 344 348 else if (p2) 345 349 // but p1 is NULL: p1 less than p2 then 346 return (-1);350 return -1; 347 351 348 352 // return 0 if strcmp returned 0 above or both strings are NULL 349 return (0);353 return 0; 350 354 } 351 355 … … 358 362 TREE *x) 359 363 { 360 /************************** 361 * rotate node x to left * 362 **************************/ 364 // rotate node x to left 363 365 364 366 TREE *y = x->right; … … 372 374 if (y != LEAF) 373 375 y->parent = x->parent; 376 374 377 if (x->parent) 375 378 { … … 396 399 TREE *x) 397 400 { 398 399 /**************************** 400 * rotate node x to right * 401 ****************************/ 401 // rotate node x to right 402 402 403 403 TREE *y = x->left; … … 411 411 if (y != LEAF) 412 412 y->parent = x->parent; 413 413 414 if (x->parent) 414 415 { … … 435 436 TREE *x) 436 437 { 437 /*************************************438 * maintain Red-Black tree balance *439 * after inserting node x *440 *************************************/441 442 438 // check Red-Black properties 443 439 while ( x != *root … … 503 499 } 504 500 } 501 505 502 (*root)->color = BLACK; 506 503 } … … 546 543 { 547 544 int iResult; 548 if ( 0 == (iResult = pfnCompare(key, current->ulKey))) // if (compEQ(key, current->key))545 if (!(iResult = pfnCompare(key, current->ulKey))) 549 546 return STATUS_DUPLICATE_KEY; 550 547 551 548 parent = current; 552 current = (iResult < 0) // compLT(key, current->key)549 current = (iResult < 0) 553 550 ? current->left 554 551 : current->right; … … 556 553 557 554 // set up new node 558 /* if ((x = malloc (sizeof(*x))) == 0)559 return STATUS_MEM_EXHAUSTED; */560 555 x->parent = parent; 561 556 x->left = LEAF; 562 557 x->right = LEAF; 563 558 x->color = RED; 564 // x->key = key;565 // x->rec = *rec;566 559 567 560 // insert node in tree … … 578 571 insertFixup(root, 579 572 x); 580 // lastFind = NULL;581 573 582 574 if (plCount) … … 667 659 } 668 660 } 661 669 662 tree->color = BLACK; 670 671 /*************************************672 * maintain Red-Black tree balance *673 * after deleting node x *674 *************************************/675 676 /* while ( x != *root677 && x->color == BLACK678 )679 {680 if (x == x->parent->left)681 {682 TREE *w = x->parent->right;683 if (w->color == RED)684 {685 w->color = BLACK;686 x->parent->color = RED;687 rotateLeft(root,688 x->parent);689 w = x->parent->right;690 }691 if ( w->left->color == BLACK692 && w->right->color == BLACK693 )694 {695 w->color = RED;696 x = x->parent;697 }698 else699 {700 if (w->right->color == BLACK)701 {702 w->left->color = BLACK;703 w->color = RED;704 rotateRight(root,705 w);706 w = x->parent->right;707 }708 w->color = x->parent->color;709 x->parent->color = BLACK;710 w->right->color = BLACK;711 rotateLeft(root,712 x->parent);713 x = *root;714 }715 }716 else717 {718 TREE *w = x->parent->left;719 if (w->color == RED)720 {721 w->color = BLACK;722 x->parent->color = RED;723 rotateRight(root,724 x->parent);725 w = x->parent->left;726 }727 if ( w->right->color == BLACK728 && w->left->color == BLACK729 )730 {731 w->color = RED;732 x = x->parent;733 }734 else735 {736 if (w->left->color == BLACK)737 {738 w->right->color = BLACK;739 w->color = RED;740 rotateLeft(root,741 w);742 w = x->parent->left;743 }744 w->color = x->parent->color;745 x->parent->color = BLACK;746 w->left->color = BLACK;747 rotateRight(root,748 x->parent);749 x = *root;750 }751 }752 }753 x->color = BLACK; */754 663 } 755 664 … … 803 712 if (y != LEAF) 804 713 y->parent = d->parent; 714 805 715 if (d->parent) 806 716 { … … 863 773 FNTREE_COMPARE *pfnCompare) // in: comparison func 864 774 { 865 /*******************************866 * find node containing data *867 *******************************/868 869 775 TREE *current = root; 870 776 while (current != LEAF) 871 777 { 872 778 int iResult; 873 if (0 == (iResult = pfnCompare(key, current->ulKey))) 874 return (current); 875 else 876 { 877 current = (iResult < 0) // compLT (key, current->key) 878 ? current->left 879 : current->right; 880 } 779 if (!(iResult = pfnCompare(key, current->ulKey))) 780 return current; 781 782 current = (iResult < 0) 783 ? current->left 784 : current->right; 881 785 } 882 786 … … 957 861 p = r; 958 862 if (p->right != LEAF) 959 return treeFirst (p->right); 960 else 961 { 962 p = r; 963 child = LEAF; 964 while ( (p->parent) 965 && (p->right == child) 966 ) 967 { 968 child = p; 969 p = p->parent; 970 } 971 if (p->right != child) 972 return p; 973 else 974 return NULL; 975 } 863 return treeFirst(p->right); 864 865 p = r; 866 child = LEAF; 867 while ( (p->parent) 868 && (p->right == child) 869 ) 870 { 871 child = p; 872 p = p->parent; 873 } 874 875 if (p->right != child) 876 return p; 877 878 return NULL; 976 879 } 977 880 … … 987 890 988 891 if ( (!r) 989 || (r == LEAF)) 892 || (r == LEAF) 893 ) 990 894 return NULL; 991 895 … … 993 897 if (p->left != LEAF) 994 898 return treeLast (p->left); 995 else 996 {997 p = r;998 child = LEAF;999 while ((p->parent)1000 && (p->left == child))1001 1002 1003 1004 1005 if (p->left != child) 1006 return p;1007 else1008 return NULL; 1009 }899 900 p = r; 901 child = LEAF; 902 while ( (p->parent) 903 && (p->left == child) 904 ) 905 { 906 child = p; 907 p = p->parent; 908 } 909 910 if (p->left != child) 911 return p; 912 913 return NULL; 1010 914 } 1011 915
Note:
See TracChangeset
for help on using the changeset viewer.
