#include<iostream.h>
#include<conio.h>
class add
{
int a,b,c;
public:
void input()
{
cout<<"\n *** Enter the value of a & b *** ";
cin>>a>>b;
}
void output()
{
c=a+b;
cout<<" The value of "<<a<<"+ "<<b<<" = "<<c;
}
};
void main()
{
add a1;
clrscr();
a1.input();
a1.output();
getch();
}
#include
#include
typedef int ElementType;
struct AvlNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;
AvlTree MakeEmpty( AvlTree T );
AvlTree Insert( ElementType X, AvlTree T );
void display(AvlTree T);
#include
struct AvlNode
{
ElementType Element;
AvlTree Left;
AvlTree Right;
int Height;
};
void display(AvlTree T)
{
if(T->Left!=NULL)
display(T->Left);
if(T->Right!=NULL)
display(T->Right);
printf("%d",T->Element);
}
AvlTree MakeEmpty( AvlTree T )
{
if( T != NULL )
{
MakeEmpty( T->Left );
MakeEmpty( T->Right );
free( T );
}
return NULL;
}
static int Height( Position P )
{
if( P 2 )
if( X > T->Right->Element )
T = SingleRotateWithRight( T );
else
T = DoubleRotateWithRight( T );
}
/* Else X is in the tree already; we'll do nothing */
T->Height = Max( Height( T->Left ), Height( T->Right ) ) + 1;
return T;
}
main()
{
AvlTree T;
Position P;
int i=0,a,ch;
T = MakeEmpty( NULL );
while(1)
{
printf("\nenter your choice 1.insert 2.display 3.exit");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("enter the element");
scanf("%d",&a);
T = Insert( a, T );
break;
case 2:
printf("display by postorder traversal\n");
display(T);
break;
case 3:
exit(0);
break;
} }
}
#include
#include
#include
struct node
{
enum colour{ BLACK, RED };
int m_data;
colour m_colour;
node* m_left;
node* m_right;
node* m_parent;
node() : m_data( NULL ), m_colour( BLACK ), m_left( NULL ), m_right( NULL ), m_parent( NULL ) {}
node( const int data ) : m_data( data ), m_colour( BLACK ), m_left( NULL ), m_right( NULL ), m_parent( NULL ) {}
~node() {}
node* successor( node* nil )
{
node* n = this;
if( m_right != nil )
{
n = m_right;
while( n->m_left != nil )
n = n->m_left;
return( n );
}
node* p = m_parent;
while( n == p->m_right )
{
n = p;
p = n->m_parent;
}
return( p );
}
};
struct rbtree
{
node* m_nil; // sentinel (all leaf nodes point here)
node* m_root;
rbtree(): m_nil( new node() ), m_root( m_nil ) {}
~rbtree()
{
destroy_node( m_root );
delete( m_nil );
}
void destroy_node( node *n )
{
if( n != m_nil )
{
destroy_node( n->m_left );
destroy_node( n->m_right );
delete( n );
}
}
void rotate_left( node *n )
{
node* p;
p = n->m_right;
n->m_right = p->m_left;
p->m_left->m_parent = n;
p->m_parent = n->m_parent;
if( n->m_parent == m_nil )
m_root = p;
else if( n == n->m_parent->m_left )
n->m_parent->m_left = p;
else
n->m_parent->m_right = p;
p->m_left = n;
n->m_parent = p;
}
void rotate_right( node* n )
{
node *p;
p = n->m_left;
n->m_left = p->m_right;
p->m_right->m_parent = n;
p->m_parent = n->m_parent;
if( n->m_parent == m_nil )
m_root = p;
else if( n == n->m_parent->m_right )
n->m_parent->m_right = p;
else
n->m_parent->m_left = p;
p->m_right = n;
n->m_parent = p;
}
int insert_key( int data )
{
node* n = m_root;
node* p = m_nil;
while( n != m_nil )
{
p = n;
if( data < n->m_data )
n = n->m_left;
else if( n->m_data < data )
n = n->m_right;
else
return( 0 ); // duplicates not permitted!
}
n = new node( data );
n->m_parent = p;
n->m_colour = node::RED;
n->m_left = n->m_right = m_nil;
if( p == m_nil )
m_root = n;
else if( data < p->m_data )
p->m_left = n;
else
p->m_right = n;
fix_up( n );
return( 1 );
}
void fix_up( node *n )
{
// u = uncle
node* u;
while( n->m_parent->m_colour == node::RED )
{
// g = grandparent
node* g = n->m_parent->m_parent;
if( n->m_parent == g->m_left )
{
u = g->m_right;
if( u->m_colour == node::RED )
{
n->m_parent->m_colour = node::BLACK;
u->m_colour = node::BLACK;
g->m_colour = node::RED;
n = g;
}
else
{
if( n == n->m_parent->m_right )
{
n = n->m_parent;
rotate_left( n );
g = n->m_parent->m_parent;
}
n->m_parent->m_colour = node::BLACK;
g->m_colour = node::RED;
rotate_right( g );
}
}
else
{
u = g->m_left;
if( u->m_colour == node::RED )
{
n->m_parent->m_colour = node::BLACK;
u->m_colour = node::BLACK;
g->m_colour = node::RED;
n = g;
}
else
{
if( n == n->m_parent->m_left )
{
n = n->m_parent;
rotate_right( n );
g = n->m_parent->m_parent;
}
n->m_parent->m_colour = node::BLACK;
g->m_colour = node::RED;
rotate_left( g );
}
}
}
m_root->m_colour = node::BLACK;
}
void delete_key( node *n )
{
node *p;
if( n->m_left m_nil )
p = n;
else
p = n->successor( m_nil );
node* x = p->m_left != m_nil ? p->m_left : p->m_right;
x->m_parent = p->m_parent;
if( p->m_parent == m_nil )
m_root = x;
else if( p == p->m_parent->m_left )
p->m_parent->m_left = x;
else
p->m_parent->m_right = x;
if( p != n )
p->m_data = n->m_data;
if( p->m_colour == node::BLACK )
{
n = x;
// b = brother
node* b;
while( n != m_root && n->m_colour == node::BLACK )
{
if( n == n->m_parent->m_left )
{
b = n->m_parent->m_right;
if( b->m_colour == node::RED )
{
b->m_colour = node::BLACK;
n->m_parent->m_colour = node::RED;
rotate_left( n->m_parent );
b = n->m_parent->m_right;
}
if( b->m_right->m_colour == node::BLACK )
{
if( b->m_left->m_colour == node::BLACK )
{
b->m_colour = node::RED;
n = n->m_parent;
}
else
{
b->m_left->m_colour = node::BLACK;
b->m_colour = node::RED;
rotate_right( b );
b = n->m_parent->m_right;
}
}
b->m_colour = n->m_parent->m_colour;
n->m_parent->m_colour = node::BLACK;
b->m_right->m_colour = node::BLACK;
rotate_left( n->m_parent );
n = m_root;
}
else
{
b = n->m_parent->m_left;
if( b->m_colour = node::RED )
{
b->m_colour = node::BLACK;
n->m_parent->m_colour = node::RED;
rotate_right( n->m_parent );
b = n->m_parent->m_left;
}
if( b->m_left->m_colour == node::BLACK )
{
if( b->m_right->m_colour == node::BLACK )
{
b->m_colour = node::RED;
n = n->m_parent;
}
else
{
b->m_right->m_colour = node::BLACK;
b->m_colour = node::RED;
rotate_left( b );
b = n->m_parent->m_left;
}
}
b->m_colour = n->m_parent->m_colour;
n->m_parent->m_colour = node::BLACK;
b->m_left->m_colour = node::BLACK;
rotate_right( n->m_parent );
n = m_root;
}
}
n->m_colour = node::BLACK;
}
}
void traverse( node *n = NULL )
{
if( !n )
n = m_root;
if( n != m_nil )
{
traverse( n->m_left );
std::cout<
static int count = 0;
++count;
if(count%20==0)
{
std::cout< count=0; } traverse( n->m_right ); } } }; int main() { rbtree* tree = new rbtree(); srand(( unsigned ) time( NULL )); std::cout<<"\nUnsorted\n"< int num=0; while( num < 600 ) { int r=rand(); if( tree->insert_key( r )) { std::cout< if( ++num%20==0 ) std::cout< } } std::cout<<"\nSorted\n"< tree->traverse(); std::cout< delete( tree ); tree = NULL; } Output Unsorted 11018 12024 19579 14269 11141 27830 23548 7243 31975 21161 5654 15205 936 11644 26265 7206 2757 15177 30215 23707 12643 29359 9300 20859 23477 16421 8426 19986 11041 11661 17392 10367 16798 10253 3276 19999 21601 22554 27110 31817 20920 16341 11695 28988 7734 5019 21731 10581 11536 215 523 31878 30663 22299 21061 12291 6407 18288 28487 20542 3792 11754 674 26390 26579 6527 28228 25163 24607 1560 28225 15926 12540 31977 2003 18615 6167 3838 27039 4206 23008 24087 8505 21550 17201 10166 18923 1710 28208 1654 6322 14978 20086 23966 27018 2634 18545 8950 12779 20778 22534 31450 31892 18298 2683 23180 21127 22462 20373 9423 13653 16344 26109 29873 3739 21116 26344 2728 14541 27877 13559 4064 1330 29894 21084 9172 25392 29316 25151 26652 3274 7074 22880 32389 23655 24957 8701 11623 12245 22585 14070 7731 31885 2555 31279 27212 31033 2648 18998 27160 115 24078 6950 31318 4304 2802 5835 11186 3613 25642 2054 4246 10216 26268 5491 7492 2371 14758 3914 20002 13764 10256 21635 2132 14288 9535 4926 26768 1049 12971 26721 29742 13926 14739 8835 24703 2963 11503 11273 25696 15576 1958 24718 18447 8270 31489 20873 10045 12974 24927 15913 6500 28252 18731 17028 13402 5029 11276 497 7463 17989 9819 20658 6932 9261 17114 8407 24836 14723 11939 13918 263 30185 26974 26271 15917 1794 17847 12440 15410 19984 28260 28629 22438 24946 12097 14189 28821 7370 27409 14774 19141 25682 9841 5359 18256 8525 16361 7820 21160 2039 28180 30927 29657 31164 26881 9880 24846 22440 17112 4478 15703 22815 13249 13854 25513 15054 23809 27315 25383 23009 18278 29672 4255 3958 8422 23530 20824 24658 32131 16320 779 21715 8050 1759 9519 3366 14585 10105 26042 26275 26135 420 16373 30217 21735 30830 17189 8718 27479 13283 10681 25528 1378 2781 28337 2905 11818 10188 28499 11115 28488 21792 10943 10848 11379 23558 16855 12536 18252 18647 26512 3722 2209 9210 28931 14551 28667 3169 26798 6783 24401 14010 24783 11215 8327 27882 17681 3546 25652 8631 28522 23499 7592 27844 1092 9849 24622 707 23003 20028 8590 32230 28390 12032 1494 2710 13433 21143 6234 19560 12074 7508 5626 3917 13171 10453 11427 6409 16727 16672 21529 12006 17224 14322 9203 9129 13385 595 19175 453 29008 21614 2887 9679 14830 12192 24780 23858 9265 5839 13203 23844 1994 23805 15461 9688 9323 16924 32315 9717 1907 21028 30977 12872 29901 14948 31131 9653 22293 2325 11046 15732 31485 2869 19840 1402 6640 15507 13578 26932 30709 32294 30636 15483 6357 1698 27418 20677 20608 16717 22614 27288 12973 3855 2167 11077 9665 7625 3752 17106 7410 18920 29555 32312 15788 15930 9536 1487 29747 17920 21016 24582 15243 1348 3759 3159 7317 2925 28322 19066 10362 29712 29181 25049 29260 2569 27648 32069 19435 8395 18211 28391 18982 6132 19031 28793 21539 15653 17295 13238 16897 16 15231 22286 20155 11474 5795 4767 24912 8324 18308 12641 28961 30263 10912 2458 6457 16678 28592 12564 1552 31507 16860 14074 2656 2649 9375 11563 23453 19829 16407 4256 25322 10438 18358 25935 31096 8593 14651 18767 16143 10824 2016 17212 16106 1036 2005 20445 22216 22896 11758 29444 5184 30336 30617 20406 31829 16898 3858 2956 29002 23547 32730 345 10936 1397 3941 1805 29661 13696 3602 19162 9271 32631 13409 2965 1617 11908 24673 12382 8414 14950 18279 899 5636 31090 28677 5282 3322 13272 2106 1550 22997 31784 27623 18804 22431 28949 28546 4031 10410 19576 17166 28728 20771 25496 331 24554 31912 16170 10853 6561 7569 12163 10329 23044 12042 6662 8056 Sorted 16 115 215 263 331 345 420 453 497 523 595 674 707 779 899 936 1036 1049 1092 1330 1348 1378 1397 1402 1487 1494 1550 1552 1560 1617 1654 1698 1710 1759 1794 1805 1907 1958 1994 2003 2005 2016 2039 2054 2106 2132 2167 2209 2325 2371 2458 2555 2569 2634 2648 2649 2656 2683 2710 2728 2757 2781 2802 2869 2887 2905 2925 2956 2963 2965 3159 3169 3274 3276 3322 3366 3546 3602 3613 3722 3739 3752 3759 3792 3838 3855 3858 3914 3917 3941 3958 4031 4064 4206 4246 4255 4256 4304 4478 4767 4926 5019 5029 5184 5282 5359 5491 5626 5636 5654 5795 5835 5839 6132 6167 6234 6322 6357 6407 6409 6457 6500 6527 6561 6640 6662 6783 6932 6950 7074 7206 7243 7317 7370 7410 7463 7492 7508 7569 7592 7625 7731 7734 7820 8050 8056 8270 8324 8327 8395 8407 8414 8422 8426 8505 8525 8590 8593 8631 8701 8718 8835 8950 9129 9172 9203 9210 9261 9265 9271 9300 9323 9375 9423 9519 9535 9536 9653 9665 9679 9688 9717 9819 9841 9849 9880 10045 10105 10166 10188 10216 10253 10256 10329 10362 10367 10410 10438 10453 10581 10681 10824 10848 10853 10912 10936 10943 11018 11041 11046 11077 11115 11141 11186 11215 11273 11276 11379 11427 11474 11503 11536 11563 11623 11644 11661 11695 11754 11758 11818 11908 11939 12006 12024 12032 12042 12074 12097 12163 12192 12245 12291 12382 12440 12536 12540 12564 12641 12643 12779 12872 12971 12973 12974 13171 13203 13238 13249 13272 13283 13385 13402 13409 13433 13559 13578 13653 13696 13764 13854 13918 13926 14010 14070 14074 14189 14269 14288 14322 14541 14551 14585 14651 14723 14739 14758 14774 14830 14948 14950 14978 15054 15177 15205 15231 15243 15410 15461 15483 15507 15576 15653 15703 15732 15788 15913 15917 15926 15930 16106 16143 16170 16320 16341 16344 16361 16373 16407 16421 16672 16678 16717 16727 16798 16855 16860 16897 16898 16924 17028 17106 17112 17114 17166 17189 17201 17212 17224 17295 17392 17681 17847 17920 17989 18211 18252 18256 18278 18279 18288 18298 18308 18358 18447 18545 18615 18647 18731 18767 18804 18920 18923 18982 18998 19031 19066 19141 19162 19175 19435 19560 19576 19579 19829 19840 19984 19986 19999 20002 20028 20086 20155 20373 20406 20445 20542 20608 20658 20677 20771 20778 20824 20859 20873 20920 21016 21028 21061 21084 21116 21127 21143 21160 21161 21529 21539 21550 21601 21614 21635 21715 21731 21735 21792 22216 22286 22293 22299 22431 22438 22440 22462 22534 22554 22585 22614 22815 22880 22896 22997 23003 23008 23009 23044 23180 23453 23477 23499 23530 23547 23548 23558 23655 23707 23805 23809 23844 23858 23966 24078 24087 24401 24554 24582 24607 24622 24658 24673 24703 24718 24780 24783 24836 24846 24912 24927 24946 24957 25049 25151 25163 25322 25383 25392 25496 25513 25528 25642 25652 25682 25696 25935 26042 26109 26135 26265 26268 26271 26275 26344 26390 26512 26579 26652 26721 26768 26798 26881 26932 26974 27018 27039 27110 27160 27212 27288 27315 27409 27418 27479 27623 27648 27830 27844 27877 27882 28180 28208 28225 28228 28252 28260 28322 28337 28390 28391 28487 28488 28499 28522 28546 28592 28629 28667 28677 28728 28793 28821 28931 28949 28961 28988 29002 29008 29181 29260 29316 29359 29444 29555 29657 29661 29672 29712 29742 29747 29873 29894 29901 30185 30215 30217 30263 30336 30617 30636 30663 30709 30830 30927 30977 31033 31090 31096 31131 31164 31279 31318 31450 31485 31489 31507 31784 31817 31829 31878 31885 31892 31912 31975 31977 32069 32131 32230 32294 32312 32315 32389 32631 32730
See related links for an example.
It depends on what the tree is being used for. If the tree is being used to store data that is not going to be modified very much, than AVL trees are probably better. In most other cases, I'd say Red-Black trees are better.
Red-black trees are typically used in real-time applications, where worst-case guarantees are vital. Red-black trees often form the basis of other tree structures, including AVL trees and LLRB trees. Computational geometry, scheduling and language dictionaries are other possible applications for RB-based trees. They are also used in functional programming as a persistent data structure.
An AVL tree is another balanced binary search tree. Named after their inventors, Adelson-Velskii and Landis, they were the first dynamically balanced trees to be proposed. Like red-black trees, they are not perfectly balanced, but pairs of sub-trees differ in height by at most 1, maintaining an O(logn) search time. Addition and deletion operations also take O(logn) time.Definition of an AVL treeAn AVL tree is a binary search tree which has the following properties: The sub-trees of every node differ in height by at most one.Every sub-tree is an AVL tree.
We use the term balance when referring to balanced binary trees. These are typically implemented using red/black trees, thus ensuring every parent node has as many nodes under the left branch as it has under the right branch.
The positive terminals in voltmeters and ammeters are generally indicated by a red coloring and a + (plus) symbol. Negative is generally black and - (minus).
red oak and black oak
A weird shade of black is produced:
The red wire is Positive, (+) and the Black wire is Negative. (-)
purple
black + white
It depends on what the tree is being used for. If the tree is being used to store data that is not going to be modified very much, than AVL trees are probably better. In most other cases, I'd say Red-Black trees are better.
Red-black trees are typically used in real-time applications, where worst-case guarantees are vital. Red-black trees often form the basis of other tree structures, including AVL trees and LLRB trees. Computational geometry, scheduling and language dictionaries are other possible applications for RB-based trees. They are also used in functional programming as a persistent data structure.
Leopdia
The name "Black Widow" comes from the spider killing their mate, plus they are black with a red or yellow hourglass.
Black, ground. Red, battery plus. Green, right channel audio (plus black for the negative speaker lead), white, Left channel audio (plus black for negative speaker lead). This is assuming that you're talking about a car stereo you're trying to install.
Red, gold, green plus black star (in the middle of the gold)
The plus/minus (red/black) terminals are for testing Direct Current (DC) power sources.