baumtypen

DEvent

Hallo
welche baumtypen kennt ihr den so?
ich kenn Binärbaum, AVL Baum, Binären Suchbaum, 123-Bäume, 123-n-bäume
das wars eigentlich, alles aus der softwaretechnik-vorlesung
aber es gibt sicherlich noch mehr baumtypen oder?

otze

octree ist noch sehr bekannt
der Red-Black-tree wird zb in der map verwendet

zocker001

Eine Frage hierzu:
Was sind BAUMTYPEN???

Könnt ihr mir sagen, was ihr damit meint.

mfg
zocker001

Bashar

**
NO. 1:

THE LARCH
**

DEvent

lol

baumtypen in der informatik:
ein abstrakter datentyp, der daten speichert in form eines baumdiagramms.
z.b. Binärbaum: hat eine wurzel und jeder knoten hat max. 2 unterknoten.

hm der Red-Black-tree ist doch genauso wie der AVL baum, also da gibts auch rechts/links einfach/doppelt rotationen um den zu balanzieren
ich hab mir die erklärung nur kurtz durchgelesen, wo liegt der vorteil zu dem AVL Baum ?

Birnbaum ist auch sehr wichtig.

elise

Bashar schrieb:

**
NO. 1:

THE LARCH
**

+++ schrieb:

Birnbaum ist auch sehr wichtig.

rofl

C++ Forumbot

Dieser Thread wurde von Moderator/in HumeSikkins aus dem Forum C++ in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

volkard

DEvent schrieb:

welche baumtypen kennt ihr den so?

da antworte ich mal nicht.

ich kenn Binärbaum, AVL Baum, Binären Suchbaum, 123-Bäume, 123-n-bäume
das wars eigentlich, alles aus der softwaretechnik-vorlesung
aber es gibt sicherlich noch mehr baumtypen oder?

den wichtigsten haste nicht erwähnt. den heap.
der heap ist ein binärbaum mit der integritätsbedingung, daß die kinder immer => des elternknotens sind. offensichtlich kann man extrem schnell das kleinste element finden (ist ja die root). entfernen und einfügen geht in O(log(n)). aber um konstenate faktoren schneller als bei den sortierbäumen, weil die integritätsbedingung schwächer ist. außerdem kann man den baum fein linksausgefüllt darstellen, so daß er gut lückenlos in einem array liegen kann, was nochmal heftig viel overhead spart. ich nenne ihn den wichtigsten, weil ich ihn benutze, wenn wiedermal schlimm auf performance achte. dann benutze ich eigentlich nur hashtables und heaps.

sehr wichtig sind noch Bayer-Bäume. das sind bäume mit fetten knoten. günstigerweise machen wir einen knoten 8k groß. im knoten stehen schlüssel und zeiger zu subknoten zum beispiel in nem sortierten array. und er wächst an der wurzel. details wird dir google schon erzählen. der bayer-baum ist extrem fein, wenn es daten sind, die auf dr platte liegen sollen. also perfekt für datenbanken, um richtig große tabellen zu halten. durch die breiten knoten verzweigt sich der baum ja auch sehr breit und man braucht kaum tiefe. also kaum plattenzugriffe. hashtables, die auch auf platte liegen können, sind erst bei ganz fetten tabellen (zum beispiel in der anwendung als nameserver) merklich schneller.

nicht völlig unwichtig ist noch der Parse-Baum. aber sowas meintest du hier vermutlich nicht.

baumartige datenstrukturen gibt es viel mehr, als du denkst. es gibt ja bücher, die sich unter anderem mit sowas beschäftigen. die heißen dann "Algorithmen in C" oder "Algorithmen und Datenstrukturen" oder so. und da ist es immer so, daß man ca 75% der gezeigten bäume schon aus anderen büchern kennt und 25% vorher noch nie da waren. außerdem werden jeen tag neue bäume erfunden. weil die rechner sich ändern. mit dem einführen von festplatten mußten b-bäume her und mit dem einführen von total viel multithreading mußten stratifizierte bäume her. ich hab mal einen erfunden, der in settop-boxen von phillips einsatz finden sollte. und wenn ich einen erfinden kann, dann können viele andere das auch.