Balanced search tree

This page explains the details of balanced search tree data structure used by Delaunay triangulation.

Background

Reference:CMU CS leture notes

Definition 1

A dictionary data structure is a data structure supporting the following operations:

* insert(key, object): insert the (key, object) pair. For instance, this could be a word and its definition, a name and phone number, etc. The key is what will be used to access the object.

* lookup(key): return the associated object.

* delete(key): remove the key and its object from the data structure. We may or may not care about this operation.

Definition 2

Balanced search tree is a kind of dictionary data structure that allows to perform these operations in time O(log n).

Definition 3

A B-tree is a search tree where for some pre-specified t ≥ 2 (think of t = 2 or t = 3):

* Each node has between t − 1 and 2t − 1 keys in it (except the root has between 1 and 2t − 1 keys). Keys in a node are stored in a sorted array.

* Each non-leaf has degree (number of children) equal to the number of keys in it plus 1. So, node degrees are in the range [t, 2t] except the root has degree in the range [2, 2t]. The semantics are that the ith child has items between the (i − 1)st and ith keys. E.g., if the keys are [a1, a2, . . . , a10] then there is one child for keys less than a1, one child for keys between a1 and a2, and so on, until the rightmost child has keys greater than a10.

* All leaves are at the same depth.

Definition 4

The rules for lookup and insert for B-trees:

* Lookup: Just do binary search in the array at the root. This will either return the item you are looking for (in which case you are done) or a pointer to the appropriate child, in which case you recurse on that child.

* Insert: To insert, walk down the tree as if you are doing a lookup, but if you ever encounter a full node (a node with the maximum 2t − 1 keys in it), perform a split operation on it (described below) before continuing. Finally, insert the new key into the leaf reached.

* Split: To split a node, pull the median of its keys up to its parent and then split the remaining 2t − 2 keys into two nodes of t − 1 keys each (one with the elements less than the median and one with the elements greater than the median). Then connect these nodes to their parent in the appropriate way (one as the child to the left of the median and one as the child to its right). If the node being split is the root, then create a fresh new root node to put the median in.

 Here is an example of B-tree with t=2.

                                        [ROOT]
                                       {   5  } 
               [LV1](x<5)                                      [LV1](x>5)  
            {   1  3  4  }                                    {    8  9   }
 
 Suppose we want to insert "2" into this B-tree.
 After comparing "2" with "5", we decided to put it into left side child LV1. 
 But it is full(n=3) now. So we need to perform a "split" to maintain balance of the tree.
 "Split" is done like this:
 
                                         [ROOT]
                                       {  3  5  } 
             [LV1](x<3)               [LV1](3<x<5)                   [LV1](x>5)  
            {   1  2  }                {   4   }                   {    8  9   }

 Suppose we want to insert "5.5" into the B-tree, it will become like this:

                                         [ROOT]
                                       {  3  5  } 
             [LV1](x<3)               [LV1](3<x<5)                   [LV1](x>5)  
            {   1  2  }                {   4   }                   {  5.5  8  9   }

 Then insert "6", one more "split" will be performed to the right-most child.

                                         [ROOT]
                                       {  3  5  8 } 
         [LV1](x<3)           [LV1](3<x<5)      [LV1](5<x<8)              [LV1](x>8)  
        {   1  2  }            {   4   }          {5.5   6}               {  8  9   }

 Further insert "4.5" & "3.5", we have

                                          [ROOT]
                                       {  3  5  8 } 
         [LV1](x<3)           [LV1](3<x<5)           [LV1](5<x<8)              [LV1](x>8)  
        {   1  2  }          { 3.5  4  4.5 }          {5.5   6}               {   9   }

 Now if we want to insert "4.8", we will find that both LV1 child and the root are full. 
 Then we need to perform a "split" on both LV1 child and root. After this a new root is generated and the tree "grows" up.
 
                                                      [NEW ROOT]
                                                       {  5  }                                    
                                [LV2](x<5)                                       [LV2](x>5)
                                 { 3  4 }                                          {  8  } 
         [LV1](x<3)     [LV1](3<x<4)         [LV1](4<x<5)                [LV1](5<x<8)            [LV1](x>8)  
        {   1  2  }       { 3.5  }         {   4.5  4.8  }                {5.5   6}              {    9   }

 Keep inserting like this, we will have a "growing" tree with balanced depth.

Module structure

The balanced search tree structure is implemented inside C/C++ standard template library (STL) in forms of std::set and std::map. For details on how to use these data structures in C/C++, please refer to relevant programming guides.

Delaunay triangulation makes use of such data structures to store information like vertices and triangles. The function that actually calculates triangulation is implemented in C++ and can be called from FreeFlex main program through a FORTRAN/C++ interface.