BIND 10 #2838: Use AVL tree instead of red-black tree in DomainTree

[BIND 10 Development]

#2838: Use AVL tree instead of red-black tree in DomainTree
-------------------------------------+-------------------------------------
                   Reporter:  muks   |                 Owner:
                       Type:         |                Status:  new
  enhancement                        |             Milestone:  Next-Sprint-
                   Priority:         |  Proposed
  medium                             |              Keywords:
                  Component:  data   |             Sensitive:  0
  source                             |           Sub-Project:  DNS
               CVSS Scoring:         |  Estimated Difficulty:  0
            Defect Severity:  N/A    |           Total Hours:  0
Feature Depending on Ticket:         |
        Add Hours to Ticket:  0      |
                  Internal?:  0      |
-------------------------------------+-------------------------------------
 Aside from the better lookup performance that AVL trees have over red-
 black trees (at the expense of slower insert time), an implementation to
 delete nodes from the `DomainTree` when it is a red-black tree is going to
 be hairy because we no longer have a `NULL_NODE` and use NULL values
 instead.

 There are many color combination cases that we will need to handle when
 deleting from a red-black tree. Each of these will require NULL testing
 before color testing and it will make our developers lose hair each time
 they have to look at this code.

 So I propose we use an AVL tree instead of a red-black tree as the core
 data structure of the `DomainTree`. AVL trees are easier to understand,
 maintain code for, and also provide better lookup performance.

 This bug is to test performance also, when switching from red-black to AVL
 trees.

 We should implement this before #2750.

-- 
Ticket URL: <http://bind10.isc.org/ticket/2838>
BIND 10 Development <http://bind10.isc.org>
BIND 10 Development