BB[alpha] Tree Traversal

Algorithm description

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

Algorithm implementation

 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;

Notes on design

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.

Worst Case Performance

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.

Selected Bibliography

[Bli94, section 6.2.2] [Meh84, p. 189] [Ott93, p. 328]

[ Samples Overview | Bibliography | WOOP Project ]