In the original “Balanced Search Trees Made Simple” paper by Arne Andersson, the first paragraph of the second chapter mentions that a single bit could be the flag before introducing the traditional integer level tracking. Does anyone know what the single-bit version would look like? How would insertion, deletion, skewing, and splitting work?
1
If you use a single bit — conventionally colored red or black — then the level of a red node is the same as the level of its parent, and the level of a black node is one less than the level of its parent. You don’t need absolute levels — only relative levels — so that’s enough in theory.
How would insertion, deletion, skewing, and splitting work?
Insertion is pretty straightforward. You’ll want two functions:
- A recursive helper function that inserts a node into a subtree and preserves the level of its root node (with the consequence that the root node may need to be red).
- A top-level ‘Insert’ function that delegates to the recursive helper, and then paints the root node black.
Deletion, however, is a mess. The issue is that a subtree may become shorter, and that can’t be expressed in the node itself, so it needs to return that information to the caller, which then has to do a whole bunch of bookkeeping. It’s 100% doable, but why would you want to?
Skewing and splitting are theoretically straightforward, but not actually relevant: those functions are just there to help implement insertion and deletion (they’re not intended to be called directly by the code that uses the tree), and they end up not being very useful (because the bookkeeping in deletion requires much more context than a single node).