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– Pseudonym ♦2016年04月01日 01:10:19 +00:00Commented 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– David Richerby2016年04月01日 04:09:41 +00:00Commented 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– vonbrand2020年02月12日 22:58:21 +00:00Commented 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.
Explore related questions
See similar questions with these tags.