Insert the given keys to the R-tree using the R-Tree insertion algorithm.

There are four visualizations in the exercise. On the left side there is the input stream and the corresponding area visualization. On the right side there is an R-Tree visualizaed both as an area and a tree.<7p>

The exercise is solved by dragging and dropping keys from the input stream to the tree visualization. The area visualizations are only used for illustrating the data structures.

An R-tree node can be selected by clicking it with the mouse. The selected node is highlighted in both tree and area visualizations. At the same time the Enlargement text field will show how much the selected node will be enlarged if the next input stream element is added there. The area text field tells the current area of the node.

A selected node can be split into two nodes by using the Split / Split & Insert button. If the selected node is a leaf, the next input stream element is added to one of the two newly created nodes. Splitting and internal node will not insert elements.

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