2-3-copac

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 12 iunie 2014; verificările necesită 14 modificări .

2-3 arbore - structură de date , care este un arbore B , fiecare nod (pagină) având fie doi copii și un câmp, fie trei copii și două câmpuri. Nodurile frunzelor sunt o excepție - nu au copii, ci unul sau două câmpuri. 2-3 copaci sunt echilibrați, adică toate vârfurile frunzelor sunt la aceeași înălțime față de rădăcina copacului.

2-top
3-top

Proprietăți

Toate vârfurile care nu sunt frunze conțin un câmp și 2 subarbori sau 2 câmpuri și 3 subarbori.
Toate vârfurile frunzelor sunt la același nivel (nivel de jos) și conțin 1 sau 2 câmpuri.
Toate datele sunt sortate (după principiul unui arbore de căutare binar ).
Un câmp într-un vârf de 2, ca într-un arbore de căutare binar, împarte spațiul valorilor posibile în două intervale: și $(-\infty ,a)$ $[a,+\infty )$
Câmpurile din cele 3 vârfuri împart spațiul valorilor posibile în trei intervale: , și $(-\infty ,a)$ $[a, b)$ $[b,+\infty )$

Vârfurile non-frunze

Nodurile non-frunze conțin unul sau două câmpuri care indică intervalul de valori din subarborele lor. Valoarea primului câmp este strict mai mare decât cea mai mare valoare din subarborele din stânga și mai mică sau egală cu cea mai mică valoare din subarborele din dreapta (sau subarborele central dacă este un 3-vertex); de asemenea, valoarea celui de-al doilea câmp (dacă există) este strict mai mare decât cea mai mare valoare din subarborele central și mai mică sau egală cu cea mai mică valoare din subarborele din dreapta. Aceste vârfuri non-frunze sunt folosite pentru a direcționa funcția de căutare către subarborele dorit și, eventual, către frunza dorită.

De exemplu, pentru a ilustra cele de mai sus, sunt valabile următoarele inegalități:

pentru 2 vârfuri: $p<a\leq q$
pentru 3 vârfuri: $p<a\leq q<b\leq r$

Vezi și

B-arborele
Lista structurilor de date (arbori)

Link -uri

Arborele (structura de date)
Arborele de căutare binar Arborele (teoria graficelor) structura arborelui
Arbori binari	arbore binar T-tree
Arbori binari cu auto-echilibrare	arbore AA arborele AVL Copac roșu-negru Splay arbore copac cu amenzi arbore cartezian Arborele Fibonacci B-arborele T-tree
B-copaci	2-3-copac B⁺-arborele B*-copac B x -arbore arborele UB 2-3-4 arbore (a,b)-copac copac dansant
arbori de prefix	arbore de sufix Arborele de prefix comprimat Arborele de căutare ternar
Partiționarea binară a spațiului	arbore k-dimensional arborele VP
Arbori non-binari	Quadtree octree Voxel rar Octree arbore exponenţial Arborele PQ
Despărțirea spațiului	R-arborele Arborele R Hilbert R+-arborele R*-copac X-arborele M-arbore Arborele Fenwick Arborele segmentului
Alți copaci	morman arbore de hash arborele degetelor arbore metric Arborele de acoperire BK-arborele Copac cu lanțuri duble iDistanța Arbore tăiat de legături Arborele LSM
Algoritmi	Lățimea prima căutare Profunzime prima căutare Algoritmul DSW protocolul spanning tree