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?

Improve this question
$\endgroup$
3
  • $\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, 2016 at 1:10
  • 1
    $\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, 2016 at 4:09
  • $\begingroup$ Red-black trees are one way of building (abstract) 2-3 trees, essentially B-trees with at most 3 children for each node. $\endgroup$
    – vonbrand
    Feb 12, 2020 at 22:58

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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