Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
21.12.2006, 16:45 Uhr
Getit

Hallo,

stehe vor folgendem Problem:
Ich habe einen BBaum aufgebaut (nicht balanciert!!!) und stehe jetzt vor dem Problem jedes 2. Element aus diesem Baum zu löschen.

Hab mir das so vorgestellt,
das ich mir den Baum traversieren lasse und dann jedes 2. Element lösche (habe neben den Nutzdaten in jedem Element auch noch nen Zähler stehen der mir angibt wann das Element eingefügt wurde) und an dessen Stelle das kleinste Element des rechten Teilbaumes hinsetze.
Soweit ist das ja nicht so schwierig,
aber wie komme ich an den Vorgänger des jeweils 2. Elements???

Ich muss ja den Zeiger des Vorgängers des jeweils 2. Elements umhängen, stehe aber vor dem Problem wie komme ich zum Vorgänger.

Bin für jeden Tip (oder URL) dankbar

P.S.: Wie schon gesagt ist der Baum nicht balanciert, und muss auch nach dem Löschen nicht balanciert sein.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
21.12.2006, 17:35 Uhr
0xdeadbeef
Gott
(Operator)

1. B-Baum != Binärbaum
2. Das jeweils vorherige Element ist das größte (rechtsseitigste) Element des linken Teilbaums. Mit anderen Worten:

C++:

node *predecessor(node *my_node) {
  node *ptr = my_node->left;

  if(ptr) {
    while(ptr->right) ptr = ptr->right;
  }

  return ptr;
}

Allerdings empfiehlt es sich, bei der Verarbeitung von Bäumen weniger in iterativen, als mehr in rekursiven Bahnen zu denken. Wenn ich richtig verstehe, worauf du da hinauswillst, dann ist das ne ziemlich langsame Art, nen Baum zu durchlaufen.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 21.12.2006 um 17:38 Uhr von 0xdeadbeef editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
21.12.2006, 18:31 Uhr
Getit

Zitat:

Wenn ich richtig verstehe, worauf du da hinauswillst, dann ist das ne ziemlich langsame Art, nen Baum zu durchlaufen.

Egal, der Prof will es so.

Aber ich verstehe deine Lösung nicht so ganz:

Bearbeitung:

Code:

              9
           /     \
          3      12
       /     \
     1        6
       \     /  \
        2  5    7

Shit, wie bekomme ich das hin das mein Bild auch so erscheint wie ich es gezeichnet habe???

Naja, nach inorder:
1, 2, 3, 5, 6, 7, 9, 12

Angenommen die 6 ist jetzt das 2. (oder 4., 6.,...) Element.
Wie soll ich mit deiner Lösung rausfinden, dass der Vorgänger von 6 die 3 ist???

Dieser Post wurde am 21.12.2006 um 18:44 Uhr von FloSoft editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
21.12.2006, 20:35 Uhr
0xdeadbeef
Gott
(Operator)

Ach so, du willst den Vater, nicht den Vorgänger. Sag das doch gleich. Ich würd mir nen parent-pointer vorhalten, der da gleich drauf zeigt, sonst musst du halt von der root-node aus suchen:

C++:

node *seek_father_of_aux(node *n, node *parent, value_type value) {
  if     (value < n->value)
    return n-> left ? seek_father_of_aux(n-> left, n, value) : NULL;
  else if(value > n->value)
    return n->right ? seek_father_of_aux(n->right, n, value) : NULL;
  return parent;
}

node *seek_father_of(node *root, value_type value) {
  return seek_father_of_aux(root, NULL, value);
}

...wobei es dann dir obliegt, zu unterscheiden, ob ein Wert einfach nicht im Baum ist oder die Root-Node den Wert enthält.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 21.12.2006 um 20:37 Uhr von 0xdeadbeef editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
21.12.2006, 21:10 Uhr
Getit

Danke!!

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: