Der Bruderbaum

Definition:

Ein Bruderbaum ist ein Baum, bei dem jeder innere Knoten entweder zwei Kinder hat, oder er hat nur ein Kind und einen Bruder, der zwei Kinder hat.
Alle Blätter liegen auf einer Höhe, sie enthalten die Daten. In einem Knoten steht immer das höchste Element des linken Teilbaumes des Knotens.

Implementierung:

download

  /*
 * Created on 30-Nov-2003
 *
 */

/**
 * @author Lina Ourima
 *	ich übernehme keine garantie für die korrektheit dieser 
 * 	implementierung, ich habe aber mein bestes versucht
 */
public class BrotherTree {
	Node root;

	public static void main(String[] args) {
		BrotherTree b = new BrotherTree();
		for(int i = 0; i < 6; i++){
			b.insert(i);
			boolean bool = b.isBrotherTree();
			System.out.println("Bruderbaum? "+bool);
			if(!bool) return;
		}
		for(int i = 0; i < 6; i++){
			System.out.print(i+" löschen... ");
			boolean bool = b.delete(i);
			System.out.println(bool);
			if(!bool) return;
			b.print();
			b.printLeaves();
			bool = b.isBrotherTree();
			System.out.println("Bruderbaum? "+bool);
			if(!bool) return;
		}
	}

	int height = -1;	
	
	boolean isBrotherTree()
	{
		height = -1;
		return hasSameHeight(root, 0) && isBrotherTree(root);
	}

	
	boolean hasSameHeight(Node n, int h){
		boolean b = true;
		if(n == null) return true;
		if(n.left== null && n.right == null){
			if(height == -1){
				height = h;
			}
			if(height != h){
				System.out.println("Blatt["+n.nr+":"+n.number+"] auf Höhe "+h+" sollte Höhe "+height+" sein!");
				return false;
			}
			return true;
		}
		if(n.left!= null){
			b = hasSameHeight(n.left, h+1);
		}
		if(n.right!= null){
			b = b && hasSameHeight(n.right, h+1);
		}
		return b;
	}
	
	boolean isBrotherTree(Node n)
	{
		if(n == null) return true;
		if(n.left == null && n.right == null) return true;
		if(n.left == null) { //wurzel hat nur ein kind
			System.out.println("Linkes Kind von "+n.nr+":"+n.number+"ist null");
			return false;
		}
		if(n.right == null) {//wurzel hat nur ein kind
			System.out.println("Wurzel "+n.nr+":"+n.number+" hat nur ein Kind");
			return false;
		} 
		int gc = 0;
		if(n.right.left != null) gc++; 
		if(n.right.right != null) gc++;
		if(n.left.left != null) gc++; 
		if(n.left.right != null) gc++;
		if(gc > 2 || gc == 0) {
			if(n.right.right == null){
				return isBrotherTree(n.right.left) && isBrotherTree(n.left);
			}
			if(n.left.right == null){
				return isBrotherTree(n.right) && isBrotherTree(n.left.left);
			}
			return isBrotherTree(n.right) && isBrotherTree(n.left);
		} else {
			System.out.println("Knoten "+n.nr+":"+n.number+" hat nur "+gc+" Enkel");
			return false;
		}
	}

	void printLeaves()
	{
		System.out.println("***Print Leaves***");
		printLeaves(root);
		System.out.println();	
	}
	
	void printLeaves(Node n)
		{
			if(n == null){
				System.out.print("null");
				return;
			}
			if(n.left != null){
				printLeaves(n.left);
			}
			if(n.left == null && n.right == null){
				System.out.print("["+n.number+"]");
				return;
			}
			if(n.right != null){
				printLeaves(n.right);
			}
		}
	
	String[] s = new String[20]; 
	
