[bind10-dev] Using AVL tree instead of red-black tree in DomainTree

[Michal 'vorner' Vaner]

Hello

I was always proposing to use AVL, mostly because it should be faster on lookups
in theory (strange that your results don't confirm it in the random order, but
we'll be filling our zones in sorted order most of the time, I guess). The
reason they were not used was mostly because bind9 was using red-black and it
was easy to port. So, I'm not against switching to AVL, if it should save the
amount of work we need to do. Maybe a topic for the technical call in week's
time?

Anyway, I know of yet simpler version of balanced tree, though I don't know much
about how fast it is. It is a version of BB-α tree (not the original from the
article I don't remember who wrote). Now, it works like this:
 • Each node remembers how many nodes are in the left and right tree.
 • The counts are updated during insert and delete.
 • During each update, we find the note closest to the root that is disbalanced
   by factor bigger than α (there may be none, in which case we're done).
 • If we find one, we take the whole subtree rooted at the node and copy it to
   a sorted array by walking it in in-order. Then we use the array to build a
   perfectly balanced tree and plug it in instead of the original node.

Now, this one has the disadvantage that some updates take longer (O(n)). But
that is still amortized O(log n) per update, it is much simpler to implement and
we can set how much balanced we want it (at the cost of more expensive updates,
as smaller factor means more frequent rebuilds).

With regards

-- 
Hello, I'm an extension to the infamous signature virus, called spymail.
Could you please copy me into your signature and send back what you were
doing last night between 10pm and 3am?

Michal 'vorner' Vaner
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <https://lists.isc.org/pipermail/bind10-dev/attachments/20130304/51b03ca4/attachment.bin>