2-3 drzewo

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

2-3 drzewem nazywamy strukturę danych będącą B-drzewem, w którym każdy wierzchołek z potomkami posiada albo 2 potomków i jeden element z informacją lub 3 potomków i 2 elementy z informacją. Wszystkie wierzchołki nie posiadające następników (liście) znajdują się na jednym poziomie. Informacje zachowywane są w pewnym porządku. Drzewa takie są zawsze zbalansowane, co gwarantuje logarytmiczny (względem rozmiaru) czas wykonywania podstawowych operacji (wstawianie, wyszukiwanie, usuwanie elementów).


Wierzchołki wewnętrzne[edytuj | edytuj kod]

Wierzchołki wewnętrzne mogą zawierać jedno lub dwa pola z informacją, które wyznaczają przedziały wartości w poddrzewach wierzchołka. Jeśli węzeł zawiera 2 następników, w nim samym znajdować się będzie jedno pole, jeśli 3 następników, 2 pola z informacją. Każde najbardziej lewe pole w wierzchołku wewnętrznym zawiera element z wartością większą niż wszystkie elementy w najbardziej lewym poddrzewie. Element najbardziej prawy będzie mniejszy od wszystkich w prawym poddrzewie. Natomiast (jeśli istnieje) następnik pomiędzy wartościami w węźle to jego poddrzewo będzie zawierać wartości z przedziału wyznaczonego przez informację w lewym i prawym polu wierzchołka. Celem takiego podziału jest szybkie wyszukiwanie i dostęp do elementów.

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]