Talk:Self-balancing binary search tree: Difference between revisions

Revision as of 06:09, 18 August 2016

Latest revision as of 18:45, 24 January 2024

(4 intermediate revisions by 3 users not shown)

Line 1:

{{WikiProject Computingbanner shell|class=startStart|importance=}}

{{WikiProject Computer scienceComputing|importance=mid|class=Start}}

{{WikiProject Computer science|importance=mid}}

}}

{{Broken anchors|links=

* <nowiki>[[Geometric series#Closed-form formula|2⁰+2¹+···+2^''h''&nbsp;=&nbsp;2^''h''+1−1]]</nowiki> The anchor (#Closed-form formula) has been [[Special:Diff/1129004581|deleted by other users]] before. <!-- {"title":"Closed-form formula","appear":{"revid":997328259,"parentid":997216384,"timestamp":"2020-12-31T00:41:26Z","removed_section_titles":["Formula"],"added_section_titles":["Closed-form formula"]},"disappear":{"revid":1129004581,"parentid":1129004434,"timestamp":"2022-12-23T03:31:31Z","removed_section_titles":["Closed-form formula"],"added_section_titles":[]}} -->

}}

== Missing citation on overview ==

The overview claims that "Maintaining the height always at its minimum value <math>\lfloor\log_2 n\rfloor</math> is not always viable; it can be proven that any insertion algorithm which did so would have an excessive overhead." with a missing citation. I believe this statement is incorrect. I sketched up a proof of a data structure that contains a sorted list backing it, which produces a perfectly height-balanced binary search tree with O(log-base2(n)) worst-case insertion time. This is as good as the insertion time for an AVL tree, so "excessive overhead" implying a slow runtime isn't right.

I followed one of the provided citations to The Art of Computer Programming Volume 3 (Donald Knuth), and on page 476, there is the following quote: "However, it appears that the bookkeeping required for maintaining the weight balance takes more time than Algorithm A [which is similar to an AVL tree]". I think the intended meaning of this is NOT that the asymptotic runtime is greater than O(<math>\log_2 n</math>); instead, that the multiplicative factor on maintaining a perfectly balanced BST is possibly higher, and the code complexity increases. Based on the data structure I sketched, there is an additional overhead in maintaining the weight balance (left and right weight) plus the neighbor nodes (two pointers; can be simplified to a single RANK field + a lookup, as in Knuth's book) per every node. This is in contrast to the AVL tree's two bits for left/right balance per node.

I propose that the line in question is changed to not state that it's impossible to maintain such a structure without sacrificing performance; instead, it should say something like

"While it is possible to maintain a BST with minimum height with the expected log(n) operations (insertion/deletion/search), in practice, the additional space requirements required to maintain such a structure outweigh the decrease in search time. An AVL tree is guaranteed to be within a factor of 1.44 of the optimal height [cite Knuth here] while requiring only two additional bits of storage in a naive implementation." An additional note can be made that AVL trees tend to come even closer to the optimal height on average. Knuth, on page 468 of the same book, stated that empirical results show that the multiplicative factor is as low as 1.01 for large N.

[[User:Rushingseas8|Rushingseas8]] ([[User talk:Rushingseas8|talk]]) 17:36, 8 March 2019 (UTC)

==tree==