my insert function of redblack tree is working good for input checks listed as comments in main() say for 10 to 20 numbers which has included all types of color changes and rotations..
i am providing input of 1000 numbers to be inserted from input file "in 0" attached.
i am also putting it at the last.
after insertion of 80 elements while loop at line 72 doesn't terminate.
i found out that my tree has become such that
element to be inserted is 2681
left(9714)=6963
left(6963)=6279
left(6279)=6535
left(6535)=9714
can anyone help me to find out why situation mentioned above occurred. help of whatsoever form is highly appreciated.
input format is as follows:
2
insert 0 5 3 5 8 6 0
select 0 2
first line=> number of operations
second line=>
insert =>insert operation
0=> 0th tree
5=>5 insertions
then 5 numbers to be inserted
third line=>
select=>select operation
0=>0th tree
2=>2nd smallest element thus selecting 2nd smallest element in 0th tree.
#include<iostream>
#include<string>
using namespace std;
int j=0;
template <class T>
class redblacktree {
public:
T x;
redblacktree<T> *left, *right, *parent;
int leftsize; // number of nodes in left subtree
int r; // the number of black nodes on any path
// from the current node to a leaf in its subtree
bool color;
redblacktree<T> *root;
redblacktree():root(NULL){}
redblacktree<T>* search(T y)
{
redblacktree<T> *p;
p=root;
while(1)
{
if(y==p->x)
return p;
if(((y>p->x)&&(p->right==NULL))||((y<p->x)&&(p->left==NULL)))
{
cout<<"key not present"<<endl;
break;
}
if((y>p->x)&&(p->right!=NULL))
{p=p->right;
}
else if((y<p->x)&&(p->left!=NULL))
{p=p->left;
}
}
}
void insert(T y)
{
redblacktree<T> *p,*q;
if(root==NULL)
{
q=new redblacktree<T>;
q->x=y;
q->left=q->right=q->parent=NULL;
q->leftsize=0;
q->r=1;
q->color=false;
root=q;
}
else
{
p=root;
q=new redblacktree<T>;
q->x=y;
q->left=q->right=NULL;
q->leftsize=0;
q->r=0;
q->color=true;
redblacktree<T> *u;
while(1) //problem is with this loop remove "//" at lines 74 ,79 & 83 to check.
{
//cout<<p->x<<endl;
if(((y>p->x)&&(p->right==NULL))||((y<p->x)&&(p->left==NULL))||(y==p->x))
break;
if((y>p->x)&&(p->right!=NULL))
{//cout<<"p->right"<<endl;
p=p->right;}
else if((y<p->x)&&(p->left!=NULL))
{//cout<<"p->left"<<endl;
p=p->left;}
}
if(y==p->x)
{
cout<<"key already presnt"<<endl;
return;
}
else if(y>p->x)
{
p->right=q;
q->parent=p;
u=q;
}
else if(y<p->x)
{
p->left=q;
q->parent=p;
u=q;
}
while(1)
{
if(u->parent->right==u)
u=u->parent;
else if(u->parent->left==u)
{
u->parent->leftsize+=1;
u=u->parent;
}
if(u==root)
break;
}
int flag=0;
redblacktree<T> *pu,*gu;
while((q->parent!=NULL)&&(q->parent->parent!=NULL))
{
if((q->parent->color)&&(q->color))
{
pu=q->parent;
gu=q->parent->parent;
if(q->parent->parent->left==q->parent)
{
if((q->parent->parent->right==NULL)||(q->parent->parent->right->color==false))
{
if(q->parent->left==q)
{
pu->color=false;
gu->color=true;
gu->leftsize=gu->leftsize-1-pu->leftsize;
if(gu==root)
flag=1;
if(flag==0)
{
if(gu->parent->left==gu)
gu->parent->left=pu;
else
gu->parent->right=pu;
}
pu->parent=gu->parent;
gu->parent=pu;
gu->left=pu->right;
if(pu->right!=NULL)
pu->right->parent=gu;
pu->right=gu;
if(flag==1)
root=pu;
break;
}
else
{
q->color=false;
gu->color=true;
gu->leftsize=gu->leftsize-2-pu->leftsize-q->leftsize;
q->leftsize=pu->leftsize+1+q->leftsize;
if(gu==root)
flag=1;
if(flag==0)
{
if(gu->parent->left==gu)
gu->parent->left=q;
else
gu->parent->right=q;
}
q->parent=gu->parent;
gu->parent=q;
if(q->left!=NULL)
q->left->parent=pu;
if(q->right!=NULL)
q->right->parent=gu;
gu->left=q->right;
pu->right=q->left;
q->left=pu;
q->right=gu;
pu->parent=q;
if(flag==1)
root=q;
break;
}
}
else if((q->parent->parent->right->color==true)&&(q->parent->parent->left==q->parent))
{
q->parent->color=false;
q->parent->parent->right->color=false;
if(q->parent->parent!=root)
{
q->parent->parent->color=true;
cout<<q->parent->parent->color<<endl;
q=q->parent->parent;
}
else
break;
}
}
else if(q->parent->parent->right==q->parent)
{
if((q->parent->parent->left==NULL)||(q->parent->parent->left->color==false))
{
if(q->parent->right==q)
{
pu->color=false;
gu->color=true;
pu->leftsize=gu->leftsize+1+pu->leftsize;
if(gu==root)
flag=1;
if(flag==0)
{
if(gu->parent->left==gu)
gu->parent->left=pu;
else
gu->parent->right=pu;
}
pu->parent=gu->parent;
gu->parent=pu;
gu->right=pu->left;
if(pu->left!=NULL)
pu->left->parent=gu;
pu->left=gu;
if(flag==1)
root=pu;
break;
}
else
{
q->color=false;
gu->color=true;
pu->leftsize=pu->leftsize-1-q->leftsize;
q->leftsize=gu->leftsize+1+q->leftsize;
if(gu==root)
flag=1;
if(flag==0)
{
if(gu->parent->left==gu)
gu->parent->left=q;
else
gu->parent->left=q;
}
q->parent=gu->parent;
gu->parent=q;
if(q->left!=NULL)
q->left->parent=gu;
if(q->right!=NULL)
q->right->parent=pu;
gu->right=q->left;
pu->left=q->right;
q->right=pu;
q->left=gu;
pu->parent=q;
if(flag==1)
root=q;
break;
}
}
else if((q->parent->parent->left->color==true)&&(q->parent->parent->right==q->parent))
{
q->parent->color=false;
q->parent->parent->left->color=false;
if(q->parent->parent!=root)
{
q->parent->parent->color=true;
q=q->parent->parent;
}
else
break;
}
}
}
else
break;
}
}
}
T kthsmallest(int k)
{
redblacktree<T> *p;
p=root;
while(1)
{
if(k==p->leftsize+1)
return p->x;
else if(k>p->leftsize+1)
{
k=k-p->leftsize-1;
p=p->right;
}
else if(k<p->leftsize+1)
p=p->left;
}
}
void traversal(redblacktree<T> *root)
{
if(root==NULL)
return;
else
{
traversal(root->left);
cout<<root->x<<" "<<root->color<<" "<<root->leftsize<<endl;
traversal(root->right);
}
}
};
int main()
{
//redblacktree<int> rb;
/* rb.insert(30);
rb.insert(40);
rb.insert(50);
rb.insert(-10);
rb.insert(0);
rb.insert(90); //input check 1
rb.insert(45);
rb.insert(36);
rb.insert(9);
rb.insert(345);
*/
/*
rb.insert(50);
rb.insert(40);
rb.insert(30); //input check 2
rb.insert(35);
rb.insert(10);
*/
/*
rb.insert(50);
rb.insert(10);
rb.insert(80);
rb.insert(90);
rb.insert(70); //input check 2
rb.insert(60);
rb.insert(65);
rb.insert(62);
rb.insert(62);
*/
/*
rb.insert(10);
rb.insert(85);
rb.insert(15);
rb.insert(70);
rb.insert(20);
rb.insert(60);
rb.insert(30);
rb.insert(50); //input check 3
rb.insert(65);
rb.insert(80);
rb.insert(90);
rb.insert(40);
rb.insert(5);
rb.insert(55);
*/
//rb.traversal(rb.root); //perform inorder traversal to check correctness of tree
int no_of_trees,tree_no,no_of_insertions,number,k,result;
int j=0;
string s;
cin>>no_of_trees;
redblacktree<int> rb[no_of_trees];
for(int i=0;i<no_of_trees;i++)
{
s.clear();
cin.ignore(2,'\n');
getline(cin,s,' ');
if(s.compare("insert")==0)
{
cin>>tree_no;
cin>>no_of_insertions;
for(int i=0;i<no_of_insertions;i++)
{
cin>>number;
cout<<++j<<"th element="<<number<<endl;
rb[tree_no].insert(number);
cout<<j<<"th insertion completed"<<"j="<<j<<endl;
}
}input file "in 0"
2
insert 0 1000
16656 11509 6963 15077 16021 2086 6535 200 4972 10296 9714 7235 11850 6279 11746 5760 17371 17399 19920 6539 16869 13383 7283 6294 6991 3740 15333 14482 6868 3049 2608 3524 18279 13292 2321 14300 15379 8856 18221 350 2873 7934 7585 14723 17934 3052 4203 15304 450 7843 5564 17319 1225 12847 7333 11937 307 6386 6418 7176 9435 12748 14421 7714 6039 16742 2013 1417 9319 233 1767 15913 11889 9353 10635 9822 16126 14839 8847 16576 2681 14411 17615 7628 10978 8668 19565 11285 15055 5983 18461 4489 18731 16602 12203 4769 17065 17937 9908 6383 1891 11675 2295 13780 4748 16651 7322 873 15210 16169 1169 1612 10579 2504 9240 5277 11173 12525 16563 6227 18508 18744 14437 958 15346 10361 9449 12410 8297 19357 2513 10188 14752 8529 7688 19501 8900 15011 4094 4110 11179 5264 9443 5479 7768 18683 10756 18941 11207 11039 8888 13436 13504 3325 14394 8849 13686 7563 4979 5703 6919 11213 19613 1671 3462 7300 4892 12362 2310 8986 192 13490 14250 9635 2689 5739 12038 17166 4679 6966 8205 17289 401 1708 613 18516 14278 18020 6079 2977 3722 16719 14190 3334 18390 1372 3281 13734 12945 12268 17648 10155 10238 7282 16565 15977 3041 13731 4377 10007 5656 1665 10408 11085 2278 12644 5362 4018 18723 12060 7740 19163 6249 14796 17552 11342 5430 4554 5075 2095 542 2722 15972 10780 13726 16257 6757 16767 9987 14855 6773 15643 16520 901 10448 2518 13545 15810 6536 15989 7869 17997 15151 17839 12792 16423 9180 1942 976 17977 4038 1518 4419 3730 16020 1865 19987 6497 18632 13695 1351 9125 9337 17871 13747 19786 4109 11013 19316 14366 10722 10906 9593 12465 5154 6015 5366 7096 10713 3342 15952 11482 18585 15692 13348 2292 2188 15700 15987 3539 8546 9044 5130 12550 12960 17026 11866 7325 7747 6492 19688 1060 18957 4841 10797 4322 15658 1509 11385 14234 1181 2867 12818 16874 16215 15110 2782 15635 11096 6322 4180 140 15173 10194 12690 8133 7219 8276 15458 18688 14768 15145 19748 17446 3706 10544 5488 3085 15774 16956 3461 13857 17550 3396 8967 331 19031 3783 10374 3211 7644 9268 17126 4055 17401 4344 16052 16579 3031 14541 11724 6500 11986 19151 17044 17474 5956 16539 18068 3274 17215 1528 17132 14764 4924 9819 18816 7676 17323 12911 14608 8688 2178 11733 16464 19579 16077 12515 19878 2829 7055 11601 9329 2761 14473 10093 235 4149 6631 2023 7424 3845 3552 2329 12197 1815 4866 19873 2858 17777 14480 11546 19955 6212 8009 3253 6010 4245 3130 12560 11300 18453 5609 17783 16646 15702 18018 794 6054 3761 11939 13620 7313 3935 19671 3231 5750 4536 3103 12330 6033 1304 3875 9708 7516 15606 16682 17247 3571 19812 9806 18592 1984 15415 16374 2350 14838 18112 6866 891 1873 18805 18232 12907 2740 17902 16138 12211 6158 19242 4540 12191 4266 12137 1898 11782 11463 18580 12750 15034 2112 2555 13625 7817 1691 9999 10168 16529 11831 17034 1140 13704 19559 3092 6611 2298 994 2748 18231 10873 5710 2770 6785 9976 18628 12404 10090 10984 18229 5123 16817 4504 2469 8354 6195 16189 2242 6444 8019 19276 7584 5444 14398 12055 8574 15392 18524 6804 9985 7955 13296 16770 17931 11923 9174 7130 3878 9079 10857 4415 17305 17047 12769 7220 13235 15012 13665 4975 18008 4969 10419 562 19367 6194 9137 18479 4717 19662 12185 16393 12957 8954 14324 4880 1848 5174 10614 5726 17975 5191 10141 15279 2238 6219 19194 1642 19884 7889 3370 2028 7654 11661 8222 511 10140 16661 172 2324 13053 16851 14999 11097 5451 16848 19993 16065 17967 4976 156 16966 7214 6787 3184 10129 12150 6789 15520 15363 46 3173 7023 11989 7405 883 8649 7578 6928 1702 4428 1927 13600 2495 16512 13385 8789 18199 18361 8945 15164 9296 15732 18349 19425 11602 8858 1162 7122 7941 1208 14016 18685 13198 1421 19569 5567 12720 10217 10990 868 15865 7510 14468 18360 4021 11573 7149 5941 9933 19815 1104 19229 19268 18653 10869 12031 19816 1711 19972 4744 19449 18657 1662 4590 1945 7230 17310 12162 18220 8027 9450 86 10107 17193 11659 17256 3133 1591 791 4237 4541 58 11132 6914 10927 6883 10450 12639 6855 15195 15808 9232 577 397 14898 7807 1427 9748 18807 2918 7132 8914 110 18791 9890 6964 4102 10681 11202 12364 14460 19279 5387 12937 9728 1746 3512 8643 17554 16465 9221 11362 748 3098 2142 14217 10144 4669 17136 17276 17304 966 19787 10915 7931 7609 5316 2853 19974 19777 8907 2972 8884 1843 16421 14351 9077 5064 15625 5541 18006 17296 16904 2474 4114 2766 412 14258 7435 17548 15254 4739 2234 15040 19375 10165 6369 4690 13018 6342 4466 5645 9314 17071 11210 5735 11421 286 14520 7045 5827 16246 8061 2730 18720 12175 9217 19132 6432 16653 399 1685 5112 6355 445 4486 6815 9176 13259 16878 17364 18904 6192 18155 13834 15648 9576 14120 13888 341 19948 10133 8403 6398 12573 4298 15616 15426 10731 15825 16137 1100 2179 303 9307 2420 10839 2203 19400 7716 3287 18303 17629 1442 15858 13276 11018 9977 10884 15080 13645 1016 3482 3764 13590 11502 3100 12736 5953 19089 12281 5810 3909 18182 6113 16937 601 16952 19140 0 8389 6148 6017 7590 17881 3014 2328 11579 13898 17408 5223 18636 4611 12708 15946 16113 8681 2065 18617 961 7875 6246 19143 17710 3182 19744 18382 6043 3464 6770 15912 9209 16509 3501 7089 19523 5829 2388 17141 6957 7612 15776 15289 4040 11721 11401 19849 4122 17187 2185 5084 8783 8432 7947 10213 15335 11412 8594 5098 14876 19086 1009 4084 15594 8231 14895 15116 17781 17283 12256 4738 8615 11753 3747 16377 7194 18870 16225 11317 16056 2130 121 8559 10562 8068 18772 9618 19480 11087 14716 14356 10172 19447 2160 5765 7677 775 4601 9179 1779 13917 14115 17664 10491 19525 16533 10436 14562 16310 12567 14683 8589 3128 2750 11082 16467 2230 2168 14904 306 16061
select 0 250