Binärbaum - die Theorie

Hey!

Ich wollte mich jetzt an einem Binärbaum wagen, dazu habe ich ein paar Fragen:

1.) Die std::map, ich nehme an das ist ebenfalls ein Binärbaum?

2.) Wie sieht die grobe Theorie aus? Ich weiß es gibt eine Wurzel, die ist ganz oben. Ich weiß, jeder Knoten hat max 2 Kinder. Jetzt gehts aber schon los:
auf einer Seite wurden die neuen Knoten sequentiell angehangen, von links nach rechts. Dann war ein Beispiel da wurden Integer gespeichert, die wurden gleich so gespeichert das von großen Zahlen nach kleinen vorsortiert wurde

7(wurzel)
|
|
+-
||
65

Was ist denn jetzt üblich?

3.)
Ich habe gelesen das bei Bäumen Rekursion verwendet werden soll. Geschieht das nur beim suchen?

Danke erstmal

DarthZiu

keine Ahnung
soweit ich weiß, werden die Elemente schon beim Einhängen in den Baum, sortiert, dass ist ja das schöne dran. Das bringt uns gleich zu
sämtliche Operationen auf Bäumen (suchen, einhängen, umsortieren, löschen) werden durch Rekursion realisiert

volkard

Aloha schrieb:

Hey!
Ich wollte mich jetzt an einem Binärbaum wagen,

viel spass mit zwe wochen frust. *g*
aber dafür ist die freude um so größer, wenn es klappt.

dazu habe ich ein paar Fragen:
1.) Die std::map, ich nehme an das ist ebenfalls ein Binärbaum?

ist nicht festgelegt. aber die anforderungen in sachen geschwindigkeit und so, die im standard festgelegt sind, sind so ausgelegt, daß sie mit einem binärbaum erfüllt werden können. zur zeit passt keine andere datenstruktur gut für std::map, aber es kann immer sein, daß einer eine tolle erfindet.

2.) Wie sieht die grobe Theorie aus? Ich weiß es gibt eine Wurzel, die ist ganz oben. Ich weiß, jeder Knoten hat max 2 Kinder.

ja, das sind binärbäume.

Jetzt gehts aber schon los:
auf einer Seite wurden die neuen Knoten sequentiell angehangen, von links nach rechts. Dann war ein Beispiel da wurden Integer gespeichert, die wurden gleich so gespeichert das von großen Zahlen nach kleinen vorsortiert wurde

die, die da so sortieren, nennt man auch sortierbäume. die haben den vorteil, daß man sachen sehr schnell wiederfinden kann. im allgemeinen sagt man sogar einfach "binärbaum", wenn man eigentlich "binärer sortierbaum" meint.

(dein bildchen war nicht lesbar.)

Was ist denn jetzt üblich?

am üblichsten sind binäre sortierbäume. das sind vermutlich auch die schnellsten im ram.

Ich habe gelesen das bei Bäumen Rekursion verwendet werden soll. Geschieht das nur beim suchen?

ja, das ist ein furchtbar großes problem. fakt ist: in c++ und in nicht ballancierten binären sortierbäumen soll man gar keine rekursion verwenden. für andere sortierbäume in c++ kann ich nur vermuten, aber bei solchen weiß ich es, weil ich damit experimentiert habe.
fakt ist auch: professoren wissen das meist nicht, weil sie bäume nur (aus pascal-büchern!) lesen und nicht entwickeln.
fragst du einen, der rekursion vertritt, kriegste zwei klassen von argumenten. a) es sei denkeinfacher.
b) es sei schneller.

b) ist objektiv falsch, wenn man sauber implementiert. zum beispiel fällt afair die orgie der fallunterscheidungen im remove von zwölf fällen auf vier fälle zusammen, wenn man einfach nur mal einen zeiger auf einen zeiger benutzt. man darf sich ja an die graphentheorievorlesung erinnern und sich mal einen baum als menge von knoten UND kanten vorstellen. nicht nur die knotenzentrierte sichtweise in üblichen programmierten bäumen. wenn man dann suchen mag, an welche kante ein neuer knoten gehängt werden sollte, hat man sofort zeiger auf zeiger (also zeiger auf kante und kante ist zeiger auf knoten).

allerdings wird b) wahr, wenn man ein computerlegastheniker ist.

böse zungen behaupten, das gelte auch für a).

Vielen Dank, damit wäre vorerst alles geklärt

