Talk:Self-balancing binary search tree

From formulasearchengine
Jump to navigation Jump to search

Template:WikiProject Computing Template:WikiProject Computer science


Is a B-Tree a binary tree? Doesn't a binary tree only allow two connections from it, while a B-Tree can have a lot more.

A B-tree is certainly not a binary tree. I have no idea when that link snuck in. Away with it! Deco 02:41, 6 Apr 2005 (UTC)


The overview states that

(log-base2(n+1) - 1) >= log-base2(n)

How can this be? Am I missing something? Seems to me it should be less than or equal, not greater than or equal. E.g., if n=1 (no children), then log-base2(1 + 1) - 1 = 0 = log-base2(1) ... so in that case they are equal. But in any other case, the left hand side is smaller. E.g., let's say n=7:

log-base2(7+1) - 1 = 2 < log-base2(7)

Right?? Mike Williamson 2013/6/3 —Preceding undated comment added 22:46, 3 June 2013 (UTC)

the formula is wrong

for example, n:=8, the left is 2, the right is 3. --User:Newmangling 2013/11/22 comment added 04:37,(UTC)

Ordered lists

The link to ordered lists goes to a page about HTML markup!

Presumably there's a better destination for it... does anyone know of one? (talk) 11:00, 27 November 2007 (UTC)


That section should mention the differences between the various algorithms, which ones are good, which ones aren't, and which perform better in certain situations. Shinobu (talk) 03:14, 7 December 2007 (UTC)

Good idea, this is an appropriate article for comparison. Dcoetzee 03:32, 7 December 2007 (UTC)

Proof of min size

I appreciate the work that went into typing the proof of the minimum tree height. That proof would be fine in a textbook, but unfortunately Wikpedia is not a textbook; its articles are not supposed to include proofs, over-justify statements, or over-explain examples. Sorry, and all the best, --Jorge Stolfi (talk) 02:27, 11 August 2009 (UTC)

There are a lot of proofs on Wikipedia. Are they really not allowed? What about if the proof only showed if you clicked a link saying 'show proof' or something? Strict rule-following should be weighed carefully against usefulness.Blackspotw (talk) 16:46, 20 May 2010 (UTC)
I think proofs are fine. They are certainly encyclopedic if they come from a reliable source. There's nothing in WP:NOT that would suggest otherwise as far as I can tell. -- intgr [talk] 18:44, 20 May 2010 (UTC)
See Category:Articles containing proofs (there are 379 of them). There is the question of how useful this proof is here - is it too verbose? Depends on the reader. Dcoetzee 18:57, 20 May 2010 (UTC)

Is a splay height balanced?

In the first part of this article it reads: "a self-balancing (or height-balanced) binary search tree is any binary search tree data structure that automatically keeps its height" a splay tree is listed in this article as a tree that fits this description. however I do not believe that a splay tree is height balanced. I'm new to this so maybe someone whos better ith this topic could fix the article if it is incorrect, I'm just studying for a test, so I am not certain enough to edit this. DriverChief (talk) 21:30, 16 December 2009 (UTC)