R-arborele | |||||||
---|---|---|---|---|---|---|---|
Tip de | Arborele multidimensional Arborele de căutare binar | ||||||
Anul inventiei | 1984 | ||||||
Autor | Antonin Guttman | ||||||
Complexitatea în simbolurile O | |||||||
|
|||||||
Fișiere media la Wikimedia Commons |
R-tree ( Eng. R-trees ) este o structură de date asemănătoare arborelui ( arbore ), propusă în 1984 de Antonin Guttman . Este similar cu un arbore B , dar este folosit pentru a accesa date spațiale, adică pentru a indexa informații multidimensionale , cum ar fi datele geografice cu coordonate bidimensionale ( latitudine și longitudine ). O interogare tipică care utilizează arbori R ar putea fi: „Găsiți toate muzeele pe o rază de 2 kilometri de locația mea actuală”.
Această structură de date descompune un spațiu multidimensional într-un set de dreptunghiuri imbricate ierarhic și, eventual, care se intersectează (pentru un spațiu bidimensional). În cazul spațiului tridimensional sau multidimensional, acestea vor fi paralelipipede dreptunghiulare ( cuboide ) sau paralelotopi .
Algoritmii de inserare și eliminare folosesc aceste casete de delimitare pentru a se asigura că obiectele „închise” sunt plasate pe același vârf de frunză. În special, noul obiect va lovi vârful frunzei care are nevoie de cea mai mică expansiune a casetei sale de delimitare. Fiecare element nod frunză stochează două câmpuri de date: o modalitate de a identifica datele care descriu obiectul (sau datele în sine) și căsuța de delimitare a acestui obiect.
În mod similar, algoritmii de căutare (de exemplu, intersecție, incluziune, vecinătate) folosesc casete de delimitare pentru a decide dacă să caute la un nod copil. Astfel, majoritatea nodurilor nu sunt niciodată atinse în timpul căutării. Ca și în cazul arborilor B, această proprietate a arborilor R îi face potriviti pentru baze de date , unde vârfurile pot fi schimbate pe disc după cum este necesar.
Pentru a împărți vârfurile debordate, pot fi utilizați diverși algoritmi, ceea ce duce la împărțirea arborilor R în subtipuri: pătratice și liniare.
Inițial, arborii R nu garantau performanțe bune în cazul cel mai rău , deși funcționau bine pe date reale. Cu toate acestea, în 2004, a fost publicat un nou algoritm care determină arbori R prioritari . Se susține că acest algoritm este la fel de eficient ca și cele mai eficiente metode moderne și, în același timp, este optim pentru cel mai rău caz [1] .
Fiecare vârf al arborelui R are un număr variabil de elemente (nu mai mult de un maxim predeterminat). Fiecare element al unui vârf care nu este frunză stochează două câmpuri de date: o modalitate de a identifica vârful copil și o casetă de delimitare (cuboid) care cuprinde toate elementele acelui vârf copil. Toate tuplurile stocate sunt stocate la același nivel de adâncime, astfel încât arborele este perfect echilibrat. Când proiectați un arbore R, trebuie să setați câteva constante:
Pentru ca algoritmii să funcționeze corect, trebuie îndeplinită condiția MinEntries <= MaxEntries / 2. Nodul rădăcină poate avea descendenți de la 2 la MaxEntries. Adesea se alege MinEntries = 2, atunci sunt îndeplinite aceleași condiții pentru rădăcină ca și pentru restul vârfurilor. De asemenea, uneori este înțelept să puneți deoparte constante separate pentru numărul de puncte din vârfurile frunzelor, deoarece adesea puteți face mai multe din ele.
Construcția unui arbore R are loc, de regulă, prin apelarea în mod repetat a operației de inserare a unui element în arbore. Ideea de inserare este similară cu inserarea într -un arbore B : dacă adăugarea unui element la următorul vârf duce la un debordare, atunci vârful este împărțit. Mai jos este algoritmul clasic de inserare descris de Antonin Guttman .
Funcția de inserareSe pot folosi diferiți algoritmi pentru a separa vârfurile, acesta este unul dintre ei. Are doar complexitate liniară și este ușor de implementat, deși nu produce cea mai optimă separare. Cu toate acestea, practica arată că o astfel de complexitate este de obicei suficientă.
Uneori, în loc de un arbore R, se folosește așa-numitul arbore cR (c înseamnă clustered ). Ideea de bază este că algoritmii de grupare , cum ar fi k-means, sunt utilizați pentru a separa vârfuri sau puncte . Complexitatea k-means este, de asemenea, liniară, dar în cele mai multe cazuri oferă un rezultat mai bun decât algoritmul liniar de separare Guttman, în contrast cu care minimizează nu numai suprafața totală a plicurilor cutiilor, ci și distanța. dintre ele și zona de suprapunere. Pentru gruparea punctelor, este utilizată metrica selectată a spațiului original; pentru gruparea vârfurilor, puteți utiliza distanța dintre centrele plicurilor lor de paralelipipedi sau distanța maximă dintre ele.
Algoritmii de grupare nu țin cont de faptul că numărul de descendenți ai unui vârf este limitat de sus și de jos de constantele algoritmului. Dacă împărțirea clusterului produce un rezultat inacceptabil, puteți utiliza algoritmul clasic pentru acest set, deoarece acest lucru nu se întâmplă des în practică.
O idee interesantă este utilizarea grupării în mai multe clustere, unde mai multe pot fi mai mult de două. Cu toate acestea, trebuie luat în considerare faptul că acest lucru impune anumite restricții asupra parametrilor structurii p-tree.
Rețineți că, în plus față de arborele cR, există și arborele clR de variație bazat pe metoda de grupare, în care un algoritm iterativ pentru rezolvarea „problema de plasare” este folosit ca centru. Algoritmul are o complexitate de calcul pătratică, dar oferă construcția unor plicuri mai compacte de paralelipipedi în înregistrările de vârf ale structurii.
Căutarea într-un copac este destul de banală, trebuie doar să ții cont de faptul că fiecare punct din spațiu poate fi acoperit de mai multe vârfuri.
Acest algoritm [2] elimină o anumită intrare E din arborele R. Algoritmul constă din următorii pași:
Funcția FindLeaf
Fie T rădăcina arborelui și E intrarea dorită.
Funcția CondenseTree
Să fie ștearsă înregistrarea E din foaia L. Apoi, este necesar să se elimine nodul care mai are puține înregistrări (mai puțin decât MinEntries) și să-și mute înregistrările. Când vă deplasați în sus în arbore, dacă este necesar, ștergeți intrările (după aceleași criterii). În drum spre rădăcină, recalculați dreptunghiurile, făcându-le cât mai mici. Algoritmul este descris mai jos. Această funcție poate fi implementată și folosind recursiunea.
Arborele (structura de date) | |
---|---|
Arbori binari | |
Arbori binari cu auto-echilibrare |
|
B-copaci |
|
arbori de prefix |
|
Partiționarea binară a spațiului | |
Arbori non-binari |
|
Despărțirea spațiului |
|
Alți copaci |
|
Algoritmi |