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

[Mukund Sivaraman]

Hi Jinmei

On Wed, Mar 06, 2013 at 02:09:58PM -0800, JINMEI Tatuya / 神明達哉 wrote:
> When I see the term "tree height" without a note I assume it's the
> maximum depth among all tree nodes, rather than the average.  But in
> this thread we talked about the average depth, which should matter
> more for overall average lookup performance.  Were the numbers in
> 004441 actually the average, or are you referring to something else?

With 1048576 names under '.', the average node depth is:

AVL: sorted = 19
AVL: random = 19.3788
            
RB: sorted = 19.5
RB: random = 19.4295

Node depth here is the distance between a node and the root of the tree,
where depth(root_node) = 1. getDistance() starts from 1 as there's a
lookup for the root node.

With this data about the height of the AVL trees in general, can we have
the code in #2838 reviewed to see if it is correct?

		Mukund
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 801 bytes
Desc: not available
URL: <https://lists.isc.org/pipermail/bind10-dev/attachments/20130307/1b6e19f4/attachment.bin>