Venus AUEB Forum

Code: Select all

class bst<Item extends Comparable> {
	private class Node{
		Node left;
		Node right;
		Item item;
		private Node(Item item) {
			this.item=item;
		}
	}
	Node root;
	public void insert(Item item) {
		root=insert(root,item);
	}
	public void insert(Item[] items) {
		for (int i=0; i<items.length; i++) 
			insert(items[i]);
		
	}
	private Node insert(Node x,Item item) {
		if (x==null)
			return new Node(item);
		else if(item.compareTo(x.item)<0) 
			x.left = insert(x.left,item);
		else
			x.right = insert(x.right,item);
		return x;
	}
	public Node protL(Node h) { //aristeri peristrofi
		Node x=h.right;
		h.right=x.left;
		x.left=h;
		return x;
	}
	public Node protR(Node h) { //dexia peristrofi
		Node x=h.left;
		h.left=x.right;
		x.right=h;
		return x;
	}
	public static void main(String args[]) {
		bst<Character> searchtree=new bst<Character>(); 
		Character[] chars={'A','S','E','R','C','H','I','N','G','X','M','P','L'};
		searchtree.insert(chars);
		//dokimes
		System.out.println(searchtree.root.item);
		System.out.println(searchtree.root.right.item);
		System.out.println(searchtree.root.right.left.item);
		System.out.println(searchtree.root.right.left.right.item);
		searchtree.rotR(searchtree.root.right);
		System.out.println("After Right Rotation");
		System.out.println(searchtree.root.item);
		System.out.println(searchtree.root.right.item);
		System.out.println(searchtree.root.right.left.item);
		System.out.println(searchtree.root.right.left.left.item);	
	}			
}

Code: Select all

void rotate( node c ) {

    node p = c.parent;		// parent of c
    node gp = p.parent;		// grandparent of c (might be null)

    // Update the lower edge which switches sides

    if (c == p.left) {
      p.left = c.right;
      if (p.left != null)
	p.left.parent = p;
      c.right = p;
      p.parent = c;
    } else {
      p.right = c.left;
      if (p.right != null)
	p.right.parent = p;
      c.left = p;
      p.parent = c;
    }

    // Update the upper edge which switches sides

    if (gp == null)
      root = c;
    else if (p == gp.left)
      gp.left = c;
    else
      gp.right = c;
    
    c.parent = gp;
  }
}

Code: Select all

    B
  /   \
 A     C

Code: Select all

                     20   
                  /       \
               15          26
              /   \       /    \
            4      17    23     30