Question on binary search Trie

Hello, I'm reading a paper that refers to using a (Digital) Binary
Search Trie to map keys into a table full of buckets. The trie is
comprised of the bits of the key (in reverse order). It is intended
to easily support manipulation of the "buckets" in the table (addition/
removal). My question refers to rebalancing the trie on removal of
nodes. I'll provide an example below (unfortunately, I have trouble
documenting tries in messages so forgive any formatting issues).

Given the following binary keys, their bucket mapping, and values
contained in said bucket.

00->Bucket A->gary, lori
01->Bucket B->kim

* (root)
0 (parent)
0 (A:gary, lori) 1 (B:kim)

Here the removal of gary or kim would promote the other bucket to the
parent (0) node and thus any searches (or insertion) for gary, lori or
kim will still work correctly and refer to the newly promoted bucket
since all keys share the 0th LSB. This I understand. It is when the
trie is deeper that is causing me confusion. Following the same
example, let's add more values


00->Bucket A->gary, lori
010->Bucket B->kim
011->Bucket C->tom

*
0 (parent) 1 (Z)
0(A) 1
0(B) 1(C)

Again, appologies for any misformatting on the trie. So what happens
here when we remove Bucket A? Do both Bucket B and C (and any of
their children) get promoted to parent 0 since they only share the 0
LSB with A? Thus:

*
0 (B,C, {all children of B&C}) 1 (Z)

Is this correct?

TIA



.

Relevant Pages

  • Re: Unable to debug Perl script
    ... through all the keys in the bucket looking for one that matches. ... Obviously, for efficiency, you want this final linear scan to be as ... Presumably the hash function was tweaked in 5.8, ...
    (comp.lang.perl.misc)
  • RMS indexed file structure questions
    ... When a record is deleted from a bucket, is the space occupied by the records zeroed or doe the record remain there intact, with only the index areas updated? ... When a record is delete from a bucket, would records stored after the deleted record in a bucket be shiften to the "left" by the length of the deleted record? ... It consists of the 65 byte keys with no separators between the keys. ...
    (comp.os.vms)
  • Re: authentication / encryption key retention
    ... Each persona would then have an identity (UID) and a sequence of keys. ... particular bucket because you identified yourself to it can invalidate ...
    (Linux-Kernel)
  • Re: "ndbm store" error on Solaris
    ... > of EFBIG or ENOSPC when too many keys hash to the same bucket. ... I hit this problem years ago after dumping an ndbm database to ...
    (comp.unix.solaris)