Autor Wątek: Drzewa Czerwono Czarne  (Przeczytany 1988 razy)

Offline dazz007

  • Użytkownik

# Styczeń 04, 2011, 14:07:35
Witam. Mam do napisania program obsługujący drzewa czerwono czarne. Niestety zaciąłem się już przy wstawianiu poszczególnych elementów do drzewa. Stworzyłem klase Node oraz klasę Tree. I moim pomysłem było, aby wstawiać te obiekty Node do drzewa poprzez dodawanie tak jakby "wskaźników" do korzenia.  Czyli dodajemy pierwszy el. Jest on root'em, następnie dodajemy kolejny i jest on teraz np. root.left. Teraz x = root.left i np. dodając znów do lewego poddrzewa el. będzie rozpoznawalny jako x.left (lub x.right) itd. Niestety nie wiem czy java pozwala na takie zagrywki, nie korzystając z żadnych List czy tablic. Czy te nowe węzły będą jakoś w pamięci. Niestety w moim początkowym kodzie chcę wstawić 10 elementów, ale mogę tylko 1. Przy kolejnej pętli program się zawiesza. Ale zdaje mi się, że to wina początkowych wartości root'a oraz nil'a ale nie mam już pomysły jak początkowo powinny one wyglądać. Oto kod:

import java.util.*;

enum Color {BLACK,RED}

class Node
{
public int key = 0;
public Color color = Color.RED;
public Node left = null;
public Node right = null;
public Node parent = null;

}

class Tree
{
public Node root = new Node();
public Node nil = new Node();

public void TreeInsert(Node z)
{
Node y = new Node();
Node x = new Node();
System.out.println("co sie tu dzieje: ");
y = nil;
System.out.println("co sie tudada: ");
x = root;
System.out.println("co sie tudada: ");
while(!x.equals(nil));
{
y = x;
System.out.println("ejeje");
if(z.key < x.key)
x = x.left;
else
x = x.right;
}

z.parent = y;
System.out.println("edae");
if(y.equals(nil)){
System.out.println("edddae");
root = z;
System.out.println("root.key: "+root.key);
}
else if(z.key < y.key)
{
System.out.println("eeee");
y.left = z;
System.out.println("eddddaqqqe");
}
else
y.right = z;
System.out.println("edddadwqdwqe");
}
}

public class RedBlackTree
{
public static int []arr = {23,45,32,15,67,21,5,23,78,13};
public static Tree T = new Tree();
public static void main(String[] args)
{
T.root = null;
T.root = T.nil;
for(int i = 0; i < 10; i++)
{
Node z = new Node();
z.key = arr[i];
T.TreeInsert(z);
System.out.println("wtf");
}
}
}

te printy są do sprawdzenia czy w ogóle chociaż raz pętla w mainie się wykonuje. I tak też jest, niestety przy następnej iteracji zawiesza się przy pierwszym while w TreeInsert. Proszę o pomoc.

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline owyn

  • Użytkownik

# Styczeń 04, 2011, 14:30:17
A po co w ogóle tworzysz jakiegoś 'nila' zamiast używać wbudowaną w język wartość null? Po przejrzeniu tego kodu odnoszę wrażenie, że nie rozumiesz jak działają referencje i tworzenie obiektów w Javie. Np. tu:
Node y = new Node();
Node x = new Node();
System.out.println("co sie tu dzieje: ");
y = nil;
System.out.println("co sie tudada: ");
x = root;
tworzysz 2 nowe obiekty tylko po to, by linijkę później je usunąć. Radzę douczyć się Javy, bo bez zrozumienia tego nie masz szans żeby napisać jakikolwiek algorytm obsługujący drzewa.

Offline dazz007

  • Użytkownik

# Styczeń 04, 2011, 16:11:42
No faktycznie, dodatkowa lektura była niezbędna. Ze względu na pośpiech przeskoczyłem dużo podręcznika javy i nie niestety to się nie opłaciło. Teraz już wiem, że takie przypisanie obiektów sprawia, że zaczynają wskazywać na ten sam obiekt a ten "nadpisany" się usuwa. Czyli w tym wypadku muszę jakoś porozumiewać się między polami. Chyba, że macie jakieś lepsze propozycję?

Offline msieradzki

  • Użytkownik

# Styczeń 06, 2011, 00:08:48
http://www.eecs.usma.edu/webs/people/okasaki/jfp99.ps Okasaki red black trees. Opisane jedynie wstawianie i to funkcyjnie, więc musisz umieć to czytać. Korzyścią jest to, że bardzo skomplikowana procedura wygląda po ludzku. Usuwanie widziałem gdzie indziej, nie jest tak piękne jak wstawianie. To tak tylko jako pomoc naukowa. ;)

Napisz sobie Node::validate() i uruchamiaj to przed/po każdą operacją. Sprawdź w niej wszystkie niezmienniki RB-drzewa.

Offline dazz007

  • Użytkownik

# Styczeń 06, 2011, 20:07:35
Już sobie poradziłem:) Działa chyba prawidłowo:) Mam teraz problem z grafiką. Chciałem na początek aby metodą Inorder wybijało mi słupki tak po sekundzie każdy. Niestety wybija mi dopiero wtedy kiedy Inorder przejdzie po wszystkich węzłach. W konsoli normalnie wybija po sekudzie wartości węzłów a słupki dopiero tak jak mówiłem, po przejściu całego Inorder. I co dziwne kiedy już po wszystkim przejdzie Inorder zaczyna wszystko od początku.. nie chce przestać. Nie wiem w czym tkwi problem. Proszę o pomoc. To jest częściowy kod:

public class Tree extends JComponent{
public int yeah = 0;
        public int Weight = 400;
        public int Hight = 200;

(....);

        Tree(){
                        this.setPreferredSize(new Dimension(Weight, Hight));
                 }
        private void InorderTreeWalk(Node z, Graphics p) {
                try
                    {
                        if(z != nil) {
                                InorderTreeWalk(z.left,p);
                       
                                if(z.color == COLOR.BLACK)
                                {
                                    System.out.println(z.key+"  czarny");
                                p.setColor(Color.BLACK);
                                p.fillRect(yeah, 0,5, 3*z.key.hashCode());
                                yeah=yeah+6;
                                }
                                 else {
                                                    System.out.println(z.key+" czerwony");
                                                p.setColor(Color.RED);
                                                p.fillRect(yeah, 0,5, 3*z.key.hashCode());
                                                yeah=yeah+6;
                                 }
                               
                            InorderTreeWalk(z.right,p);
                }
                Thread.sleep(1000);
                    }
                    catch(Exception e){       
                    }
       
        }
        public void paint(Graphics p){
                InorderTreeWalk(root,p);
        }
}
//---------------------------------------------------------------------------
public class Main extends JFrame{
        public static void main (String args[]) {               
               
                Main window = new Main();
                window.setVisible(true);
                System.out.println("usunalem element 41");
               
        }
        Main(){
                JPanel content = new JPanel();
                setLayout(new GridLayout(1,1));
        content.setLayout(new GridLayout(1,1));
       
        Tree drawing = new Tree();
       
        drawing.insert(41);
        drawing.insert(23);
        drawing.insert(31);
        drawing.insert(12);
        drawing.insert(19);
        drawing.insert(8);
   
        content.add(drawing);
        this.setContentPane(content);
        this.setTitle("yayyaya");
        this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        this.pack();
        this.setLocationRelativeTo(null);

        }
}