One advantage claimed for scapegoat trees over other balanced trees like AVL or red-black(RB trees - just mentioning AVL henceforth) is not needing to store additional balance information.
But can't an AVL tree node do without additional storage for balance information?
(I'm not considering possibilities to hide it in "the payload" (item, considered "immutable for the tree handling").)
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
One frequent characterisation of the storage for the balance information for an AVL tree node (henceforth node) is 2 bits:
either for balance factors (differences between children's heights) of -1, 0, or 1,
or leftIsTaller&rightIsTaller.
More than half the nodes being leaves, it is possible to reduce this to one bit:
The balance of nodes with less than two children is obvious; for two children, push down the bits left&right.
Customarily, AVL trees are described (&implemented) with targeted access to each child as left or right child.
Keeping that, it should be possible to encode one bit in either having the children in their proper place as implied by key order, or exchanged.
There would seem to be a problem with leaves, but those can be detected to be leaves in constant time, the parent leaning their way if there is no sibling; the sibling's way if that is not a leaf.
(The implementation for "0-overhead (balanced) trees" haunting me being
two maps from parent item to left child item and right.)
-
$\begingroup$
targeted access to each childcustomarily, "we" think ordered tree without mention. $\endgroup$ Nov 1, 2021 at 6:21 -
$\begingroup$ More useful questions may include: What, usually, is "stored in that bit"? Well, the result of comparing left to right. When is it useful to store the (non-local) balance information instead of order? Whenever in the use of the tree this promises to reduce cost. Even analysing just look-up cost, the effects of different representations are hard to assess. $\endgroup$ Nov 1, 2021 at 10:09
-
$\begingroup$ Accept your own answer otherwise it will keep popping forever looking for an answer. $\endgroup$– S. M.Jul 16 at 17:10
-
$\begingroup$ (@AlokMaity: never noticed, the one tag I'm watching is algorithms.) $\endgroup$ Jul 16 at 19:02