Binärbaum - die Theorie
-
Vielen Dank, damit wäre vorerst alles geklärt
-
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
-
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
-
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")
-
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
-
Offtopic, ich weiß, aber WTF ist ein Binärbaum?
-
Eine Datenstruktur mit einem Parent und zwei Nachfolgern. Das entscheidende ist aber eher, wie man diese Struktur verwendet
-
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.