otze

lustig wirds dann, wenn man im binärbaum sortieren will,weil man unheimlich schnell die balancierung des baums verliert, dh dass der großteil der werte auf einer seite des baums landen, was sich direkt auf die geschwindigkeit des baums auswirkt

SideWinder

otze schrieb:

lustig wirds dann, wenn man im binärbaum sortieren will,weil man unheimlich schnell die balancierung des baums verliert, dh dass der großteil der werte auf einer seite des baums landen, was sich direkt auf die geschwindigkeit des baums auswirkt

Deswegen balanciert man ihn ja auch sofort danach wieder aus - AVL-Baum lässt grüßen

MfG SideWinder

volkard

otze schrieb:

lustig wirds dann, wenn man im binärbaum sortieren will,weil man unheimlich schnell die balancierung des baums verliert,

am liebsten nehme ich nicht ballancierte bäume. nicht dieses stl-monster, was sogar aufwärts-zeiger hat.
weil ich aus der anwendung heraus garantieren kann, daß die daten "zufällig" kommen. dann hat der sortierbaum im durchschnitt gerade mal eine ebene mehr, als nötig wäre.
bitter ist das nur, wenn man sowas nicht garantieren kann. einfachstes beispiel ist wohl, daß man daten in nem baum hält für den schnellen zugriff und bei programmende per in-order-traversion abspeichert. und beim programmstart diese sortierten daten in den nicht-ballancierten baum lädt. dann hat man verloren.
ist aber kein problem, zuerst den elternknoten zu speichern und dann erst beide kinder. dann kommt der baum beim nächsten laden genauso in den speicher, wie er schon drin war. ich würde nicht verlangen, daß jeder baum gleich ein avl-baum ist. warum nicht auch mal das ballancieren total ignorieren, aber prüfen, ob der baum kollabiert ist (beim suchen zum beispiel die tiefe mitschreiben, und wenn tiefe>k*ld(anzahl) (mit k==1.5 od3r k==2), dann den ganzen baum ganz böse durchrütteln (ach, was, einfach an diesem pfad spreizen)). uih, ein spreizbaum, der nicht immer spreizt, sonder nur bei pathologischen fällen. das klingt schweineeffizient. /me hat gerade wieder was tolles erfunden. muss ich mal ausmessen, wenn ich wieder zeit hab.

was mich da interesiert

wer benutzt kommerz. Binär-Bäume?

ich meine wenn es um schnellen zugriff von daten ect. geht ( DB-Anwendugen ) nimmt man doch nicht Binär ( 2 ) sonder 400 oder so "kinder". oder liege ich da falsch?

/me hat gerade wieder was tolles erfunden. muss ich mal ausmessen, wenn ich wieder zeit hab.

Hehe, kannst es ja zur Standardisierung vorschlagen.
*auf die Knie fall vor dem Meister*

Machst du eigentlich an deinem C++ Tutorial Remake noch weiter?
(expected answer: "keine Zeit")

Cpp_Junky

newkid schrieb:

was mich da interesiert

wer benutzt kommerz. Binär-Bäume?

ich meine wenn es um schnellen zugriff von daten ect. geht ( DB-Anwendugen ) nimmt man doch nicht Binär ( 2 ) sonder 400 oder so "kinder". oder liege ich da falsch?

Ja, 400 ist schon nah dran. Genau genommen sind es 399. Man nennt das auch Mega-Tree-O-Matic und es ist affen-sau-mäßig schnell
Geht natürlich nur auf sehr schnellen Maschinen - Die langsamen Desktop Systeme müssen halt mit Binärbäumen auskommen

michaelwitzik

Offtopic, ich weiß, aber WTF ist ein Binärbaum?

Cpp_Junky

Eine Datenstruktur mit einem Parent und zwei Nachfolgern. Das entscheidende ist aber eher, wie man diese Struktur verwendet

volkard

newkid schrieb:

ich meine wenn es um schnellen zugriff von daten ect. geht ( DB-Anwendugen ) nimmt man doch nicht Binär ( 2 ) sonder 400 oder so "kinder". oder liege ich da falsch?

da liegts du richtig. aber leigen denn immer alle daten auf der platte? gibts in einem programm nur tabellen mit mehr als 10000000 einträgen? wenn ich sicher bin, daß die daten gut im ram aufgehoben sind, dann ist ein binärbaum schneller als ein bayer-baum, würde ich sagen.