patternMinor
Keeping a binary search tree by splitting nodes (like a B-Tree)
Viewed 0 times
keepingnodessearchsplittinglikebinarytree
Problem
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?
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?
Solution
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.
The advantages are a bit hand-wavey: it is sometimes faster, and sometimes simpler, and sometimes uses less space.
Context
StackExchange Computer Science Q#55270, answer score: 2
Revisions (0)
No revisions yet.