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?

  • $\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
    Commented 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$ Commented 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
    Commented Feb 12, 2020 at 22:58

1 Answer 1


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.


Your Answer

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

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