TRAKLA2

1.  let min be the minimum number of data items or children 
     allowed in a node
 2.  let max be the maximum number of data items or children 
     allowed in a node
 3.  let k be the data item to be inserted in the R-tree
 4.  let n be the root node of the R-tree
     // choose the node to insert into
 5.  while n is not a leaf node
 6.    choose the child whose corresponding area needs least 
       enlargement to include k
 7.      resolve ties by choosing the child with the 
         smallest area
 8.        resolve ties by choosing the leftmost child
 9.    let n be the chosen node
     
10.  if n is not full
11.    insert k in n
12.  else
       // split and divide the entries into the nodes
13.    split n creating a new sibling node r and
       redistribute the data stored in n among n and r while 
       trying to minimize the overlap and size of their areas
14.    if the number of data items in n is less than min
15.      insert k in n
16.    else if the number of data items in r is less than min
17.      insert k in r
18.    else
19.      insert k in n or r depending on whose corresponding 
         area needs least enlargement to include k
20.        resolve tie by choosing the node with smaller area
21.          resolve tie by choosing the node with less data
22.            resolve tie by choosing n
       // propagate a split up the tree
23.    let p be n
24.    do
25.      let p be the parent of p
26.      if the number of children in p is more than max
27.        split p creating a new sibling node r and
           redistribute the children stored in p among p and 
           r while trying to minimize the overlap and size of 
           their areas
28.      else
29.        break
30.    while p is not the root node