mit konstanter laufzeit durch einen binaerbaum iterieren?

otze

wie fädelt man denn einen Baum?^^

Bashar

Das is ne gute Frage ... da verweise ich auf Knuth und andere Checker

otze

wie heisst denn das dazu passende buch?

btw:
so wird der iterator der stl::map(die ja auf einem binaeraum basiert) incrementiert...ich muss sagen, dass ich nur Bahnhof versteh

template <class _Dummy> _Rb_tree_node_base* _STLP_CALL
_Rb_global<_Dummy>::_M_increment(_Rb_tree_node_base* _M_node)
{
  if (_M_node->_M_right != 0) {
    _M_node = _M_node->_M_right;
    while (_M_node->_M_left != 0)
      _M_node = _M_node->_M_left;
  }
  else {
    _Base_ptr __y = _M_node->_M_parent;
    while (_M_node == __y->_M_right) {
      _M_node = __y;
      __y = __y->_M_parent;
    }
    if (_M_node->_M_right != __y)
      _M_node = __y;
  }
  return _M_node;
}

kann jemand der anwesenden skiller hier damit was anfangen? saß jetzt ca 2 stunden über der _tree.h/_tree.c und komm nich weiter...

Andreas2

Ich geh mal davon aus, dass die Sortieroperation das < ist.
Dann sind alle Werte links vom aktuellen Knoten "kleiner", als der Wert des aktuellen Knotens, und alle Werte rechts davon sind grösser. Man will nun von einem vorgegebenen Knoten den nächst grösseren Wert erhalten.
Dabei gibt es 2 Möglichkeiten:
1. Der aktuelle Knoten A hat einen rechten Link zum Knoten B:
Dann geht man weiter zum rechten Knoten B. Von B aus geht man nun soweit wie möglich nach links, denn alle Knoten links von B sind grösser als A, aber kleiner als B. Und wir suchen ja nach dem kleinstmöglichen Wert, der grösser als A ist, deshalb so weit nach links wie möglich. Das ist der erste Teil des Codes:

if (_M_node->_M_right != 0) {
    _M_node = _M_node->_M_right;
    while (_M_node->_M_left != 0)
      _M_node = _M_node->_M_left;
  }

2. Falls vom Knoten A kein rechter Link abgeht:
Dann geht man zum Mutterknoten M (parent). Falls A der rechte Knoten von M ist, dann ist A grösser als M. In dem Fall weiter zum parent von M, und prüft wieder, ob M der rechte Knoten vom parent ist. Dies macht man solang, bis man zu einem Knoten gelangt, der links von seinem parent liegt, oder die Wurzel des Baums erreicht ist. Zum Schluss testet man noch, ob wirklich ein "grösserer" Knoten zurückgegeben wird:

else {
    _Base_ptr __y = _M_node->_M_parent;
    while (_M_node == __y->_M_right) {
      _M_node = __y;
      __y = __y->_M_parent;
    }
    if (_M_node->_M_right != __y)
      _M_node = __y;
  }

So, ich hoff, das war einigermassen erhellend...

Gruss,
Andreas

Bashar

Oberflächlich betrachtet verletzt diese Implementation den Standard, weil die while-Schleifen den Aufwand auf O(logn) treiben. Man müsste allerdings mal analysieren, ob der Aufwand nicht aufgrund der Struktur des Baumes am Ende doch amortisiert konstant ist.

otze

ach klar, jetzt weis ich, wie das ist:

ich ging davon aus,dass die datenknoten(d) zu den normalen noten(n) so im baum liegen:

d  d  d  d
 \/    \/ 
  n    n
    \/
    n

faktisch scheints in der map so zu sein:

d  d  d  d
 \/    \/ 
  d    d
    \/
    d

kein wunder, dass ich mit dem oben gezeigten code nich klar gekommen bin

SideWinder

@otze: Tip beim Lesen von HP-STL-Code: Einfach mal Replace drüber laufen lassen, mit schöneren Variablennamen ist das schon viel besser zu lesen

MfG SideWinder

otze

das schlimmste sind eh die defines-.-

otze

ich hab noch ne frage, und zwar bin ich grad bei der neukonzeption der map, und da kam doch bei mir nochmal die folgende frage auf:

wie oft muss ein Baum ausbalanciert werden?

es is ja so, dass man die logarithmische zugriffszeit nur erreichen kann,wenn der Baum balanciert ist, da sich sonst die zugriffszeit schnell O(n/2) nähert, und ich frag mich,m ob ich bei jedem einfügen neubalancieren soll, oder in einem bestimmten abstand n(n währe in diesem fall die anzahl der einträge, ab der der baum eine neue ebene erhalten müsste-also 2^d+1-1,wobei d die aktuelle voll ausgelastete ebenenanzahl des baum ist)?

SideWinder

Ein Baum muss immer dann ausbalanciert werden wenn sein Höhenunterschied [-1/+1] unter- bzw. überschreitet?!

Wenn ich links eingefügt werde und Elter keinen rechten Bruder hat kannst du schon die Arbeiter pfeifen.

MfG SideWinder

Andreas2

Wenn Du den Baum als Red-Black-Tree implementierst, musst Du Dir (fast) keine Sorgen mehr über das ausbalancieren machen. Dort wird beim Einfügen eines neuen Elements gleich entlang des Einfüge-Pfades balanciert. Der zusätzliche Aufwand gegenüber einem "normalen" insert ist sehr gering, und die resultierenden Bäume meist recht nah am "idealen" Baum. Wie das mit den Red-Black-Trees genau funktioniert, kannst Du z.B. in Sedgewicks "Algorithms in C++" nachlesen.

otze

hmm wie müsste ein algorithmus aussehen, der einen solchen (perfekten) Baum konstruieren kann?

//mit 3 elementen
1  3
 \/
  2
//mit 7 elementen
1  3 5  7
 \/   \/
  2    6
   \  /
    4
//mit 15 Elementen
1  3 5  7 9  11 13 15
 \/   \/   \/    \/
  2    6   10    14
   \  /     \   /
    4         12
      \     /
         8

wenn ich den Baum bei jedem ebenensprung balancieren müsste, dann ginge dass einfach,ich würde alle elemente in eine liste/vector packen, sortieren, und dann würde ich einfach daraus den neuen Baum erstellen(die mitte der liste wär dann der root(im beispiel des 15er knotens das 8. element) dann wird für die beiden teilabschnitte links und rechts vom root knoten wieder die mitte gesucht(das sind dann die punkte 4 und 12) und an die 8 gehängt, das passiert dann mit den nächsten abschnitten bis kein punkt mehr zu vergeben ist

aber für einen algorithmus, der sich bei jedem einfüge vorgang sofort perfekt ausrichtet fehlt mir irgendwie das system...
zb in dem Fall:

dieser Baum ist mit diesen Werten perfekt angeordnet,was würde aber passieren, wenn ich jetzt ne 11 einfügen würde? am ende müsste der Baum so umgeordnet worden sein:

beim besten willen, ich kann da keinen anständigen algorithmus finden

otze

hier mal der algorithmus, den ich grad mal gemacht hab:

erstelle neuerKnoten
ebene=1
testknoten=baumwurzel

solange Baumende nicht erreicht
	wenn neuerKnoten==testknoten
		abbrechen 
	wenn  neuerKnoten<testknoten
		testknoten=linke seite von testknoten
	sonst testknoten=rechte seite von testknoten
	ebene+1

wenn testknoten==ende
	tausche ende mit neuerknoten
sonst
	wenn neuerknoten==testknoten
		füge neuerknoten in testknoten ein
		abbrechen
	wenn neuerknoten<testknoten
		hänge neuerknoten an linke seite von testknoten
	sonst 
		hänge neuerknoten an rechte seite von testknoten
knotenZahl+1
ebene+1	
Wenn knotenzahl==maxKnoten
	ebenenZahl+1
	maxKnoten=2^ebenenZahl-1

wenn ebene>ebenenZahl
	sortiereBaum;

nicht an den namen stören, ich hab mir angewöhnt, bei algorithmen entweder alles deutsch, oder alles englisch zu machen, im code werden also die variablennamen durch englische ersetzt

ich denke, der algorithmus müsste alles abdecken, was auftreten kann, oder hab ich was vergessen?

über sortiereBaum mach ich mir später gedanken,aber ich glaub, da kann man viel über rekursion machen...