	void print()
	{
		System.out.println("***Print Tree***");
		for(int i = 0; i < 20; i++){
			s[i] = "";
		}
		print(root, 0);
		for(int i = 0; i < 20; i++){
			if(s[i]!=""){
				System.out.println(s[i]);
			}
		}
		System.out.println();	
	}
	
	
	void print(Node n, int h)
	{
		//Inorder
		if(n == null){
			s[h] += "Null";
			return;
		}
		
		if(n.left != null){
			print(n.left, h+1);
		}
		s[h] += n.toString();
		if(n.right != null){
			print(n.right, h+1);
		}
	}
	
	boolean insert(int x){
		System.out.println(x+" einfügen");
		if(root == null){
			root = new Node(x);
			System.out.println("neue Wurzel");
			print();
			return true;
		}
		Node neighbar = findNeighbar(root, x);
		if(neighbar == null) {
			System.out.println("War schon vorhanden");
			print();
			return false;
		} //Knoten schon vorhanden
		Node n = new Node(x);
		insert(neighbar, n);
		changeLabels(n);
		print();
		return true;
	}
	
	Node find(Node n, int x){
		if(n == null){
			return null;
		}
		if(n.left == null && n.right == null){
			if(n.number == x){
				return n;
			} else {
				System.out.println(x+" nicht gefunden, fand stattdessen "+n.number);
				return null;
			}
		}
		if(n.right == null || x <= n.number){
			return find(n.left, x);
		}
		if(x > n.number){
			return find(n.right, x);
		}
		return null; // dahin dürfen wir im korrekten bruderbaum nicht kommen
	}
	
	boolean delete(int k){
		Node n = find(root, k);
		if(n == null){
			System.out.println("Knoten nicht gefunden!");
			return false;
		}
		delete(n);
		return true;
	}
	
	Node getBrother(Node n){
		if(n.parent == null) return null;
		if(n.parent.left == n) return n.parent.right;
		return n.parent.left;
	}
	
	void delete(Node n){
		System.out.println("delete:: "+n);
		//print();
		if(n.parent == null){ // n wurzel
			root = null;
			return;
		}
		Node daddy = n.parent;
		Node brother = getBrother(n);
		if(daddy.parent == null){ // wurzel, ein kind wird gelöscht, baum verliert höhe
			//bruder muss existieren (wurzel immer zwei kinder)
			root = brother;
			brother.parent = null;
			brother.computeMax();
			System.out.println("wurzel, ein kind wird gelöscht, baum verliert höhe wurzel: "+root);
			return;
		}
		Node opa = daddy.parent;
		if(daddy.right == null){ //vater hatte nur ein kind
			System.out.println("vater hatte nur ein kind, delete "+daddy);
			delete(daddy);
			return;
		} 
		daddy.deleteChild(n);
		if(daddy.left == null){
			//fehler....
			System.out.println("daddy.left == null daddy: "+daddy.nr+":"+daddy.number);
		}
		Node uncle = getBrother(daddy);
		if(uncle == null){ //kein onkel
			Node urOpa = opa.parent; 
			System.out.println("kein Onkel ");
			//jetzt muss vater onkel mit zwei kindern haben
			Node daddysUncle = getBrother(opa);
			if(urOpa.right == opa){ //opa hat linken bruder
				System.out.println("opa hat linken bruder");
				Node willbeDeleted = daddysUncle.right;
				opa.setRightChild(daddy);
				opa.setLeftChild(daddysUncle.right);
				if(opa.right.right == null && opa.left.right == null){ // opa hat nur zwei enkel
					System.out.println("verschmelzen");
					opa.left.setRightChild(opa.right.left);
					opa.right = null;
				}
				willbeDeleted.parent = daddysUncle;
				delete(willbeDeleted);
				return;
			}else { //der bruder vom opa steht rechts
				//opas linkes kind ist schon der daddy
				System.out.println("opa hat rechten bruder");
				Node willbeDeleted = daddysUncle.left;
				opa.setRightChild(daddysUncle.left);
				if(opa.right.right == null && opa.left.right == null){ // opa hat nur zwei enkel
					System.out.println("verschmelzen");
					opa.left.setRightChild(opa.right.left);
					opa.right = null;
				}
				willbeDeleted.parent = daddysUncle;
				delete(willbeDeleted);
				return;
			}
		}
		if(uncle.right != null){ // Onkel hat 2 Kinder
			System.out.println("Onkel hat 2 Kinder");
			changeLabels(opa);
			return;
		}
		//Onkel hat nur ein Kind, verschmelzen
		System.out.println("Onkel hat nur ein Kind, verschmelzen");
		if(opa.left == daddy){
			daddy.setRightChild(uncle.left);
			delete(uncle);
		} else {
			uncle.setRightChild(daddy.left);
			delete(daddy);
		}
		return;
	}
	
	void insert(Node neighbar, Node x){
		if(neighbar.parent == null){//neighbar ist wurzel
			if(x.number < neighbar.number){
				root = new Node(x, neighbar);
			} else {
				root = new Node(neighbar, x);
			}
			return;
		}
		Node daddy = neighbar.parent;
		if(daddy.right == null){ //vater hat nur ein kind
			x.parent = daddy;
			if(neighbar.number < x.number){
				daddy.right = x;
				daddy.max = x.max;
			}
			if(neighbar.number > x.number){
				daddy.right = neighbar;
				daddy.max = neighbar.max;
				daddy.left = x;
				daddy.number = x.max;
			}
			return;
			//kann nicht gleich sein
		}
		 // Vater hat zwei Kinder 
			Node one, two, three;
			if(x.number < daddy.left.number) {
				one = x;
				two = daddy.left;
				three = daddy.right;
			} else
			if(x.number > daddy.right.number){
				one = daddy.left;				
				two = daddy.right;
				three = x;
			} else {
				one = daddy.left;
				two = x;
				three = daddy.right;
			}
			if(daddy.parent == null){ //Vater Wurzel
				System.out.println("Vater Wurzel");
				daddy.setLeftChild(one);
				daddy.setRightChild(two);
				three.parent = new Node(three);
				root = new Node(daddy, three.parent);
				return;
			} 
			Node opa = daddy.parent;
			if(opa.right == null){ //Vater hat keinen Bruder
				one.parent = new Node(one);
				one.parent.parent = daddy.parent;
				daddy.setLeftChild(two);
				daddy.setRightChild(three);
				opa.setLeftChild(one.parent);
				opa.setRightChild(daddy);
				return;
			} 
			// Vater hat Bruder
			Node uncle = getBrother(daddy);
				Node orphant;
				if(opa.right == uncle) {
					orphant = three;
					daddy.setLeftChild(one);
					daddy.setRightChild(two);
				} //Vater hat rechten Bruder
				else {
					orphant = one;
					daddy.setLeftChild(two);
					daddy.setRightChild(three);
				} 
				//Vater hat Bruder
				if(uncle.right == null){ //Bruder vom Vater hat nur ein Kind
					uncle.addChild(orphant);
					return;
				} else {//Bruder vom Vater hat zwei Kinder
					orphant.parent = new Node(orphant);
					System.out.println("Bruder vom Vater hat zwei Kinder");
					System.out.println("daddy.left "+daddy.left+"daddy.right "+daddy.right
					+"uncle.left "+uncle.left+"uncle.right "+uncle.right
					+"orphant "+orphant+"orphant.parent "+orphant.parent);
					insert(daddy, orphant.parent);
					return;
				}
	}
	

	void changeLabels(Node n){
		if(n != null && n.parent!=null){
			if(n.parent.right!=null){
				n.parent.max = n.parent.right.max;
			} else {
				/*System.out.println(n);
				System.out.println(n.parent);
				System.out.println(n.parent.max);
				System.out.println(n.parent.left);*/
				n.parent.max = n.parent.left.max;
			}
			n.parent.number = n.parent.left.max;
			changeLabels(n.parent);
		}
	}

