Talk:Self-balancing binary search tree

From formulasearchengine
Jump to navigation Jump to search

Template:WikiProject Computing Template:WikiProject Computer science

tree

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)


overview

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? 84.9.75.24 (talk) 11:00, 27 November 2007 (UTC)

Implementations

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)