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