	Node findNeighbar(Node n, int x){
		if(n.number == x){
			return null;
		}
		if(n.left == null){
			System.out.println("Nachbar von "+x+" ist "+n);
			return n;
		}
		if(n.right == null || x < n.number){
			return findNeighbar(n.left, x);
		}
		if(x > n.number){
			return findNeighbar(n.right, x);
		}
		return null;
	}

	static int numNode = 0;
	class Node{
		int number;
		int max; //gröstes element in seinem teilbaum
		Node left, right, parent;
		int nr;
		
		void computeMax(){
			if(left == null){
				return;
			}
			number = left.max;
			if(right == null){
				max = left.max;
				return;
			}
			max = right.max;
			
		}
		
		void setLeftChild(Node n){
			left = n;
			if(left != null){
				n.parent = this;
				number = n.max;
			} else {
				if(right != null){
					left = right;
					number = left.max;
					max = left.max;
					right = null;
				} else {
					max = number;
				}
			}
		}
		
		void setRightChild(Node n){
			right = n;
			if(right != null){
				n.parent = this;
				max = n.max;
			} else {
				if(left != null){
					max = left.max;
				} else {
					max = number;
				}
			}
		}
		void addChild(Node n){
			if(left.number < n.number){
				setRightChild(n);
			} else {
				setRightChild(left);
				setLeftChild(n);
			}
		}
		
		void deleteChild(Node n){
			if(left == n){
				setLeftChild(right);
				right = null;
				number = left.max;
				max = left.max;
			} 
			if(right == n){
				right = null;
				number = left.max;
				max = left.max;
			} 
		}
		
		public String toString(){
			if(left == null && right == null){
				if(parent != null){
					return "["+parent.nr+"<-"+nr+":"+number+"]";
				}
				if(parent != null){
					return "[*null<-"+nr+":"+number+"*]";
				}
			}
			String s =  "";
			if(parent == null){
				s += "(*";
				if(left!=null)s +=  left.nr+":"+left.number+" ";
				s += "."+nr+":"+number+".";
				if(right!=null) s += " "+right.nr+":"+right.number;
				s += "*)";
			} else {
				s += "("+parent.nr+"<-  ";
				if(left!=null) s += left.nr+":"+left.number+" ";
				s += "."+nr+":"+number+".";
				if(right!=null) s += " "+right.nr+":"+right.number;
				s += ")";
			}
			return s;
		}
		
		
		Node(int i){
			number = i;
			max = i;
			nr = numNode;
			numNode++;
		
		}
		
		Node(Node l){
			number = l.max;
			max = l.max;
			left = l;
			left.parent = this;
			nr = numNode;
			numNode++;
		}
		
		Node(Node l, Node r){
			number = l.max;
			max = r.max;
			left = l;
			right = r;
			left.parent = this;
			right.parent = this;
			nr = numNode;
			numNode++;
		}
	}
}

