fork download
copy 
  1. #include <iostream>
  2. #include <time.h>
  3. #include <cstdlib>
  4. #include <stdio.h>
  5.  
  6. using namespace std;
  7.  
  8. struct Node
  9. {
  10.    int Key;
  11.    Node* Left_Child;
  12.    Node* Right_Child;
  13.    Node* Father;
  14. };
  15.  
  16. void Initialization(Node* &Ref_Root)
  17. {
  18.    Ref_Root = 0;
  19. }
  20.  
  21. Node* Find_Node(Node* &Ref_Root, int Key)
  22. {
  23.    if (!Ref_Root) return 0;
  24.    Node* Temp = Ref_Root;
  25.    while (true)
  26.    {
  27.       if (Temp->Key == Key) return Temp;
  28.       if (Key < Temp->Key)
  29.       {
  30.          if (!Temp->Left_Child) return 0;
  31.          Temp = Temp->Left_Child;
  32.          continue;
  33.       }
  34.       if (Key > Temp->Key)
  35.       {
  36.          if (!Temp->Right_Child) return 0;
  37.          Temp = Temp->Right_Child;
  38.          continue;
  39.       }
  40.    }
  41. }
  42.  
  43. int Ten_To_One_Million_Ten(void)
  44. {
  45.    int Number = 0;
  46.    while (Number > 1000010 || Number < 10)
  47.    {
  48.       Number = (rand() << 5) + rand()%32;
  49.    }
  50.    return Number;
  51. }
  52.  
  53. bool Add_Node(Node* &Ref_Root, int Key)
  54. {
  55.    if (!Ref_Root)
  56.    {
  57.       Ref_Root = new Node;
  58.       Ref_Root->Left_Child = 0;
  59.       Ref_Root->Right_Child = 0;
  60.       Ref_Root->Father = 0;
  61.       Ref_Root->Key = Key;
  62.       return true;
  63.    }
  64.    if (Find_Node(Ref_Root, Key) != 0) return false;
  65.    Node* Temp;
  66.    Temp = Ref_Root;
  67.    while (true)
  68.    {
  69.       if (Key < Temp->Key)
  70.       {
  71.          if (Temp->Left_Child)
  72.          {
  73.             Temp = Temp->Left_Child;
  74.             continue;
  75.          }
  76.          if (!Temp->Left_Child)
  77.          {
  78.             Temp->Left_Child = new Node;
  79.             Temp->Left_Child->Left_Child = 0;
  80.             Temp->Left_Child->Right_Child = 0;
  81.             Temp->Left_Child->Father = Temp;
  82.             Temp->Left_Child->Key = Key;
  83.             return true;
  84.          }
  85.       }
  86.       if (Key > Temp->Key)
  87.       {
  88.          if (Temp->Right_Child)
  89.          {
  90.             Temp = Temp->Right_Child;
  91.             continue;
  92.          }
  93.          if (!Temp->Right_Child)
  94.          {
  95.             Temp->Right_Child = new Node;
  96.             Temp->Right_Child->Left_Child = 0;
  97.             Temp->Right_Child->Right_Child = 0;
  98.             Temp->Right_Child->Father = Temp;
  99.             Temp->Right_Child->Key = Key;
  100.             return true;
  101.          }
  102.       }
  103.    }
  104. }
  105.  
  106. void Create_Tree(Node* &Ref_Root, int X)
  107. {
  108.    int i = X;
  109.    while (i > 0)
  110.    {
  111.       if (Add_Node(Ref_Root, Ten_To_One_Million_Ten())) --i;
  112.    }
  113. }
  114.  
  115. bool Delete_Node(Node* &Ref_Root, int Key)
  116. {
  117.    if (!Ref_Root) return false;
  118.    Node* Temp;
  119.    Node* Father;
  120.    if (Ref_Root->Key == Key)
  121.    {
  122.       if (!Ref_Root->Left_Child && !Ref_Root->Right_Child)
  123.       {
  124.          delete Ref_Root;
  125.          Ref_Root = 0;
  126.          return true;
  127.       }
  128.       if (Ref_Root->Left_Child && !Ref_Root->Right_Child)
  129.       {
  130.          Temp = Ref_Root;
  131.          Ref_Root = Ref_Root->Left_Child;
  132.          delete Temp;
  133.          return true;
  134.       }
  135.       if (!Ref_Root->Left_Child && Ref_Root->Right_Child)
  136.       {
  137.          Temp = Ref_Root;
  138.          Ref_Root = Ref_Root->Right_Child;
  139.          delete Temp;
  140.          return true;
  141.       }
  142.       if (Ref_Root->Left_Child && Ref_Root->Right_Child)
  143.       {
  144.          if (!Ref_Root->Left_Child->Right_Child)
  145.          {
  146.             Temp = Ref_Root->Left_Child;
  147.             Temp->Right_Child = Ref_Root->Right_Child;
  148.             delete Ref_Root;
  149.             Ref_Root = Temp;
  150.             return true;
  151.          }
  152.          Temp = Ref_Root->Left_Child;
  153.          Father = Ref_Root;
  154.          while (Temp->Right_Child)
  155.          {
  156.             Father = Temp;
  157.             Temp = Temp->Right_Child;
  158.          }
  159.          if (!Temp->Left_Child)
  160.          {
  161.             Father->Right_Child = 0;
  162.             Temp->Left_Child = Ref_Root->Left_Child;
  163.             Temp->Right_Child = Ref_Root->Right_Child;
  164.             delete Ref_Root;
  165.             Ref_Root = Temp;
  166.             return true;
  167.          }
  168.          if (Temp->Left_Child)
  169.          {
  170.             Father->Right_Child = Temp->Left_Child;
  171.             Temp->Left_Child = Ref_Root->Left_Child;
  172.             Temp->Right_Child = Ref_Root->Right_Child;
  173.             delete Ref_Root;
  174.             Ref_Root = Temp;
  175.             return true;
  176.          }
  177.       }
  178.    }
  179.    Temp = Find_Node(Ref_Root, Key);
  180.    if (Temp == 0) return false;
  181.    Father = Temp->Father;
  182.    if (!Temp->Left_Child && !Temp->Right_Child)
  183.    {
  184.       if (Father->Left_Child && Father->Left_Child->Key == Temp->Key) Father->Left_Child = 0;
  185.       if (Father->Right_Child && Father->Right_Child->Key == Temp->Key) Father->Right_Child = 0;
  186.       delete Temp;
  187.       return true;
  188.    }
  189.    if (Temp->Left_Child && !Temp->Right_Child)
  190.    {
  191.       if (Father->Left_Child && Father->Left_Child->Key == Temp->Key) Father->Left_Child = Temp->Left_Child;
  192.       if (Father->Right_Child && Father->Right_Child->Key == Temp->Key) Father->Right_Child = Temp->Left_Child;
  193.       delete Temp;
  194.       return true;
  195.    }
  196.    if (!Temp->Left_Child && Temp->Right_Child)
  197.    {
  198.       if (Father->Left_Child && Father->Left_Child->Key == Temp->Key) Father->Left_Child = Temp->Right_Child;
  199.       if (Father->Right_Child && Father->Right_Child->Key == Temp->Key) Father->Right_Child = Temp->Right_Child;
  200.       delete Temp;
  201.       return true;
  202.    }
  203.    if (Temp->Left_Child && Temp->Right_Child)
  204.    {
  205.       if (!Temp->Left_Child->Right_Child)
  206.       {
  207.          Temp->Left_Child->Right_Child = Temp->Right_Child;
  208.          if (Father->Left_Child && Father->Left_Child->Key == Temp->Key) Father->Left_Child = Temp->Left_Child;
  209.          if (Father->Right_Child && Father->Right_Child->Key == Temp->Key) Father->Right_Child = Temp->Left_Child;
  210.          delete Temp;
  211.          return true;
  212.       }
  213.       if (Temp->Left_Child->Right_Child)
  214.       {
  215.          Node* Temp2 = Temp->Left_Child;
  216.          Node* Temp3 = Temp->Left_Child->Right_Child;
  217.          while (Temp3->Right_Child)
  218.          {
  219.             Temp2 = Temp3;
  220.             Temp3 = Temp3->Right_Child;
  221.          }
  222.          if (!Temp3->Left_Child)
  223.          {
  224.             if (Father->Left_Child && Father->Left_Child->Key == Temp->Key) Father->Left_Child = Temp3;
  225.             if (Father->Right_Child && Father->Right_Child->Key == Temp->Key) Father->Right_Child = Temp3;
  226.             Temp2->Right_Child = 0;
  227.             Temp3->Right_Child = Temp->Right_Child;
  228.             Temp3->Left_Child = Temp->Left_Child;
  229.             delete Temp;
  230.             return true;
  231.          }
  232.          if (Temp3->Left_Child)
  233.          {
  234.             if (Father->Left_Child && Father->Left_Child->Key == Temp->Key) Father->Left_Child = Temp3;
  235.             if (Father->Right_Child && Father->Right_Child->Key == Temp->Key) Father->Right_Child = Temp3;
  236.             Temp2->Right_Child = Temp3->Left_Child;
  237.             Temp3->Right_Child = Temp->Right_Child;
  238.             Temp3->Left_Child = Temp->Left_Child;
  239.             delete Temp;
  240.             return true;
  241.          }
  242.       }
  243.    }
  244. }
  245.  
  246. void Rotate_Left(Node* &Ref_Root, Node* Ref_Node)
  247. {
  248.    if (!Ref_Root) return;
  249.    if (!Ref_Node->Right_Child) return;
  250.    Node* Right_Child = Ref_Node->Right_Child;
  251.    if (!Ref_Node->Father)
  252.    {
  253.       Ref_Node->Right_Child = Right_Child->Left_Child; //
  254.       if (Right_Child->Left_Child) Right_Child->Left_Child->Father = Ref_Node; //
  255.       Right_Child->Left_Child = Ref_Node; //
  256.       Right_Child->Father = 0;
  257.       Ref_Node->Father = Right_Child; //
  258.       Ref_Root = Right_Child; 
  259.    }
  260.    else
  261.    {
  262.       Node* Father = Ref_Node->Father;
  263.       bool Is_Left_Child = true;
  264.       if (Father->Right_Child && Father->Right_Child->Key == Ref_Node->Key) Is_Left_Child = false;
  265.       Ref_Node->Right_Child = Right_Child->Left_Child; //
  266.       if (Right_Child->Left_Child) Right_Child->Left_Child->Father = Ref_Node; //
  267.       Right_Child->Left_Child = Ref_Node; //
  268.       Ref_Node->Father = Right_Child; //
  269.       Right_Child->Father = Father;
  270.       if (Is_Left_Child == true) Father->Left_Child = Right_Child;
  271.       else Father->Right_Child = Right_Child;
  272.    }
  273. }
  274.  
  275. void Rotate_Right(Node* &Ref_Root, Node* Ref_Node)
  276. {
  277.    if (!Ref_Root) return;
  278.    if (!Ref_Node->Left_Child) return;
  279.    Node* Left_Child = Ref_Node->Left_Child;
  280.    if (!Ref_Node->Father)
  281.    {
  282.       Ref_Node->Left_Child = Left_Child->Right_Child;
  283.       if (Left_Child->Right_Child) Left_Child->Right_Child->Father = Ref_Node;
  284.       Left_Child->Right_Child = Ref_Node;
  285.       Left_Child->Father = 0;
  286.       Ref_Node->Father = Left_Child;
  287.       Ref_Root = Left_Child;   
  288.    }
  289.    else
  290.    {
  291.       Node* Father = Ref_Node->Father;
  292.       bool Is_Left_Child = true;
  293.       if (Father->Right_Child && Father->Right_Child->Key == Ref_Node->Key) Is_Left_Child = false;
  294.       Ref_Node->Left_Child = Left_Child->Right_Child;
  295.       if (Left_Child->Right_Child) Left_Child->Right_Child->Father = Ref_Node;
  296.       Left_Child->Right_Child = Ref_Node;
  297.       Ref_Node->Father = Left_Child;
  298.       Left_Child->Father = Father;
  299.       if (Is_Left_Child == true) Father->Left_Child = Left_Child;
  300.       else Father->Right_Child = Left_Child;
  301.    }
  302. }
  303.  
  304. int Log2(int N)
  305. {
  306.    int T = 1;
  307.    while (T < N) T <<= 1;
  308.    if (T > N) T >>= 1;
  309.    return T;
  310. }
  311.  
  312. void DSW(Node* &Ref_Root)
  313. {
  314.    if (!Ref_Root) return;
  315.    int Nodes_Counter = 1;
  316.    while (Ref_Root->Left_Child) Rotate_Right(Ref_Root, Ref_Root);
  317.    Node* Ref_Node = Ref_Root->Right_Child;
  318.    if (!Ref_Node) return;
  319.    while (Ref_Node)
  320.    {
  321.       if (Ref_Node->Left_Child)
  322.       {
  323. 	     Rotate_Right(Ref_Root, Ref_Node);
  324. 	     Ref_Node = Ref_Node->Father;
  325. 	  }
  326. 	  else
  327. 	  {
  328. 		 ++Nodes_Counter;
  329. 		 Ref_Node = Ref_Node->Right_Child;
  330. 	  }
  331.    }
  332.    int N = Nodes_Counter + 1 - Log2(Nodes_Counter + 1);
  333.    Ref_Node = Ref_Root;
  334.    for (int i = 0; i < N; ++i)
  335.    {
  336.       Rotate_Left(Ref_Root,Ref_Node);
  337.       Ref_Node = Ref_Node->Father->Right_Child;
  338.    }
  339.    int X = Nodes_Counter - N;
  340.    while(X > 1)
  341.    {
  342.       X >>= 1;
  343.       Ref_Node = Ref_Root;
  344.       for(int i = 0; i < X; ++i)
  345.       {
  346.          Rotate_Left(Ref_Root,Ref_Node);
  347.          Ref_Node = Ref_Node->Father->Right_Child;
  348.       }
  349.    }
  350. }
  351.  
  352. void Print_In_Order(Node* &Ref_Root)
  353. {
  354.    if (!Ref_Root) return;
  355.    if (Ref_Root->Left_Child) Print_In_Order(Ref_Root->Left_Child);
  356.    cout << Ref_Root->Key << endl;
  357.    if (Ref_Root->Right_Child) Print_In_Order(Ref_Root->Right_Child);
  358. }
  359.  
  360. int Calculate_Height(Node* &Ref_Node)
  361. {
  362.    int Left_Height = 0;
  363.    int Right_Height = 0;
  364.    if (Ref_Node->Left_Child) Left_Height = Calculate_Height(Ref_Node->Left_Child);
  365.    if (Ref_Node->Right_Child) Right_Height = Calculate_Height(Ref_Node->Right_Child);
  366.    if (Left_Height > Right_Height) 
  367.    {
  368.       ++Left_Height;
  369.       return Left_Height;
  370.    }
  371.    if (Left_Height <= Right_Height)
  372.    {
  373.       ++Right_Height;
  374.       return Right_Height;
  375.    }
  376. }
  377.  
  378. int main()
  379. {
  380.    int X1, X2;
  381.  
  382.    FILE* fp = fopen("inlab04.txt", "r");
  383.    if (fp == NULL) return -1;
  384.    fscanf (fp, "%d %d", &X1, &X2);
  385.    fclose(fp);
  386.  
  387.    clock_t begin, end;
  388.    double time_spent;
  389.    begin = clock();
  390.    srand(time(NULL));
  391.  
  392.    Node* Root;
  393.    Initialization(Root);
  394.    Create_Tree(Root, X1);
  395.    cout << "Wysokosc drzewa dla X1 przed wykonaniem DSW: " << Calculate_Height(Root) << endl;
  396.    DSW(Root);
  397.    cout << "Wysokosc drzewa dla X1 po wykonaniu DSW: " << Calculate_Height(Root) << endl;
  398.    while (Root) Delete_Node(Root, Root->Key);
  399.    Create_Tree(Root, X2);
  400.    cout << "Wysokosc drzewa dla X2 przed wykonaniem DSW: " << Calculate_Height(Root) << endl;
  401.    DSW(Root);
  402.    cout << "Wysokosc drzewa dla X2 po wykonaniu DSW: " << Calculate_Height(Root) << endl;
  403.  
  404.    end = clock();
  405.    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  406.    cout << "Program wykonal sie w: " << time_spent << " sekund" << endl;
  407.    return 0;
  408. }
  409.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tFvxbt
language:
Text (text 6.10)
created:
10 years ago
visibility:
secret

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!