Hide text Hide pseudo-code | |

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

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 |