Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections;
- using System.Collections.Generic;
- namespace _2_3_Tree_WORKING
- {
- class Program
- {
- static void Main(string[] args)
- {
- TwoThreeTree<int> twoThree = new TwoThreeTree<int>();
- twoThree.add(4);
- twoThree.add(6);
- twoThree.add(8);
- twoThree.add(3);
- twoThree.add(9);
- twoThree.add(1);
- twoThree.add(11);
- Console.WriteLine(twoThree.Find(1));
- Console.WriteLine();
- Console.ReadLine();
- }
- }
- public class TwoThreeTree<Integer>
- {
- private class Node<Integer>
- {
- internal List<Integer> Keys = new List<Integer>(); //pravimo listu kljuceva koji primaju T vrednost
- internal List<Node<Integer>> Children = new List<Node<Integer>>(); //pravimo listu dece
- internal bool isLeaf() { return Children.Count == 0; } //proveravamo da li je leaf, ako je broj dece cvora 0 onda jeste
- internal bool is4Node() { return Keys.Count == 3; }
- // novi Node je uvek degree-a 2 (1 vrednost sadrzi)
- // moze biti leaf (zadnji) Node ili ima 2 Children-a
- public Node(Integer x) // konstruktor nase klase Node u kome u listu kljuceva dodajemo prosledjenu vrednost
- {
- Keys.Add(x);
- }
- 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
- {
- Keys.Add(x);
- Children.Add(left);
- Children.Add(right);
- //Children.Add(null); // hack
- }
- internal bool add(Integer val) //rekurzivna funkcija za dodavanje vrednosti u stablo
- {
- if (isLeaf()) // proveravamo da li je nas cvor Leaf ako jeste dodajemo vrednost
- return addToLeaf(val);
- else return addToInterior(val); //ako nije Leaf trazimo Leaf cvor gde cemo dodati
- }
- // nove vrednosti uvek dodajemo u leaf Node.
- internal bool addToLeaf(Integer x)
- {
- int cmp;
- for (int i = 0; i < Keys.Count; i++)
- {
- cmp = Compare(Convert.ToInt32(x), Convert.ToInt32(Keys.ToArray()[i])); //proveravamo koji broj je veci, zbog mesta insertovanja
- if (cmp == 0)
- return false;
- 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
- {
- Keys.Insert(i, x);
- return true;
- }
- }
- Keys.Add(x); //ako je broj najveci u cvoru samo ga ubacimo u listu na sledece mesto
- return true;
- }
- internal bool addToInterior(Integer x) //ovu metodu pozivamo da bi nasli mesto gde treba da insertujemo nasu vrednost (slucaj kada nas root ima decu)
- {
- int cmp;
- for (int i = 0; i <= Keys.Count; i++)
- {
- if (i == Keys.Count)
- cmp = -1; // ovde ulazimo kada je broji koji se insertuje najveci u cvoru i treba da ide u desno dete
- else
- cmp = Compare(Convert.ToInt32(x), Convert.ToInt32(Keys.ToArray()[i]));
- if (cmp == 0)
- return false;
- else if (cmp < 0) //znaci da je nasa vrednost koju insertujemo manja od vrednosti u cvoru (idemo u levo dete)
- {
- bool retVal = Children.ToArray()[i].add(x); //dodajemo u dete naseg cvora
- if (Children.ToArray()[i].is4Node()) //proveravamo da li posle insertovanja broja dolazi do narusavanja strukture tj. da imamo 3 clana u cvoru
- childIs4Node(i); //ako dolazi do toga idemo ovde da odradimo splitovanje
- return retVal; //vracamo true jer smo uspesno dodali vrednost
- }
- }
- return false;
- }
- internal void childIs4Node(int i)
- {
- Node<Integer> the4Node = Children.ToArray()[i]; //pravimo novi cvor i dodajemo vrednosti dece i novog broja( znaci sva tri broja idu u ovaj cvor)
- if (i == 2) //ako je i==2 znaci da je to nase 3ce dete po redu gde treba da se doda
- Keys.Add(Children.ToArray()[i].Keys.ToArray()[1]); //srednji broj ide u cvor iznad
- else Keys.Insert(i, Children.ToArray()[i].Keys.ToArray()[1]); //srednji broj prebacujemo u cvor iznad (u roditelja)
- Node<Integer> newChild1, newChild2; //pravimo dva nova deteta
- if (Children.ToArray()[i].isLeaf()) //proveravamo da li je leaf cvor u koji treba da unesemo vrednost
- {
- newChild1 = new Node<Integer>(Children.ToArray()[i].Keys.ToArray()[0]); //levo dete uzima kljuc levo od srednjeg (manji broj)
- newChild2 = new Node<Integer>(Children.ToArray()[i].Keys.ToArray()[2]);//desno dete uzima kljuc desno od srednjeg (veci broj)
- }
- else
- {
- newChild1 = new Node<Integer>(Children.ToArray()[i].Keys.ToArray()[0],
- Children.ToArray()[i].Children.ToArray()[0],
- Children.ToArray()[i].Children.ToArray()[1]);
- newChild2 = new Node<Integer>(Children.ToArray()[i].Keys.ToArray()[2],
- Children.ToArray()[i].Children.ToArray()[2],
- Children.ToArray()[i].Children.ToArray()[3]);
- }
- Children.Remove(the4Node); //brisemo cvor koji smo splitovali i napravili da zaddovolji strukturu (cvor koji ima 3 kljuca)
- Children.Insert(i, newChild2); //dodajemo desno dete na mesto koje treba
- Children.Insert(i, newChild1); //dodajemo levo dete na mesto koje treba
- }
- public int Compare(int a, int b)
- {
- if (a > b)
- return 1;
- else if (a < b)
- return -1;
- else
- return 0;
- }
- }
- Node<Integer> root;
- public TwoThreeTree()
- {
- root = null;
- }
- // TwoThreeTree add metoda
- public bool add(Integer val)
- {
- if (root == null) // ako je nas koren prazan pravimo novi
- {
- root = new Node<Integer>(val); //ovde pravimo
- return true;
- }
- else //ako vec posedujemo neki clan u korenu
- {
- bool isNew = root.add(val); //da li je novi koren proveravamo
- // if root is a 4-node, split it
- if (root.Keys.Count == 3) //posle svakog dodavanja proveravamo da li imamo 3 kljuca, ako imamo radimo splitovanje
- {
- Node<Integer> left, right; //pravimo levo i desno dete cvora
- if (root.isLeaf()) //proveravamo da li trenutni koren nema dece ako nema
- {
- left = new Node<Integer>(root.Keys.ToArray()[0]); //u levo dete ide najmanji broj od trenutna tri
- right = new Node<Integer>(root.Keys.ToArray()[2]);//u desno dete ide najveci broj od trenutna tri
- }
- else
- {
- left = new Node<Integer>(root.Keys.ToArray()[0],
- root.Children.ToArray()[0],
- root.Children.ToArray()[1]);// pravimo decu i dodajemo vrednosti
- right = new Node<Integer>(root.Keys.ToArray()[2],
- root.Children.ToArray()[2],
- root.Children.ToArray()[3]);
- }
- 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)
- }
- return isNew;
- }
- }
- //metoda za pretragu broja u 2-3 tree
- public bool Find(int value)
- {
- Node<Integer> result = FindNode(root, value);
- if (result != null)
- {
- return true;
- }
- return false;
- }
- private Node<Integer> FindNode(Node<Integer> current, int value)
- {
- Node<Integer> temp = current;
- int i = 0;
- while (i <= current.Keys.Count - 1 && value > Convert.ToInt32(current.Keys[i]))
- {
- i++;
- }
- if (i <= current.Keys.Count - 1 && value == Convert.ToInt32(current.Keys[i]))
- {
- return current;
- }
- else if (current.isLeaf())
- {
- return null;
- }
- else
- {
- return FindNode(current.Children[i], value);
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement