fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define MAX 100
  3.  
  4.  
  5.  
  6. /*
  7.     sap xep chen
  8. */
  9. void print(int *a, int array_size) {
  10.     for(int i = 0 ; i <  array_size ; i++) {
  11.         printf("%-5d",a[i]);
  12.     }
  13.     printf("\n");
  14. }
  15. void inserttion_sort(int *a, int array_size) {
  16.     int i,j, last;
  17.     for(i = 1; i < array_size ; i++) {
  18.         last = a[i];
  19.         j = i;
  20.         while((j > 0) && ( a[j-1] > last)) {
  21.             a[j] = a[j-1];
  22.             j = j - 1;
  23.         }
  24.         a[j] = last;
  25.     }
  26. }
  27.  
  28. /*
  29.     day phai duoc sap xep theo thu tu khong giam (tang dan co the bang nhau)
  30.     phai cho phep truy cap truc tiep, suy ra khong ap dung voi danh sach lien ket don
  31. */
  32.  
  33. int binary_search_(int *a, int size_, int value_target) {
  34. /*
  35.     cach dung vong lap
  36.     logn
  37. */
  38.     int lower, upper, mid;
  39.     lower = 0;
  40.     upper = size_ - 1;
  41.     while(lower <= upper) {
  42.         mid = (lower + upper)/2;
  43.         if(value_target > a[mid] ) {
  44.             lower = mid + 1;
  45.         } else if (value_target < a[mid]) {
  46.             upper = mid - 1;
  47.         } else {
  48.             return mid;
  49.         }
  50.     }
  51.     return -1;
  52. }
  53.  
  54. int binary_search_(int *a, int lower, int upper, int value_target) {
  55. /*
  56.     cach dung de quy
  57.     logn
  58. */
  59.  
  60.    printf("\n%d %d\n", lower, upper);
  61.     if( lower > upper) {
  62.         return -1;
  63.     }
  64.  
  65.     int mid;
  66.     mid = (lower + upper)/2;
  67.     if( value_target < a[mid]) {
  68.         return binary_search_(a,0,mid-1,value_target);
  69.     } else if ( value_target > a[mid]) {
  70.         return binary_search_(a,mid+1,upper,value_target);
  71.     } else {
  72.         return mid;
  73.     }
  74. }
  75.  
  76.  
  77.  
  78.  
  79. /*
  80.     binary search tree
  81. */
  82.  
  83. typedef struct node {
  84.     int data;
  85.     struct node *left;
  86.     struct node *right;
  87.     struct node *parent;
  88. }node;
  89.  
  90. node* create_node(int data) {
  91.     node *root = (node*)malloc(sizeof(node));
  92.     if(root == NULL) {
  93.         printf("\nERORR ALLOCATE");
  94.         exit(1);
  95.     }
  96.     root->data = data;
  97.     root->left = NULL;
  98.     root->right = NULL;
  99.     root->parent = NULL;
  100.     return root;
  101. }
  102.  
  103. void inOrder(node *root) {
  104.     if(root != NULL) {
  105.         inOrder(root->left);
  106.         printf("%d  ",root->data);
  107.         inOrder(root->right);
  108.     }
  109.  
  110. }
  111.  
  112. void free_tree(node *root) {
  113.     if (root == NULL) {
  114.         return;
  115.     }
  116.     free_tree(root->left);
  117.     free_tree(root->right);
  118.     free(root);
  119. }
  120.  
  121. node* create_tree() {
  122.     node *a_ = create_node(50);
  123.     node *b = create_node(30);
  124.     node *c = create_node(55);
  125.     node *d = create_node(25);
  126.     node *e = create_node(35);
  127.     node *f = create_node(53);
  128.     node *g = create_node(60);
  129.     node *h = create_node(10);
  130.     node *i = create_node(31);
  131.     node *k = create_node(37);
  132.     node *j = create_node(62);
  133.     node *l = create_node(20);
  134.     node *m = create_node(23);
  135.     //link
  136.     a_->parent = NULL;
  137.     a_->left =  b;
  138.     a_->right = c;
  139.     b->parent = a_;
  140.     c->parent = a_;
  141.  
  142.     b->left = d;
  143.     b->right = e;
  144.     d->parent = b;
  145.     e->parent = b;
  146.  
  147.     c->left = f;
  148.     c->right = g;
  149.     f->parent = c;
  150.     f->parent = c;
  151.  
  152.     d->left = h;
  153.     h->parent = d;
  154.  
  155.     e->left = i;
  156.     e->right = k;
  157.     i->parent = e;
  158.     k->parent = e;
  159.  
  160.     g->right =j;
  161.     j->parent = g;
  162.  
  163.     h->right = l;
  164.     l->parent = h;
  165.  
  166.     l->right = m;
  167.     m->parent = l;
  168.     return a_;
  169. }
  170.  
  171. node* find_min(node *root) {
  172.     if(root == NULL) {
  173.         return (NULL);
  174.     } else {
  175.         if(root->left == NULL) return root;
  176.         else return find_min(root->left);
  177.     }
  178. }
  179.  
  180. node* find_max(node *root) {
  181.     if(root == NULL) {
  182.         return (NULL);
  183.     } else {
  184.         if(root->right == NULL) return root;
  185.         else return find_max(root->right);
  186.     }
  187. }
  188.  
  189. int successor(node *root, node *x) {
  190.     if(x->right != NULL) {
  191.         node *tmp = find_min(x->right);
  192.         return tmp->data;
  193.     }
  194.  
  195.     // neu no khong co cay con phai
  196.     // thi tim to tien gan nhau co cay con trai la no
  197.     // hoac to tien gan nhat co cay con trai
  198.     node *p = x->parent;
  199.     while(p != NULL && p->right == x) {
  200.         x = p;
  201.         p = x->parent;
  202.     }
  203.     return p->data;
  204. }
  205.  
  206. int predecessor(node *root, node *x) {
  207.     if(x->left != NULL) {
  208.         node *tmp = find_max(x->left);
  209.         return tmp->data;
  210.     }
  211.  
  212.     // neu no khong co cay con phai
  213.     // thi tim to tien gan nhau co cay con trai la no
  214.     // hoac to tien gan nhat co cay con trai
  215.     node *p = x->parent;
  216.     while(p != NULL && p->left == x) {
  217.         x = p;
  218.         p = x->parent;
  219.     }
  220.     return p->data;
  221. }
  222. /*
  223.     chinh la binary search
  224. */
  225. node* search_(node *root, int target) {
  226. //    int flag = 0;
  227.     if(root != NULL) {
  228.         if(target < root->data) {
  229.             return search_(root->left, target);
  230.         } else if( target > root->data) {
  231.             return search_(root->right, target);
  232.         } else {
  233.             return root;
  234.         }
  235.     }
  236.     return NULL;
  237. }
  238.  
  239. void search_result(node *root, int target) {
  240.     node *tmp2 = search_(root,target);
  241.     if(tmp2 != NULL) {
  242.         printf("founded");
  243.     } else {
  244.         printf("not founded");
  245.     }
  246.     printf("\n");
  247. }
  248.  
  249. /*
  250.     thac tac insert
  251.     phai dam bao van la cay bst
  252. */
  253.  
  254. node* insert_bst(node *root, int value) {
  255.     if( root == NULL) {
  256.         root = create_node(value);
  257.     } else if ( value > root->data) {
  258.         root->right = insert_bst(root->right, value);
  259.         /* update pararen cho node them vao do
  260.             se bi trung lap vs cai node truoc do
  261.             nhung khong sao
  262.         */
  263.         root->right->parent = root;
  264.     } else if ( value < root->data) {
  265.         root->left = insert_bst(root->left, value);
  266.         root->left->parent = root;
  267.     }
  268.     return root;
  269. }
  270. /*
  271.     thao tac delete, khi loai bo 1 node can dam bao cay van la bst
  272.     4 truong hop
  273.     thu nhat: node can loai bo la node leaf
  274.     thu hai: chi co con trai
  275.     thu ba: chi co con phai
  276.     thu 4: co ca 2 con
  277. */
  278.  
  279. node* delete_bst(node *root,int value) {
  280.     node *tmp;
  281.     if( value > root->data) {
  282.         root->right = delete_bst(root->right, value);
  283.     } else if ( value < root->data) {
  284.         root->left = delete_bst(root->left, value);
  285.     } else if( root->left && root->right) {
  286.         /* node co 2 con, roi vao truong hop 4
  287.             tim sucessor y cua node can xoa x
  288.             go y ra khoi cay
  289.             noi con con phai cua y vao cha cua y (VI SUCCESSOR CUA NO LA PHAN TU TRAI NHAT ROI,
  290.              NEN NEU CO, THI CHI CO THE CO CON PHAI THOI)
  291.             thay the y vao vi tri can xoa
  292.         */
  293.         tmp = find_min(root->right);
  294.         root->data = tmp->data;
  295.         root->right = delete_bst(root->right, tmp->data);
  296.     }
  297.     else{
  298.         /*den day la tim duoc vi tri can xoa roi*/
  299.         /* truong hop 1-3`*/
  300.         tmp = root;
  301.         /* node CHI CO con phai, hoac khong co con*/
  302.         if(tmp->left == NULL) {
  303.             root = root->right;
  304.         } else if ( tmp->right == NULL) {
  305.         /* node co 1 con trai*/
  306.             root = root->left;
  307.         }
  308.         free(tmp);
  309.         return root;
  310.     }
  311.  
  312. }
  313.  
  314. void delete_bst_result(node *root, int value) {
  315.     if( search_(root, value)) {
  316.         delete_bst(root, value);
  317.     } else {
  318.         printf("\nnode not exist");
  319.     }
  320. }
  321.  
  322.  
  323. int main() {
  324. ///**
  325.     // int a[MAX] = {20,4,1,3,2,16,9,10,14,8,7};
  326.     int a[MAX] = {1,2,3,4,5,6,7,8};
  327.     int size_ = 7;
  328.     // inserttion_sort(a,size_);
  329.     // print(a,size_);
  330.     int value_target = -10;
  331.     // printf("%d\n", binary_search_(a,size_,value_target));
  332.     // recursive
  333.     // binary_search_(a,0,size_,value_target);
  334.     printf("%d", binary_search_(a,0,size_,value_target));
  335. //*/
  336.  
  337. /**
  338.     node *root = create_tree();
  339.     node *tmp = find_min(root);
  340.     printf("\nmin tree bst = %d",tmp->data);
  341.     node *tmp1 = find_max(root);
  342.     printf("\nmax tree bst = %d",tmp1->data);
  343.     printf("\nsuccessor: ");
  344.     printf("%d ---> %d ",root->left->left->left->right->right->data,successor(root,root->left->left->left->right->right));
  345.     printf("\npredecessor: ");
  346.     printf("%d ---> %d ",root->left->left->left->right->right->data,predecessor(root,root->left->left->left->right->right));
  347.     printf("\ninorder tree: ");
  348.     inOrder(root);
  349.     int node_target = -300;
  350.     printf("\nsearch value node %d: ",node_target);
  351.     search_result(root,node_target);
  352.     printf("\ninsert 34");
  353.     insert_bst(root, 34);
  354.     printf("\ninorder tree: ");
  355.     inOrder(root);
  356.     printf("\ninsert 36");
  357.     insert_bst(root, 36);
  358.     printf("\ninorder tree: ");
  359.     inOrder(root);
  360.     printf("\n<<<<test>>>>");
  361.     printf("\nsuccessor: ");
  362.     printf("%d ---> %d ",root->left->right->left->data,successor(root,root->left->right->left));
  363. //    printf("\n %d", root->left->right->left->right->parent->data);
  364.     printf("\npredecessor: ");
  365.     printf("%d ---> %d ",root->left->right->right->data,predecessor(root,root->left->right->right));
  366.     printf("\ndelete value node leaf 23: ");
  367.     delete_bst_result(root,23);
  368.     printf("\ndelete value node leaf 20: ");
  369.     delete_bst_result(root,20);
  370.     printf("\ndelete value node leaf 25: ");
  371.     delete_bst_result(root,25);
  372.     printf("\ninorder tree: ");
  373.     inOrder(root);
  374.     printf("\ndelete value node not leaf 50: ");
  375.     delete_bst_result(root,50);
  376.     printf("\ninorder tree: ");
  377.     inOrder(root);
  378.     free_tree(root);
  379.     node *a = create_node(25);
  380.     insert_bst(a,25);
  381.     insert_bst(a,15);
  382.     insert_bst(a,40);
  383.     insert_bst(a,20);
  384.     insert_bst(a,30);
  385.     insert_bst(a,45);
  386.     insert_bst(a,17);
  387.     delete_bst_result(a,15);
  388.     printf("\ninorder tree: ");
  389.     inOrder(a);
  390.     free(a);
  391. */
  392.  
  393.     return 0;
  394. }
Success #stdin #stdout 0s 4416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 7

0 2

0 0

0 -1
-1
https://ideone.com/0vpfsU
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!