Balanciertheit von Binärbäumen bestimmen

Hiho,

Ich soll folgendes Problem lösen :

Die Unbalanciertheit u(v) eines Knotens v in einem Binärbaum B ist der Höhenunterschied der beiden
darunterliegenden Teilbäume. Die Unbalanciertheit U(B) eines Binärbaumes B ist die maximale
Unbalanciertheit aller Knoten v im Baum B.
a) Entwerfen Sie einen (möglichst einfachen) Algorithmus, der die Unbalanciertheit U(B) eines Binärbaumes
B mit n Knoten in linearer Zeit berechnet und definieren Sie alle verwendeten Datenstrukturen.
b) Analysieren Sie Laufzeit und Speicherbedarf.

Also meine Idee ist folgende:

Um die Tiefe des Teilbaumes unter einem Knoten zu berechnen verwende ich das Unterprogramm hier:

public int [] getDepth(){
  int lDepth = 0;
  int rDepth = 0;

  if(getLeft() != null){
    lDepth = getLeft().getDepth();
  }
  if(getRight() != null){
    rDepth = getRight().getDepth();

Int [] Depth = [ lDepth, rDepth ];
return Depth

dann muss ich nur noch diese Programm für jeden Knoten aufrufen und kann die Unbalanciertheit in jedem Knoten bestimmen oder?

CStoll

Der Ansatz ist gut, kommt nur nicht auf lineare Laufzeit. Der Trick besteht darin, daß du nicht nur die Höhe, sondern auch die Balanciertheit der Unterbäume in einem Abwasch berechnest und zurückgeben lässt:

int getsize(int& balance)
{
  int bleft=0,bright=0;
  int sleft = left!=NULL ? left->getsize(bleft) : 0;
  int sright = right!=NULL ? right->getsize(bright) : 0;
  balance = max(bleft,bright,abs(sleft-sright));
  return max(sleft,sright)+1;
}

(ungetestet)