2-3 drzewo

2-3 drzewo – struktura danych będąca 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łek z 2 następnikami
wierzchołek z 3 następnikami

Wierzchołki wewnętrzne

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ż

Linki zewnętrzne

Wizualizacja 2-3 drzewa (ang.)
2-3 Drzewa opis (ang.)