Rot-schwarz Baum Problem

[Terry12]

hi, was bedeuten die Methoden

if (isRed(node) && isRed(node.right) && !isRed)
und
if (isRed(node) && isRed(node.left) && isRed)

in unten aufgeführtem Quellcode für mein Baum?

/**Die Klasse RBTree repraesentiert den Rot-Schwarz Baum mit seinen Methoden.
 * 
 * 
 */
public class RBTree implements IRBTree<String> {
 
    public static final boolean RED = true;
    public static final boolean BLACK = false;
    public Node root;
 
    public String get(String key) throws NullPointerException {
        assert (key!=null): "Key darf nicht leer sein!";
        Node node = root;        
 
        while (node != null) {
            int cmp = ((String)key).compareTo((String)node.key);
                   if (cmp < 0) {
                node = node.left;
                System.out.println("Links: " +node.toString());
            } else if (cmp > 0) {
                node = node.right;
                System.out.println("Rechts: "+node.toString());
            } else if (cmp == 0) {
                return (String)node.key;
            }
        }
        return null;
    }
 
    public boolean isRed(Node node) {
        if (node == null){
            return false;
        }
        return node.color;
    }
 
    private Node rotateLeft(Node h) {
        if (h == null) return null;
        
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        return x;
    }
 
    private Node rotateRight(Node h) {
        if (h == null) return null;
        
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        return x;
    }
 
    public Node insert(Node node, String key, boolean isRed) {
 
        if (node == null) {
            return new Node(key, RED);
        }
 
        if (isRed(node.left) && isRed(node.right)) {
            node.color = RED;
            node.left.color = BLACK;
            node.right.color = BLACK;
        }
 
        int cmp = ((String)key).compareTo((String)node.key);
 
        if (cmp < 0) {
            node.left = insert(node.left, key,BLACK);
 
            if (isRed(node) && isRed(node.left) && isRed) {
                node = rotateRight(node);
            }
 
            if (isRed(node.left) && isRed(node.left.left)) {
                node = rotateRight(node);
                node.color = BLACK;
                node.right.color = RED;
            }
 
        } else {
            node.right = insert(node.right, key,  RED);
 
            if (isRed(node) && isRed(node.right) && !isRed) {
                node = rotateLeft(node);
            }
 
            if (isRed(node.right) && isRed(node.right.right)) {
                node = rotateLeft(node);
                node.color = BLACK;
                node.left.color = RED;
            }
        }
        return node;
    }
 
    public void insert(String key) {
        this.root = insert(this.root, key,  BLACK);
        this.root.color = BLACK;
    }
    
    public Node getRoot()
    {
        return root;
    }
    
    /*public void traverseInOrder(Node root)
    {            
        String temp;
        StringBuffer sb= new StringBuffer("-->");
        
        if (root.left !=null){
            traverseInOrder(root.left);
            sb.append(root.toString());
            sb.toString();
            System.out.println(sb);
        }
        if  (root.right !=null)  {
            traverseInOrder(root.right);            
        }     
        
    }*/
    
    public void traverseInOrder(Node root)
    {    
        //Node node = root;
        String temp;
        StringBuffer s= new StringBuffer();
        
        if (root !=null){
            traverseInOrder(root.left);
            temp = ((String)root.toString());
            s.append(temp).append("-->");
            traverseInOrder(root.right);  
            System.out.println(s);
        } 
    }
            
    public String toString(Node n)
    {
        StringBuffer sb = new StringBuffer();
        sb.append("Wurzel: " + this.getRoot()+ "Knoten: " +n.toString());
        return sb.toString();
    }
    
}

und warum fügt er bei cmp<0 bei insert einen schwarzen Knoten ein?

        if (cmp < 0) {
            node.left = insert(node.left, key,BLACK);

 

[Paddelpirat]

Stell doch mal bitte Vermutungen an, was die Zeilen deiner Meinung nach bedeuten könnten.

 

[Terry12]

naja ich denke mal die beiden oberen Methoden behandeln ein paar Fälle bezueglich neu Anordnung des Baums, aber da gibt es doch eigentlich 5 Fälle die zu unterscheiden sind oder?
und warum man unten beim einfügen einen schwarzen einfügt , wenn cmp<0 versteh ich auch nicht...

 

[Paddelpirat]

Dann geh die Fälle doch einfach mal per Definition durch und schau nach, ob es funktioniert oder nicht.