Advertisement
Guest User

Untitled

a guest
Aug 18th, 2019
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 9.52 KB | None | 0 0
  1. using System;
  2. using System.Collections;
  3. using System.Collections.Generic;
  4.  
  5. namespace _2_3_Tree_WORKING
  6. {
  7.     class Program
  8.     {
  9.         static void Main(string[] args)
  10.         {
  11.             TwoThreeTree<int> twoThree = new TwoThreeTree<int>();
  12.             twoThree.add(4);
  13.             twoThree.add(6);
  14.             twoThree.add(8);
  15.             twoThree.add(3);
  16.             twoThree.add(9);
  17.             twoThree.add(1);
  18.             twoThree.add(11);
  19.             Console.WriteLine(twoThree.Find(1));
  20.             Console.WriteLine();
  21.             Console.ReadLine();
  22.         }
  23.     }
  24.  
  25.     public class TwoThreeTree<Integer>
  26.     {
  27.  
  28.         private class Node<Integer>
  29.         {
  30.             internal List<Integer> Keys = new List<Integer>(); //pravimo listu kljuceva koji primaju T vrednost
  31.             internal List<Node<Integer>> Children = new List<Node<Integer>>(); //pravimo listu dece
  32.  
  33.             internal bool isLeaf() { return Children.Count == 0; } //proveravamo da li je leaf, ako je broj dece cvora 0 onda jeste
  34.             internal bool is4Node() { return Keys.Count == 3; }
  35.  
  36.             // novi Node je uvek degree-a 2 (1 vrednost sadrzi)
  37.             // moze biti leaf (zadnji) Node ili ima 2 Children-a
  38.             public Node(Integer x) // konstruktor nase klase Node u kome u listu kljuceva dodajemo prosledjenu vrednost
  39.             {
  40.                 Keys.Add(x);
  41.             }
  42.  
  43.             public Node(Integer x, Node<Integer> left, Node<Integer> right) //konstruktor koji pozivamo kada dolazi do splitovanja, novom root-u postavljamo levo i desno dete
  44.             {
  45.                 Keys.Add(x);
  46.                 Children.Add(left);
  47.                 Children.Add(right);
  48.                 //Children.Add(null); // hack
  49.             }
  50.  
  51.             internal bool add(Integer val) //rekurzivna funkcija za dodavanje vrednosti u stablo
  52.             {
  53.                 if (isLeaf()) // proveravamo da li je nas cvor Leaf ako jeste dodajemo vrednost
  54.                     return addToLeaf(val);
  55.                 else return addToInterior(val); //ako nije Leaf trazimo Leaf cvor gde cemo dodati
  56.             }
  57.  
  58.             // nove vrednosti uvek dodajemo u leaf Node.
  59.             internal bool addToLeaf(Integer x)
  60.             {
  61.                 int cmp;
  62.                 for (int i = 0; i < Keys.Count; i++)
  63.                 {
  64.                     cmp = Compare(Convert.ToInt32(x), Convert.ToInt32(Keys.ToArray()[i]));  //proveravamo koji broj je veci, zbog mesta insertovanja
  65.                     if (cmp == 0)
  66.                         return false;
  67.                     else if (cmp < 0) //ako je nas cmp (compare) manji od nula, znaci da je broj koji insertujemo manji od trenutnog i treba da se postavi na jedno mesto ispred njega
  68.                     {
  69.                         Keys.Insert(i, x);
  70.                         return true;
  71.                     }
  72.                 }
  73.                 Keys.Add(x); //ako je broj najveci u cvoru samo ga ubacimo u listu na sledece mesto
  74.                 return true;
  75.             }
  76.  
  77.             internal bool addToInterior(Integer x) //ovu metodu pozivamo da bi nasli mesto gde treba da insertujemo nasu vrednost (slucaj kada nas root ima decu)
  78.             {
  79.                 int cmp;
  80.                 for (int i = 0; i <= Keys.Count; i++)
  81.                 {
  82.                     if (i == Keys.Count)
  83.                         cmp = -1; // ovde ulazimo kada je broji koji se insertuje najveci u cvoru i treba da ide u desno dete
  84.                     else
  85.                         cmp = Compare(Convert.ToInt32(x), Convert.ToInt32(Keys.ToArray()[i]));
  86.                     if (cmp == 0)
  87.                         return false;
  88.                     else if (cmp < 0) //znaci da je nasa vrednost koju insertujemo manja od vrednosti u cvoru (idemo u levo dete)
  89.                     {
  90.                         bool retVal = Children.ToArray()[i].add(x); //dodajemo u dete naseg cvora
  91.                         if (Children.ToArray()[i].is4Node()) //proveravamo da li posle insertovanja broja dolazi do narusavanja strukture tj. da imamo 3 clana u cvoru
  92.                             childIs4Node(i); //ako dolazi do toga idemo ovde da odradimo splitovanje
  93.                         return retVal; //vracamo true jer smo uspesno dodali vrednost
  94.                     }
  95.                 }
  96.                 return false;
  97.             }
  98.  
  99.             internal void childIs4Node(int i)
  100.             {
  101.                 Node<Integer> the4Node = Children.ToArray()[i]; //pravimo novi cvor i dodajemo vrednosti dece i novog broja( znaci sva tri broja idu u ovaj cvor)
  102.                 if (i == 2) //ako je i==2 znaci da je to nase 3ce dete po redu gde treba da se doda
  103.                     Keys.Add(Children.ToArray()[i].Keys.ToArray()[1]); //srednji broj ide u cvor iznad
  104.                 else Keys.Insert(i, Children.ToArray()[i].Keys.ToArray()[1]); //srednji broj prebacujemo u cvor iznad (u roditelja)
  105.                 Node<Integer> newChild1, newChild2; //pravimo dva nova deteta
  106.                 if (Children.ToArray()[i].isLeaf()) //proveravamo da li je leaf cvor u koji treba da unesemo vrednost
  107.                 {
  108.                     newChild1 = new Node<Integer>(Children.ToArray()[i].Keys.ToArray()[0]); //levo dete uzima kljuc levo od srednjeg (manji broj)
  109.                     newChild2 = new Node<Integer>(Children.ToArray()[i].Keys.ToArray()[2]);//desno dete uzima kljuc desno od srednjeg (veci broj)
  110.                 }
  111.                 else
  112.                 {
  113.                     newChild1 = new Node<Integer>(Children.ToArray()[i].Keys.ToArray()[0],
  114.                                             Children.ToArray()[i].Children.ToArray()[0],
  115.                                             Children.ToArray()[i].Children.ToArray()[1]);
  116.                     newChild2 = new Node<Integer>(Children.ToArray()[i].Keys.ToArray()[2],
  117.                                             Children.ToArray()[i].Children.ToArray()[2],
  118.                                             Children.ToArray()[i].Children.ToArray()[3]);
  119.                 }
  120.                 Children.Remove(the4Node); //brisemo cvor koji smo splitovali i napravili da zaddovolji strukturu (cvor koji ima 3 kljuca)
  121.                 Children.Insert(i, newChild2); //dodajemo desno dete na mesto koje treba
  122.                 Children.Insert(i, newChild1); //dodajemo levo dete na mesto koje treba
  123.             }
  124.  
  125.             public int Compare(int a, int b)
  126.             {
  127.                 if (a > b)
  128.                     return 1;
  129.                 else if (a < b)
  130.                     return -1;
  131.                 else
  132.                     return 0;
  133.             }
  134.         }
  135.  
  136.  
  137.         Node<Integer> root;
  138.  
  139.         public TwoThreeTree()
  140.         {
  141.             root = null;
  142.         }
  143.  
  144.         // TwoThreeTree add metoda
  145.         public bool add(Integer val)
  146.         {
  147.             if (root == null) // ako je nas koren prazan pravimo novi
  148.             {
  149.                 root = new Node<Integer>(val); //ovde pravimo
  150.                 return true;
  151.             }
  152.             else //ako vec posedujemo neki clan u korenu
  153.             {
  154.                 bool isNew = root.add(val); //da li je novi koren proveravamo
  155.                 // if root is a 4-node, split it
  156.                 if (root.Keys.Count == 3) //posle svakog dodavanja proveravamo da li imamo 3 kljuca, ako imamo radimo splitovanje
  157.                 {
  158.                     Node<Integer> left, right; //pravimo levo i desno dete cvora
  159.                     if (root.isLeaf()) //proveravamo da li trenutni koren nema dece ako nema
  160.                     {
  161.                         left = new Node<Integer>(root.Keys.ToArray()[0]); //u levo dete ide najmanji broj od trenutna tri
  162.                         right = new Node<Integer>(root.Keys.ToArray()[2]);//u desno dete ide najveci broj od trenutna tri
  163.                     }
  164.                     else
  165.                     {
  166.                         left = new Node<Integer>(root.Keys.ToArray()[0],
  167.                                            root.Children.ToArray()[0],
  168.                                            root.Children.ToArray()[1]);// pravimo decu i dodajemo vrednosti
  169.                         right = new Node<Integer>(root.Keys.ToArray()[2],
  170.                                             root.Children.ToArray()[2],
  171.                                             root.Children.ToArray()[3]);
  172.                     }
  173.                     root = new Node<Integer>(root.Keys.ToArray()[1], left, right); //pravimo novi root koji ostaje sa sredisnjim brojem i setujemo mu levo i desno dete(cvorovi koje smo prethodno kreirali)
  174.                 }
  175.                 return isNew;
  176.             }
  177.         }
  178.  
  179.         //metoda za pretragu broja u 2-3 tree
  180.         public bool Find(int value)
  181.         {
  182.             Node<Integer> result = FindNode(root, value);
  183.             if (result != null)
  184.             {
  185.                 return true;
  186.             }
  187.             return false;
  188.         }
  189.  
  190.         private Node<Integer> FindNode(Node<Integer> current, int value)
  191.         {
  192.             Node<Integer> temp = current;
  193.  
  194.             int i = 0;
  195.  
  196.             while (i <= current.Keys.Count - 1 && value > Convert.ToInt32(current.Keys[i]))
  197.             {
  198.                 i++;
  199.             }
  200.  
  201.             if (i <= current.Keys.Count - 1 && value == Convert.ToInt32(current.Keys[i]))
  202.             {
  203.                 return current;
  204.             }
  205.             else if (current.isLeaf())
  206.             {
  207.                 return null;
  208.             }
  209.             else
  210.             {
  211.                 return FindNode(current.Children[i], value);
  212.             }
  213.         }
  214.     }
  215. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement