Elemente aus binären Bäumen löschen

Post Reply
Message
Author
bakunin
Posts: 597
Joined: 16. Aug 1999 6:44
Location: Lorsch (Südhessen)
Contact:

Elemente aus binären Bäumen löschen

#1 Post by bakunin »

Hi!

Gegeben sei folgender sortiere binäre Baum:
<blockquote><pre><font size="1" face="">code:</font><hr><font face="Courier New" size="2">
50
/ \
33 70
/ \ / \
20 40 60 80
/ | / \
5 27 36 45
/ \ /
35 39 43
/ \
41 44
</font><hr></pre></blockquote>
Wie kann ich z.B. die Zahl 40 aus diesem binären Baum entfernen? Er soll danach auch noch sortiert sein und es soll möglichst simpel und mit wenigen Operationen passieren. Hinzufügen und suchen waren ja noch einfach. Ein Element zu entfernen, dass einen oder keinen Nachfolger hat, ist auch trivial. Aber wie ich das bei Elementen mit 2 Nachfolgern machen kann, weiß ich nicht, d.h. ich hatte mir schon was überlegt, was aber in einem Fall wie dem obigen nicht funktioniert.

Es scheint im Web leider kein Binary-Tree-FAQ zu geben. :)

Cheers,
GNU/Wolfgang

marc
Posts: 444
Joined: 20. Apr 2001 23:31
Location: Arnsberg

Re: Elemente aus binären Bäumen löschen

#2 Post by marc »

Nabend.

Ich würd jetzt spontan sagen, daß man einfach den Zeiger auf den linken Nachfolger (die 36) von dem nächstgrößeren Element ausgehen läßt. Also von der 41 ein Zeiger auf die 36. Und die 33 zeigt dann auf 45.

Ich bin mir jetzt nicht ganz sicher, aber eventuell findet man da was im Web unter dem Stichwort "Topologisches Sortieren".

Gruß
Marc

marc
Posts: 444
Joined: 20. Apr 2001 23:31
Location: Arnsberg

Re: Elemente aus binären Bäumen löschen

#3 Post by marc »

Ich versuchs nochmal etwas ausführlicher...

Angenommen man ist in dem Baum gerade auf 33, dann einen Hilfspointer auf die 33, um sich diese Position zu merken.
Dann den linken Pointer des zu löschenden Elementes (40) sichern, also einen Hilfszeiger auf die 36.
Danach von der rechten Seite des zu löschenden Elementes aus immer links halten und den Baum durchlaufen, bis es nicht mehr weitergeht. (40 - 45 - 43 - 41 - NIL)
Und dann von dem letzten Element (41) den linken Pointer auf die vorher gesicherte 36 verbiegen.
Zum Schluß dann noch von dem Vorgänger des zu löschenden Elementes (33, siehe 1. Hilfspointer) den rechten Pointer auf den rechten Pointer des zu löschenden Elementes biegen. Damit zeigt der rechte Zeiger der 33 dann auf die 45 und das Element 40 ist Geschichte. Sollte es zumindest.
Ich hoffe ich hab nichts übersehen. Für Speicherlecks übernehme ich keine Verantwortung ;)
Gruß
Marc

bakunin
Posts: 597
Joined: 16. Aug 1999 6:44
Location: Lorsch (Südhessen)
Contact:

Re: Elemente aus binären Bäumen löschen

#4 Post by bakunin »

Hi Marc!

Super, vielen Dank. Das ist ähnlich wie das, was ich mir überlegt hatte, nur war ich nicht darauf gekommen, an das äußerste Element den anderen Teil dranzuhängen, ich wollte stattdessen dieses Element (also hier die 41) an die Stelle des zu löschenden Elementes (40) schieben. Das geht aber genau dann schief, wenn dieses Element noch einen Nachfolger auf der anderen Seite hat, also wenn an der 41 noch eine 42 hängen würde. Den Baum oben habe ich in dieser Hinsicht also sogar falsch konzipiert.

Cheers,
GNU/Wolfgang

marc
Posts: 444
Joined: 20. Apr 2001 23:31
Location: Arnsberg

Re: Elemente aus binären Bäumen löschen

#5 Post by marc »

Moin.
Wieso meintest Du, daß der Baum falsch konzipiert war? Wenn ich das Sortierkonzept richtig gedeutet habe, dann seh ich eigentlich nichts was gegen den Baum spricht.

Was mir gerade noch eingefallen ist:
Wenn man den Baum so wie geschrieben bearbeitet, also die 40 löscht und den Rest unten dran hängt, erhält man ja so einen Baum:
<blockquote><pre><font size="1" face="">code:</font><hr><font face="Courier New" size="2">
50
/ \
33 70
/ \ / \
20 45 60 80
/ | /
5 27 43
/ \
41 44
/
36
/ \
35 39

Das ist zwar richtig sortiert, ist aber nicht so ganz ausgeglichen im Aufbau.
Deine Idee, die 41 an die Stelle der 40 zu setzen, geht übrigens doch, allerdings müßte man dann komplett anders vorgehen.
Man könnte dann alles unterhalb der 40 als neuen "Unterbaum" aufbauen, wobei dann die 41 die obere Wurzel wäre,
da sie in der Mitte liegt (Es ist jetzt natürlich Zufall, daß es die 41 ist, es hätte auch eine andere Zahl sein können...)
Dieser Unterbaum wird dann rechts an die 33 gehängt. Dieses Vorgehen ist zwar etwas aufwendiger,
aber dafür erhält man auch einen etwas ausgeglicheneren Baum mit einer geringeren Tiefe:

50
/ \
33 70
/ \ / \
20 41 60 80
/ | / \
5 27 36 44
/ | | \
35 39 43 45
</font><hr></pre></blockquote>
Gruß
Marc (der Binärbäume früher mal gehaßt hat ;)

PS: Das Board hat 'n Bug. Wenn man zwei "code"-Blöcke definiert, steht im zweiten das gleiche wie im ersten. (Ein Dankeschön an die Vorschau-Funktion)

Descartes

Re: Elemente aus binären Bäumen löschen

#6 Post by Descartes »

> PS: Das Board hat 'n Bug. Wenn man zwei "code"-Blöcke definiert, steht im zweiten das gleiche wie im ersten. (Ein Dankeschön an die Vorschau-Funktion)

Das Problem ist bekannt -- hatte ich Mirko aka. Demon bereits vor ein/zwei Jahren mal gesagt.

Descartes

Re: Elemente aus binären Bäumen löschen

#7 Post by Descartes »

@GNU/Wolfgang
Warum nicht die GNU libavl verwenden ?

GNU libavl
<a href="http://www.msu.edu/user/pfaffben/avl/" target="_blank"><!--auto-->http://www.msu.edu/user/pfaffben/avl/</a><!--auto-->

AVL Tree Beispiel-Implementierung
<a href="http://www.cs.uow.edu.au/people/nabg/AB ... eecode.txt" target="_blank"><!--auto-->http://www.cs.uow.edu.au/people/nabg/AB ... <!--auto-->

<blockquote><pre><font size="1" face="">code:</font><hr><font face="Courier New" size="2">
void AVLTree::Del(AVLTreeNode*& t, AVLTreeNode*& r)
{
/*
auxiliary routine for DeleteRec. It is called when record to
be deleted has left and right branches. In such cases, it is
not possible to simply unhook the bad record. It has to be
replaced by the largest (i.e. rightmost) record in it left branch.
example
delete 25 from this tree:

25
|
+------------+------------+
| |
12 37
| |
+-----+-----+ +-----+-----+
6 20 30 48
| | | |
+---+---+ +---+---+ +---+---+ +---+---+
| | | | | | |
4 9 18 22 33 42 50
| | | |
+--+--+ +--+--+ +-+--+ +-+--+
| | | | |
5 14 19 23 45
|
+--+--+
|
13

new tree will have 23 at root. This routine is called with
pointer to 12 (left of node 25) as argument r.
Recursively move down and right from 12 until get to 23.
There do second part of code of routine (copy data defining node 23
into original node 25), unhook the 23 node (if its got left children
then substitute them at point where 23 used to hook in)
delete the node that used to hold the data 23

that will result in the following (unbalanced) tree
23
|
+------------+------------+
| |
12 37
| |
+-----+-----+ +-----+-----+
6 20 30 48
| | | |
+---+---+ +---+---+ +---+---+ +---+---+
| | | | | | |
4 9 18 22 33 42 50
| | |
+--+--+ +--+--+ +-+--+
| | | |
5 14 19 45
|
+--+--+
|
13

as unwind the recursion, check balance
its OK at 22
but at 20 discover that we were "left-long" and right branch
has just got shorter, so do a rebalance
that operation will result in the tree

23
|
+------------+------------+
| |
12 37
| |
+-----+-----+ +-----+-----+
6 18 30 48
| | | |
+---+---+ +---+---+ +---+---+ +---+---+
| | | | | | |
4 9 14 20 33 42 50
| | | |
+--+--+ +--+-+ +--+--+ +-+--+
| | | | |
5 13 19 22 45


If you had a complex tree (!), similar effects might propagate
back to earlier levels
*/

if(r->RightLink() != NULL)
{
/* on inward recursion, chase right pointers */
Del(t,r->RightLink());

/* and when unwinding recursion do rebalancing */
if(fResizing == CHANGED_SIZE)
Check_balance_after_Right_Delete(r);
}
else
{
AVLTreeNode *x;

/* this is code that "promotes" the node
* copying data from 23 of example into original 25 record
*/
t->Replace(r->Data());
x = r; /* keep pointer to tree-node that is being unlinked */

/* unlinking 23 (if 23 had had a left, e.g. a 22.5 entry,
* this would become 22's right)
*/
r = r->LeftLink();
fResizing = CHANGED_SIZE;

/* and get rid of the node that had the 23 */
delete x;
}
}
</font><hr></pre></blockquote>

bakunin
Posts: 597
Joined: 16. Aug 1999 6:44
Location: Lorsch (Südhessen)
Contact:

Re: Elemente aus binären Bäumen löschen

#8 Post by bakunin »

Hi!

Marc schrieb:
> Wieso meintest Du, daß der Baum falsch konzipiert war?

Weil meine ursprüngliche Idee, die ja nicht richtig war, mit meinem Baum dennoch funktioniert. Ich wollte eigentlich einen Baum verwenden, an dem mein falsches Verfahren scheitern würde. So meinte ich das.

> Dieses Vorgehen ist zwar etwas aufwendiger, aber dafür erhält man auch einen etwas ausgeglicheneren Baum mit einer geringeren Tiefe

Das erreichte Resultat ist sehr gut, aber bei einem riesigen Baum dauert das vermutlich ewig. Gibt's nicht noch ein Verfahren, das die Vorteile von beiden vereinigt? <img src="http://www.pl-forum.de/UltraBoard/Images/Wilk.gif" border="0" align="middle">

Descartes schrieb:
> Warum nicht die GNU libavl verwenden ?

Die Idee, eine Bibliothek zu verwenden, missfällt mir in dem konkreten Fall ein wenig, weil mein Code selbst eine Bibliothek ist, die eben unter anderem auch so etwas anbietet bzw. in erster Linie intern verwendet. Ich möchte wenigstens die Abhängigkeiten von Bibliotheken zu zusätzlichen Bibliotheken gering halten. Viele Leute machen sich nunmal in der Praxis nicht die Mühe, erst Bibliothek A zu compilieren, um dann Bibliothek B compilieren zu können, die von Programm C erfordert wird. Aber etwas Code von anderswo einzubauen ist eine gute Idee. Ich sauge mir das gleich mal.

> (if its got left children then substitute them at point where 23 used to hook in)

Ah, darauf war ich auch nicht gekommen, obwohl das recht naheliegend ist. Mit dieser Änderung funktioniert mein erster Ansatz dann auch.

Gerade hatte mein Code wenigstens korrekt funktioniert. Jetzt muss ich nochmal einiges neuschreiben. Ihr seid schuld. <img src="http://www.pl-forum.de/UltraBoard/Images/Wilk.gif" border="0" align="middle">

Cheers,
GNU/Wolfgang

Post Reply