in einer baum struktur den ersten identischen parent von 2 knoten finden

hallo brauche einen algo um in einer baum struktur den ersten identischen parent von 2 knoten zu finden, hat da jemand eine idee wie man das performant lösen könnte?

lg lolo

knivil

Was ist der erste Parent im Baum?

--d
  '-C
    '-A
    '-B

in diesem fall c

axo am besten ohne temp. array

Fedaykin

noobLolo schrieb:

hallo brauche einen algo um in einer baum struktur den ersten identischen parent von 2 knoten zu finden, hat da jemand eine idee wie man das performant lösen könnte?

lg lolo

Ich würde zu jeden Knoten eine HashSet mit parents führen. Dann für die Knoten dessen Eltern die du suchst. Das ParentElement in die List einfügen und im HashSet des anderen Knotens schauen ob der Knoten existiert. Existiert er hast du den elternknoten. Ansonsten machst du das gleiche beim anderen Knoten. Kurzum du führst immer die HashSets der Elternknoten der beiden Suchknoten als Akkumulator mit und erweiterst abwechselnd die Tiefe um den nächsten Parent. Du musst natürlich noch prüfen ob du bei einen Element bereits an der Wurzel bist, dann musst du nur beim anderen Element weitermachen etc. Je nachdem was dir von deinen Baum bekannt ist kannst du das noch optimieren. (Anstatt abwechselnd zum nächsten Parent zu springen für einen besonders tiefen knoten immer 2 mal den Parent ermitteln bevor der andere Knoten an die reihe kommt). Sofern du die Tiefe der Knoten kennst kannst du da schon Parents rausfiltern die gar nicht in frage kommen.

Edit: Oh ohne Temparray wirds schwieriger. Das ist nicht wirklich effizient. Dort kommst du wohl kaum drumherum als in allen anderen Elementen eines Knotens zu schauen ob der 2. Knoten dort existiert, andernfalls weiter nach oben gehen. Es sei denn du kannst noch gewisse allgemeine Aussagen über den Baum treffen (z.B. kennst du die Tiefe der beiden Knoten, dann kannst du nicht in Frage kommenen Elemente schon ausblenden)

knivil

Ich würde zu jeden Knoten eine HashSet mit parents führen.

Warum? Es ist ein Baum, so dass jeder Knoten maximal ein Parent hat. Wenn es ein Baum ist, dann hat jeder Knoten eine Liste von Kindknoten. Einfach rekursiv den Baum nach Knoten durchsuchen, die zwei Kindknoten besitzen. Wenn es das nicht ist, dann spezifiziere naeher, was erster und was parent ganz genau bedeutet.

Fedaykin

knivil schrieb:

Ich würde zu jeden Knoten eine HashSet mit parents führen.

Warum? Es ist ein Baum, so dass jeder Knoten maximal ein Parent hat.

Ja aber ich führe die Parents der Parents der Parents im HashSet mit um schnell zu prüfen ob einer der Parents in beiden Sets vorkommt. Das wäre das schnellste was mir einfällt (Dummerweise speicherlastig )

Bei näherer Betrachtung reicht sogar nur ein HashSet "Besuchte Parents" egal von wem die kommen. Wenn der aktuelle Parent eines Knotes dort schon drinnen ist, ist es der erste gemeinsame, andernfalls wird der Parent dort hinzu gefügt (Im grunde das Akkumulator prinzip)

knivil

Sorry, ich weiss nicht wovon du redest.

Jester

@Fedaykin: dann kannst du doch gleich von beiden Knoten aus abwechselnd im Baum nach oben laufen und abbrechen sobald du den ersten Knoten von beiden Seiten entdeckt hast.

Es gibt auch Datenstrukturen, die das Abfragen nach linearer Vorberechnung in konstanter Zeit ermöglichen -- die sind aber nicht ganz einfach: http://en.wikipedia.org/wiki/Lowest_common_ancestor

Fedaykin

Jester schrieb:

@Fedaykin: dann kannst du doch gleich von beiden Knoten aus abwechselnd im Baum nach oben laufen und abbrechen sobald du den ersten Knoten von beiden Seiten entdeckt hast.

Ich glaube das ist meine Idee. Vielleicht etwas komplizierter erläutert. Das war schon immer mein Problem.

also so hab ichs jetzt einfach mal gemacht, auch wenn mir das extra array ein bischen aufstößt

,findFirstEqualParent:function(nodeA,nodeB){
		dbg("ffe");
		var tmpA = [nodeA], tmpB = [nodeB],buffer,la,lb;

		buffer = nodeA;
		while(buffer = buffer.parent)
			tmpA.push(buffer);

		buffer = nodeB;
		while(buffer = buffer.parent)
			tmpB.push(buffer);

		la = tmpA.length;
		lb = tmpB.length;

		while(tmpA[--la] == tmpB[--lb]);

		return tmpA[++la];
	}

lg lolo

Jester

Das sieht aber ein bißchen verschwenderisch aus, Du läufst ja immer bis ganz nach oben... abwechselnd laufen und nur laufen bis man einen Knoten findet, der schon bearbeitet worden ist ist je nach Aussehen des Baums deutlich effizienter.

Fedaykin

Hmm.. ich weiss nicht so genau ob das bei einen ungleichmässigen Baum funktioniert. Welche Sprache ist das überhaupt?

Du baust einen Puffer aus allen Parents der Knoten auf. Das ist wohl unnötig.
Mache abwechselnd für A und B folgendes.
1.) Weise A oder B tmp zu
2.) Prüfe ob tmp.Parent im Buffer vorhanden ist
3.) wenn nein füge tmp.Parent dem Buffer hinzu
4.) wenn ja ist tmp.Parent das elternelement von A und B.
5.) A (bzw = A (oder B).Parent

Das ganze ist dumm beschrieben hoffe das prinzip ist klar. Ausserdem musst du prüfen ob A bzw B. Parent die Wurzel ist, wenn ja dann musst du das ganze nur beim anderen Knoten fortführen.

du meinst so?

,findFirstEqualParentA:function(nodeA,nodeB){
		var bufferA = nodeA, bufferB = nodeB;

		while(bufferA){
			bufferB = nodeB;
			while(bufferB){
				if(bufferA == bufferB)
					return bufferA;
				bufferB = bufferB.parent;
			}
			bufferA = bufferA.parent;
		}
	}

lg lolo

Fedaykin

ich würds so machen (Achtung Pseudocode)

GetParent(nodeA,nodeB)
{
  //flag was gerade dran ist A oder B
  bool UseA = true;
  //prüfen ob A oder B gleich sind
  if (nodeA == nodeB) return nodeA;
  //A und B als Besucht angeben 
  VisitedParents = {nodeA,nodeB}
  while( true )
  {
  //prüfen ob A an der reihe ist und A nicht die Wurzel ist 
  if (UseA && nodeA != root)
  {
     //nächsten Parent prüfen
     if (CheckNode(nodeA.Parent, VisitedParents)
     {
        //Wenn CheckNode true liefert haben wir das ziel erreicht
        return nodeA.Parent
     }
     else
     {
        //Checknode war nicht erfolgreich also auf den nächsten Parent gehen
        //und mit anderen knoten weitermachen
        nodeA = nodeA.Parent;
        UseA = false;
     }  
  }
  //Das gleiche für KnotenB
  else if (!UseA && nodeB != root)
  {
    if (CheckNode(nodeB.Parent, VisitedParents)
     {
        return nodeB.Parent
     }
     else
     {
        nodeB = nodeB.Parent;
        UseA = true;
     } 
  }
  //Knoten A und Knoten B sind nun root aber es wurde keine übereinstimmung    gefunden
  else
  { 
     return null;
  }
  }
}

CheckNode(node,VisitedParents)
{
     Prüfen ob in visited schon der knoten drin ist.
     if (VisistedParents.Exist(node)
        //Wenn ja dann haben wir den gemeinsamen knoten
        return true;
     else
        //Knoten war nicht enthalten also als besucht markieren und false liefern
        VisitedParents.Add(node);
        return false;

}

das ganze sollte js ein. also da meine knoten eh schon eine flag haben, hab ichs jetzt mal so gemacht

danke an Jester an dieser stelle

,cleanTainting:function(node){
		while(node && node.flags & MR_TAINTED){
			node.flags ^= MR_TAINTED;
			node = node.parent;
		}
	}
	,cleanTaintingEx:function(){
		var l = arguments.length
			,node;

		while(l--)
			this.cleanTainting(arguments[l]);
	}
	,findFirstEqualParentC:function(nodeA,nodeB){
		var tmpA, tmpB;

		tmpA = nodeA;
		tmpB = nodeB;

		do{
			dbg('tmpA.flags == '+debugFlags(tmpA.flags));
			if(tmpA.flags & MR_TAINTED){
				this.cleanTaintingEx(nodeA,nodeB);
				return tmpA;
			}

			tmpA.flags |= MR_TAINTED;
			tmpA = tmpA.parent;

			dbg('tmpB.flags == '+debugFlags(tmpB.flags));
			if(tmpB.flags & MR_TAINTED){
				this.cleanTaintingEx(nodeA,nodeB);
				return tmpB;
			}

			tmpB.flags |= MR_TAINTED;
			tmpB = tmpB.parent;
		}while(tmpA && tmpB);

		while(tmpA){
			dbg('tmpA.flags == '+debugFlags(tmpA.flags));
			if(tmpA.flags & MR_TAINTED){
				this.cleanTaintingEx(nodeA,nodeB);
				return tmpA;
			}

			tmpA.flags |= MR_TAINTED;
			tmpA = tmpA.parent;
		}

		while(tmpB){
			dbg('tmpB.flags == '+debugFlags(tmpB.flags));
			if(tmpB.flags & MR_TAINTED){
				this.cleanTaintingEx(nodeA,nodeB);
				return tmpB;
			}

			tmpB.flags |= MR_TAINTED;
			tmpB = tmpB.parent;
		}
	}

lg lolo

Jester

edit: das bezog sich auf den zweiten versuch, deine neue implementierung hab ich mir noch nicht angeschaut. hier ist mein versuch in C++-nahem Pseudo-Code

Das scheint mir nicht korrekt zu sein, Deine Suchen können sich ja verpassen. Ich nehme einfach mal an, dass ich pro Knoten ein Bit Speicher zum markieren habe und anfangs alle Knoten unmarkiert sind

Pseudo-Code

lca(nodeA,nodeB)
{
  if(nodeA == nodeB) return nodeA;

  tmpA = nodeA;
  tmpB = nodeB;

  mark(tmpA);
  mark(tmpB);

  for(;;)
  {
    if(tmpA != root) // wenn wir nicht die Wurzel sind einen Schritt nach oben   laufen
    {
      tmpA = parent(tmpA);
      if(is_marked(tmpA))  // wenn schon markiert, räume Markierungen auf und gib Knoten zurück
      {
        clearMarks(nodeA,tmpA);
        clearMarks(nodeB,tmpB);
        return tmpA;
      }
      mark(tmpA);  // sonst markiere Knoten
    }

    // und fahre mit vertauschen Rollen fort
    swap(tmpA,tmpB);
    swap(nodeA,nodeB);
  }
}

clearMarks(start,end)
{
  unmark(start);

  while(start != end)
  {
    start = parent(start);
    unmark(start);
  }
}