Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <conio.h>
- #include <stdio.h>
- #include <time.h>
- using namespace std;
- int ile;
- struct node{
- int val;
- int bf;
- node *left;
- node *right;
- node *up;
- };
- void dfs_inorder(node *tree){
- if(tree){
- ile++;
- dfs_inorder(tree->left);
- //cout<<endl<<tree->val;
- dfs_inorder(tree->right);
- }
- return;
- }
- void dfs_preorder(node *tree){
- if(tree){
- cout<<endl<<tree->val;
- dfs_preorder(tree->left);
- dfs_preorder(tree->right);
- }
- return;
- }
- void dfs_postorder(node *tree){
- if(tree){
- dfs_postorder(tree->left);
- dfs_postorder(tree->right);
- ile++;
- delete tree;
- }
- }
- void lr(node *&root,node *A){
- node *B=A->left;
- node *C=B->right;
- node *D=A->up;
- B->right=C->left;
- if(B->right) B->right->up=B;
- A->left=C->right;
- if(A->left) A->left->up = A;
- C->right = A;
- C->left = B;
- A->up=B->up=C;
- C->up=D;
- if(D){
- if(D->left == A) D->left = C;
- else D->right = C;
- }
- else root=C;
- if(C->bf==1) A->bf=-1;
- else A->bf=0;
- if(C->bf==-1) B->bf=1;
- else B->bf = 0;
- C->bf = 0;
- return;
- }
- void ll(node *&root,node *A){
- node *B=A->left;
- node *C=A->up;
- A->left=B->right;
- if(A->left) A->left->up=A;
- B->right=A;
- B->up=C;
- A->up=B;
- if(C){
- if(C->left==A) C->left=B;
- else C->right=B;
- }
- else root=B;
- if(B->bf==1) A->bf=B->bf=0;
- else{
- A->bf=1;
- B->bf=-1;
- }
- return;
- }
- void rl(struct node *&root,struct node *A){
- node *B=A->right;
- node *C=B->left;
- node *D=A->up;
- B->left=C->right;
- if(B->left) B->left->up=B;
- A->right=C->left;
- if(A->right) A->right->up=A;
- C->left=A;
- C->right=B;
- A->up=B->up=C;
- C->up=D;
- if(D){
- if(D->left==A) D->left=C;
- else D->right=C;
- }
- else root=C;
- if(C->bf==-1) A->bf=1;
- else A->bf=0;
- if(C->bf==1) B->bf=-1;
- else B->bf=0;
- C->bf = 0;
- return;
- }
- void rr(struct node *&root,struct node *A){
- node *B=A->right;
- node *C=A->up;
- A->right=B->left;
- if(A->right) A->right->up=A;
- B->left=A;
- B->up=C;
- A->up=B;
- if(C){
- if(C->left==A) C->left=B;
- else C->right=B;
- }
- else root=B;
- if(B->bf==-1) A->bf=B->bf=0;
- else{
- A->bf=-1;
- B->bf=1;
- }
- return;
- }
- node *node_find(node *elem,int b){
- cout<<"Sciezka do elementu "<<b<<" ...";;
- while((elem)&&(elem->val!=b)){
- cout<<endl<<elem->val;
- if(b>=elem->val) elem=elem->right;
- else elem=elem->left;
- }
- return elem;
- }
- node *node_find_prim(node *elem,int b){
- while((elem)&&(elem->val!=b)){
- if(b>=elem->val) elem=elem->right;
- else elem=elem->left;
- }
- return elem;
- }
- node *node_up(node *elem){
- node *tmp;
- if(elem){
- if(elem->left){
- elem=elem->left;
- while(elem->right) elem=elem->right;
- }
- else
- do{
- tmp=elem;
- elem=elem->up;
- }while((elem)&&(elem->right!=tmp));
- }
- return elem;
- }
- node *node_erase(node *&root,node *del){
- node *tmp;
- node *del1;
- node *del2;
- bool cor;
- if(del->left && del->right){
- del1=node_erase(root,node_up(del));
- cor=false;
- }
- else{
- if(del->left){
- del1=del->left;
- del->left=NULL;
- }
- else{
- del1=del->right;
- del->right=NULL;
- }
- del->bf=0;
- cor =true;
- }
- if(del1){
- del1->up=del->up;
- del1->left=del->left;
- if(del1->left) del1->left->up=del1;
- del1->right=del->right;
- if(del1->right) del1->right->up=del1;
- del1->bf=del->bf;
- }
- if(del->up){
- if(del->up->left==del) del->up->left=del1;
- else del->up->right=del1;
- }
- else root=del1;
- if(cor){
- del2=del1;
- del1=del->up;
- while(del1){
- if(!del1->bf){
- if(del1->left==del2) del1->bf=-1;
- else del1->bf = 1;
- break;
- }
- else{
- if(((del1->bf==1) && (del1->left==del2)) || ((del1->bf==-1) && (del1->right==del2))){
- del1->bf=0;
- del2=del1;
- del1=del1->up;
- }
- else{
- if(del1->left==del2) tmp = del1->right;
- else tmp = del1->left;
- if(!tmp->bf){
- if(del1->bf==1) ll(root,del1);
- else rr(root,del1);
- break;
- }
- else if(del1->bf==tmp->bf){
- if(del1->bf==1) ll(root,del1);
- else rr(root,del1);
- del2=tmp;
- del1=tmp->up;
- }
- else{
- if(del1->bf==1) lr(root,del1);
- else rl(root,del1);
- del2=del1->up;
- del1=del2->up;
- }
- }
- }
- }
- }
- return del;
- }
- void node_add(struct node *&tree,int b){
- struct node *add=new struct node;
- struct node *tmp;
- struct node *root=tree;
- bool t;
- if(tree==NULL){
- tree=new struct node;
- tree->left=NULL;
- tree->right=NULL;
- tree->up=NULL;
- tree->val=b;
- return;
- }
- while(true){
- if(b>=tree->val){
- if(tree->right==NULL){
- tree->right=add;
- add->val=b;
- add->left=NULL;
- add->right=NULL;
- add->bf=0;
- add->up=tree;
- break;
- }
- else tree=tree->right;
- }
- else{
- if(tree->left==NULL){
- tree->left=add;
- add->val=b;
- add->left=NULL;
- add->right=NULL;
- add->bf=0;
- add->up=tree;
- break;
- }
- else tree=tree->left;
- }
- }
- if(tree->bf) tree->bf=0;
- else{
- if(tree->left==add) tree->bf=1;
- else tree->bf=-1;
- tmp=tree->up;
- t=false;
- while(tmp){
- if(tmp->bf){
- t=true;
- break;
- }
- if(tmp->left==tree) tmp->bf=1;
- else tmp->bf=-1;
- tree=tmp;
- tmp=tmp->up;
- }
- if(t){
- if(tmp->bf==1){
- if(tmp->right==tree) tmp->bf=0;
- else if(tree->bf==-1) lr(root,tmp);
- else ll(root,tmp);
- }
- else{
- if(tmp->left==tree) tmp->bf=0;
- else if(tree->bf==1) rl(root,tmp);
- else rr(root,tmp);
- }
- }
- }
- return;
- }
- void com(int comm,node *&root){
- return;
- }
- int *dane(int n){
- int index1;
- int index2;
- int tmp;
- int *tab=new int[n];
- for(int i=0;i<n;i++) tab[i]=i;
- for(int i=0;i<n*10;i++){
- index1=rand()%n;
- index2=rand()%n;
- tmp=tab[index1];
- tab[index1]=tab[index2];
- tab[index2]=tmp;
- }
- return tab;
- }
- void dane_delete(int *tab,int n){
- delete []tab;
- return;
- }
- int main(){
- srand(time(NULL));
- int cmd;
- node *root=NULL;
- node *root4ever=NULL;
- cout<<"1. dodaj elem (int)\n";
- cout<<"2. usun elem (int wartosc)\n";
- cout<<"3. znajdz elem (int wartosc)\n";
- cout<<"4. dfs preorder, post order\n";
- cout<<"5. stworz drzewo losowych (int ilosc)\n";
- cout<<"6. usun drzewo\n";
- //while(cin>>cmd) com(cmd,root);
- /*
- clock_t start;
- int *tab;
- system("cls");
- for(int i=500000;i<=5000000;i=i+500000) cout<<i<<" ";
- getche();
- system("cls");
- for(int i=500000;i<=5000000;i=i+500000){
- tab=dane(i);
- start=clock();
- for(int j=0;j<i;j++){
- node_add(root,tab[j]);
- if(j==0) root4ever=root;
- }
- cout<<endl<<clock()-start;
- start=clock();
- ile=0;
- for(int j=0;j<i/10;j++) node_find_prim(root,j);
- cout<<endl<<clock()-start;
- start=clock();
- dfs_inorder(root);
- cout<<endl<<clock()-start;
- cout<<endl<<ile;
- cout<<endl<<endl;
- dane_delete(tab,i);
- root=NULL;
- }
- */
- ile=0;
- node_add(root,0);
- root4ever=root;
- node_add(root,666);
- node_add(root,31);
- node_add(root,564);
- node_add(root,18);
- node_add(root,12);
- node_add(root,7);
- node_add(root,9);
- node_add(root,5);
- node_add(root,142);
- node_add(root,21);
- node_add(root,1331);
- node_add(root,121);
- node_add(root,111);
- node_add(root,1141);
- node_add(root,4121);
- dfs_inorder(root4ever);
- cout<<ile;
- getche();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement