mit konstanter laufzeit durch einen binaerbaum iterieren?

otze

Shade Of Mine schrieb:

otze schrieb:

@shade
du weist schon, dass es zwischen den datenknoten in einem binaerbaum keine direkten verbindungen gibt?

Konstante Zeit heisst doch nur, dass es unabhängig von der Gesamtzahl ist.

Und egal wie groß der Baum ist, ich brauche immer die gleiche Zeit (OK, nicht immer die gleiche, weil ein 'Schritt' nach links schneller geht als nach oben und dann 'rechts', aber es ist unabhängig ob der Baum 10, 100 oder 1mio Elemente hat).

falsch, und ich trete sofort den beweis an:
balancierter baum mit 2 datennodes:

d1 d2
 \/
 n

von d1 zu d2(den datennodes) brauchen wir eine bestimmte zeit(und zwar die, um von d1 nach n und von n nach d2 zu kommen)

nun hängen wir noch zwei weitere nodes(d3,d4) dran:

d1 d2 d3 d4
 \/    \/
  n1   n3
   \  /
    n2

von d1 nach d2 und von d3 und d4 brauch man dieselbe zeit wie im ersten baum.
von d2 nach d3 dauerts...länger(von d2 nach n1,nach n2 nach n3 nach d3) das is also nicht konstant.

und immer von n2 auszugehen, und den nächstgrößeren node zu suchen würde eine logarithmische laufzeit brauchen-also auch nicht das was man braucht

bäume wachsen von oben nach unten.

otze

dann machn kopfstand

@bashar Threading wär dann aber mit ner mittelgroßen Sünde gleichzusetzen oder?

Bashar

Wieso, haste ne bessere Idee?

otze

nee...
ich hab aber keine ahnung, wie ich den iterator aufbauen soll... also ob ich einfach einen vector mit zeigern auf die einzelnen datennodes erstellen soll, und dem iterator diesen dann übergebe(was garantiert nicht performant wär) oder... ka

TheTester

mich würde persönlich mal die exakte Textstelle aus dem Standard interessieren, hab das Teil leider nicht. Ich kann mir grad eben partout nich vorstellen was gemeint ist, von wegen konstante Laufzeit. Damit is doch sicher die Laufzeit proportional zur Anzahl der Elemente gemeint oder?

otze
****

was wäre an deiner Idee nicht "performant"?

bye

tt

Bashar

http://www.kuzbass.ru:8086/docs/isocpp/

Relevant sind hauptsächlich folgende Stellen:
24.1p8: All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized). Therefore, requirement tables for the iterators do not have a complexity column.

23.1.2p6: iterator of an associative container is of the bidirectional iterator category.

Da map ein assoziativer Container ist, muss map bidirektionale Iteratoren bereitstellen, welche die Operatoren ++ und -- in konstanter Zeit unterstützen müssen.

otze

konstant proportional zur anzahl der elemente wäre linear
@Thetester
für jeden node der im vector enthalten sein muss, müsste der tree einmal durchlaufen werden, was bedeuten würde, dass die komplexität des algorithmus O(log₂(nⁿ)) ist

.

Bashar

Es gibt IMHO eigentlich nur 2 Möglichkeiten: Entweder fette Iteratoren, die einen Stack eingebaut haben. Oder gefädelte ( ) Bäume.

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.