mit konstanter laufzeit durch einen binaerbaum iterieren?

Shade Of Mine

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).

Bashar

otze schrieb:

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

Diese Verbindungen heißen Threads (jedenfalls laut Knuth, ka wie man die auf deutsch nennt).

tag

Langenscheidt Wörterbuch schrieb:

thread I s. 1. Faden m: a) Zwirn m, Garn n: hang by a thread übertragen an einem Faden hängen, b) im weiteren Sinne Faser f, Fiber f, c) übertragen (dünner) Strahl, Strich m, d) übertragen Zs.-hang m: lose the thread (of one's story) den Faden verlieren; resume (oder take up) the thread den Faden wieder aufnehmen; 2. Technik Gewinde(gang m) n; II Verb/transitiv 3. Nadel einfädeln; 4. Perlen etc. aufreihen; 5. mit Fäden durchziehen; 6. übertragen durchziehen, -dringen; 7. sich winden durch: thread one's way (through) sich (hindurch)schlängeln (durch); 8. Technik Gewinde schneiden in (Akkusativ): thread on anschrauben

Bashar

Danke, aber das wußte ich. Man kann aber Fachwörter oft nicht einfach so übersetzen. Bevor ich mich also in die Nesseln setze, gebe ich lieber nicht vor, es zu wissen.

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