A BB[alpha] tree is a weight-balanced tree. An introduction as well as further references can be found in the paper Discrete Loops And Worst Case Performance, section 6.2.2.
The following table shows a simple BB[alpha] tree (with alpha=1/4) and the balances of the nodes.
BB[alpha] tree | node | balance |
---|---|---|
6 | 5/8 | |
4 | 3/5 | |
11 | 2/3 | |
2 | 1/3 | |
5 | 1/2 | |
3 | 1/2 | |
8 | 1/2 |
1 function bbalpha_search (root: node_type; key: key_type) return node_type 2 is 3 node_pointer: node_type; 4 begin 5 discrete node_pointer := root 6 new node_pointer := node_pointer.left | node_pointer.right 7 with r := L -- number of leaves in the tree 8 new r = floor((1-alpha)*r) 9 loop 10 if node_pointer = null then 11 return null; 12 elsif key (node_pointer) = key_to_search then 13 return node_pointer; 14 elsif key (node_pointer) < key_to_search then 15 node_pointer := node_pointer.left; 16 else 17 node_pointer := node_pointer.right; 18 end if; 19 end loop; 20 end bbalpha_search;
The height of a BB[alpha] tree is bound as follows:
height <= ((ld L) - 1) / (- ld (1 - alpha)) + 1
where L denotes the number of leaves in the tree. We could have used the same approach as in the (natural) binary or AVL tree, where the remainder function of the discrete loop was bound by the maximum height of the tree.
By using the following properties, however we obtain a simpler remainder function (line 8):
W(pl) <= (1 - alpha) W(p)
W(pr) <= (1 - alpha) W(p)
(W(p) denotes the number of leaves of p, p is a node, pl and pr its left and right child, respectively.)
Our remainder function works on the number of leaves of the tree or subtree.
By choosing an alpha in the interval [1/4, 1-Sqrt(2)/2], we obtain a complexity of
O( log L )
where L denotes the number of leaves in the tree.
[Bli94, section 6.2.2] [Meh84, p. 189] [Ott93, p. 328]
[ Samples Overview | Bibliography | WOOP Project ]