Drzewo czerwono-czarne

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Drzewo czerwono-czarne – rodzaj samoorganizującego się binarnego drzewa poszukiwań - struktury danych stosowanej w informatyce najczęściej do implementacji tablic asocjacyjnych. Została ona wynaleziona przez Rudolfa Bayera w 1972 roku, który nazwał je symetrycznymi binarnymi B-drzewami. Współczesną nazwę oraz dokładne zbadanie ich właściwości zawdzięcza się pracy "A dichromatic framework for balanced trees" z 1978 roku autorstwa Leo J. Guibasa oraz Roberta Sedgewicka.

Struktura danych (ang. data structure) - sposób uporządkowania informacji w komputerze. Na strukturach danych operują algorytmy.Rotacja drzewa – w informatyce operacja polegająca na lokalnej zmianie struktury binarnego drzewa poszukiwań (BST) z zachowaniem porządku wierzchołków. Rotacje stosuje się w drzewach BST do uzyskania wyważenia drzewa i minimalizacji jego wysokości, co prowadzi do zmniejszenia kosztu operacji na drzewie.

Drzewa czerwono-czarne są skomplikowane w implementacji, lecz charakteryzują się niską złożonością obliczeniową elementarnych operacji, takich jak wstawianie, wyszukiwanie czy usuwanie elementów z drzewa.

Problem[ | edytuj kod]

Podstawowe binarne drzewo poszukiwań pozwala na szybkie wyszukiwanie porównywalnych danych, np. liczb dzięki zorganizowaniu ich w formę drzewa binarnego, przez co czas wykonywania elementarnych operacji jest uzależniony od średniej głębokości h takiego drzewa i wynosi O(h) . Jednak drzewo takie nie posiada żadnych mechanizmów, które dążą do jego zrównoważenia, przez co nietrudno jest uzyskać słabo rozgałęzioną strukturę o dużej głębokości. Czas wykonywania operacji będzie wtedy niewiele lepszy, niż dla zwykłych list.

Tablica asocjacyjna (tablica skojarzeniowa, mapa, słownik, ang. associative array, map, dictionary) – nazwa dla powszechnie stosowanego w informatyce abstrakcyjnego typu danych, który przechowuje pary (unikatowy klucz, wartość) i umożliwia dostęp do wartości poprzez podanie klucza.Informatyka – dyscyplina nauki zaliczana do nauk ścisłych oraz techniki zajmująca się przetwarzaniem informacji, w tym również technologiami przetwarzania informacji oraz technologiami wytwarzania systemów przetwarzających informację. Początkowo stanowiła część matematyki, później rozwinęła się do odrębnej dyscypliny – pozostaje jednak nadal w ścisłej relacji z matematyką, która dostarcza informatyce podstaw teoretycznych.

Drzewo czerwono-czarne jest rozszerzeniem podstawowej struktury o algorytm równoważenia wykonywany po każdej operacji INSERT oraz DELETE. W przypadku tej struktury elementy-liście nie przechowują żadnych informacji, dlatego często w ich miejsce wprowadza się dla zaoszczędzenia pamięci i uproszczenia kodu pojedynczego wartownika.

Wartownik w informatyce jest stosowany do przyspieszania operacji m.in. na tablicach, listach, drzewach. Nazwa ta odnosi się do specjalnego rodzaju obiektu, oznaczającego koniec struktury danych. W listach i drzewach implementowanych za pomocą wskaźników wartownikiem jest często wskaźnik pusty. W wielu językach programowania łańcuchy znaków są zakończone wartownikiem – znakiem o kodzie 0.Binarne drzewo poszukiwań (ang. Binary Search Tree (BST)) – dynamiczna struktura danych będąca drzewem binarnym, w którym lewe poddrzewo każdego węzła zawiera wyłącznie elementy o kluczach nie większych niż klucz węzła a prawe poddrzewo zawiera wyłącznie elementy o kluczach nie mniejszych niż klucz węzła. Węzły, oprócz klucza, przechowują wskaźniki na swojego lewego i prawego syna oraz na swojego ojca. Dla pełnego drzewa BST o n węzłach pesymistyczny koszt każdej z podstawowych operacji wynosi O(log n). Złożoność obliczeniowa jest tak niska, ponieważ operacje wykonywane są wzdłuż drzewa. Z tego samego powodu w skrajnym przypadku, gdy drzewo składa się z jednej gałęzi koszt ten wzrasta do O(n). W literaturze często też podaje się koszt wykonania operacji w uzależnieniu od wysokości drzewa h - wynosi on O(h). Przechodząc drzewo metodą in-order, uzyskuje się ciąg wartości posortowanych niemalejąco.


Podstrony: 1 [2] [3] [4]




Warto wiedzieć że... beta

Drzewo splay (drzewo rozchylane) – w informatyce – struktura danych w formie samodostosowującego się drzewa poszukiwań binarnych, wynaleziona przez Daniela Sleatora i Roberta Tarjana, reprezentująca zbiór elementów z porządkiem liniowym.

Reklama