/*
0 einf³gen
neue Wurzel
***Print Tree***
(*.0:0.*)

Bruderbaum? true
1 einf³gen
Nachbar von 1 ist (*.0:0.*)
***Print Tree***
(*0:0 .2:0. 1:1*)
[2<-0:0][2<-1:1]

Bruderbaum? true
2 einf³gen
Nachbar von 2 ist [2<-1:1]
Vater Wurzel
***Print Tree***
(*2:0 .5:1. 4:2*)
(5<-  0:0 .2:0. 1:1)(5<-  3:2 .4:2.)
[2<-0:0][2<-1:1][4<-3:2]

Bruderbaum? true
3 einf³gen
Nachbar von 3 ist [4<-3:2]
***Print Tree***
(*2:0 .5:1. 4:2*)
(5<-  0:0 .2:0. 1:1)(5<-  3:2 .4:2. 6:3)
[2<-0:0][2<-1:1][4<-3:2][4<-6:3]

Bruderbaum? true
4 einf³gen
Nachbar von 4 ist [4<-6:3]
Bruder vom Vater hat zwei Kinder
daddy.left [4<-6:3]daddy.right [4<-7:4]uncle.left [2<-0:0]uncle.right [2<-1:1]
phant [8<-3:2]orphant.parent (*3:2 .8:2.*)
Vater Wurzel
***Print Tree***
(*5:1 .10:2. 9:4*)
(10<-  2:0 .5:1. 8:2)(10<-  4:3 .9:4.)
(5<-  0:0 .2:0. 1:1)(5<-  3:2 .8:2.)(9<-  6:3 .4:3. 7:4)
[2<-0:0][2<-1:1][8<-3:2][4<-6:3][4<-7:4]

Bruderbaum? true
5 einf³gen
Nachbar von 5 ist [4<-7:4]
***Print Tree***
(*5:1 .10:2. 9:3*)
(10<-  2:0 .5:1. 8:2)(10<-  12:3 .9:3. 4:4)
(5<-  0:0 .2:0. 1:1)(5<-  3:2 .8:2.)(9<-  6:3 .12:3.)(9<-  7:4 .4:4. 11:5)
[2<-0:0][2<-1:1][8<-3:2][12<-6:3][4<-7:4][4<-11:5]

Bruderbaum? true
0 l÷schen... delete:: [2<-0:0]
Onkel hat nur ein Kind, verschmelzen
delete:: (5<-  3:2 .8:2.)
Onkel hat 2 Kinder
true
***Print Tree***
(*5:2 .10:2. 9:3*)
(10<-  2:1 .5:2.)(10<-  12:3 .9:3. 4:4)
(5<-  1:1 .2:1. 3:2)(9<-  6:3 .12:3.)(9<-  7:4 .4:4. 11:5)
[2<-1:1][2<-3:2][12<-6:3][4<-7:4][4<-11:5]

***Print Leaves***
[1][2][3][4][5]
Bruderbaum? true
1 l÷schen... delete:: [2<-1:1]
kein Onkel
opa hat rechten bruder
verschmelzen
delete:: (9<-  6:3 .12:3.)
Onkel hat nur ein Kind, verschmelzen
delete:: (10<-  4:4 .9:5.)
wurzel, ein kind wird gel÷scht, baum verliert h÷he wurzel: (*2:2 .5:3. 4:4*)
true
***Print Tree***
(*2:2 .5:3. 4:4*)
(5<-  3:2 .2:2. 6:3)(5<-  7:4 .4:4. 11:5)
[2<-3:2][2<-6:3][4<-7:4][4<-11:5]

***Print Leaves***
[2][3][4][5]
Bruderbaum? true
2 l÷schen... delete:: [2<-3:2]
Onkel hat 2 Kinder
true
***Print Tree***
(*2:3 .5:3. 4:4*)
(5<-  6:3 .2:3.)(5<-  7:4 .4:4. 11:5)
[2<-6:3][4<-7:4][4<-11:5]

***Print Leaves***
[3][4][5]
Bruderbaum? true
3 l÷schen... delete:: [2<-6:3]
vater hatte nur ein kind, delete (5<-  6:3 .2:3.)
delete:: (5<-  6:3 .2:3.)
wurzel, ein kind wird gel÷scht, baum verliert h÷he wurzel: (*7:4 .4:4. 11:5*)
true
***Print Tree***
(*7:4 .4:4. 11:5*)
[4<-7:4][4<-11:5]

***Print Leaves***
[4][5]
Bruderbaum? true
4 l÷schen... delete:: [4<-7:4]
wurzel, ein kind wird gel÷scht, baum verliert h÷he wurzel: (*.11:5.*)
true
***Print Tree***
(*.11:5.*)

***Print Leaves***
[5]
Bruderbaum? true
5 l÷schen... delete:: (*.11:5.*)
true
***Print Tree***
Null

***Print Leaves***
null
Bruderbaum? true
*/