Schiefe Bäume Bezug zu Binary Search Tree
Ich weiß was Binäre Suchbaum ist und ich weiß, wie Sie funktionieren. Aber was braucht es, damit sich eine schiefe Baum? Was ich meine ist, tun alle Knoten haben, um zu gehen auf eine Seite? oder gibt es irgendeine andere Kombination?
Dass ein Baum in dieser Form (siehe unten) ist der einzige Weg, um es der schiefe Baum? Wenn nicht, was sind andere mögliche schiefe Bäume????
Schiefe Baum Beispiel:
Auch, ich suchte aber nicht finden konnte, eine gute und solide definition einer Schiefen Baum. Hat jemand eine gute definition?
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
Heraus, eine schiefe Baum ist der Schlimmste Fall von einem Baum.
`
Die Anzahl der Permutationen von 1, 2, ... n = n!
Die Anzahl der BST-Formen: (1/n+1)(2n!/n!n!)
Die Anzahl der schiefe Bäume 1, 2, ....n = 2^(n-1)
`
Hier ist ein Beispiel, das ich gezeigt wurde:
http://i61.tinypic.com/4gji9u.png
Eine gute definition für eine skew-Baum ist ein binärer Baum, so dass alle Knoten bis auf einen haben nur ein Kind. (Die übrigen Knoten hat keine Kinder.) Eine weitere gute definition ist ein binärer Baum mit n Knoten, so dass seine Tiefe n-1.
Einen binären Baum, der beherrscht wird ausschließlich durch das linke Kind von Knoten oder rechten Kind-Knoten, wird als eine schiefe binären Baum, genauer gesagt Links verzerrt binären Baum oder rechts schief binären Baum.