3
$\begingroup$

A B-tree is kept balanced (i.e. all leaves at same depth) by splitting a node when adding a child that won't fit, and propagating this splitting up to the root.

Can the same technique be used to keep a regular binary search tree balanced (since a binary search tree can be viewed as a 2 child maximum B-tree)? If so, does that rebalancing method have a name, and what are its advantages/disadvantages to other ways of keeping a BST balanced, such as Red-Black trees?

$\endgroup$
  • $\begingroup$ In a sense, red-black trees do work on precisely that principle. (The sense is that red-black trees are just an alternative way to implement 2-3-4 trees.) $\endgroup$ – Pseudonym Apr 1 '16 at 1:10
  • $\begingroup$ I'm not sure what you're asking. A "regular binary search tree" doesn't have any balancing mechanism; as soon as you add such a mechanism, it's not a regular binary search tree" any more -- it's a something-something balanced binary search tree. $\endgroup$ – David Richerby Apr 1 '16 at 4:09
2
$\begingroup$

1-2 Brother Trees, as in "Purely Functional 1-2 Brother Trees" by Ralf Hinze in some way allow splitting a node. Like in 2-4 trees where nodes have 2 to 4 children, in 1-2 brother trees, nodes have 1 to 2 children.

The advantages are a bit hand-wavey: it is sometimes faster, and sometimes simpler, and sometimes uses less space.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.