Typ danych to zbiór wartości oraz operacji, jakie można na nich wykonać. Struktura danych to mechanizm organizacji informacji zapewniający wygodne i efektywne sposoby dostępu do nich i ich przetwarzanie. Klasyczne struktury danych to
Tablice są sztywnym zbiorem danych tego samego typu, zapisanych w jednym ciągu w pamięci i dostępnych za pośrednictwem indeksu. Do i-tego elementu tablicy A można się odwołać za pomocą konstrukcji A[i]. Dostęp do każdego elementu tablicy jest tak samo szybki. Dozwolone indeksy zwykle zaczynają się od zera (C/C++, Python) lub od jedynki (Pascal).
W języku C mianem ciągu znaków (łańcucha znaków, napisu, stringu) określa się tablicę znaków o zmiennej długości. Koniec napisu zaznacza się za pomocą specjalnego znaku końca ciągu ('\0'). W Pythonie typ string jest typem wbudowanym, a napisy są niezmienne i mają określone pewne działania. W innych językach mogą występować inne implementacje. Typowe operacje na stringach: wyznaczanie długości stringu, kopiowanie stringu, porównywanie leksykograficzne, sklejanie stringów. Stringi są użyteczne, ponieważ wiele aplikacji przetwarza dane tekstowe, a ponadto stringi są zwykle efektywnie realizowane w systemach komputerowych.
Lista połączona jest to zbiór elementów, z których każdy jest zawarty w węźle, zawierającym dodatkowo łącze do innego węzła. Jedynym sposobem dostania się do konkretnego elementu listy jest przejście przez listę od jej samego początku. Ostatni węzeł listy możemy oznaczyć za pomocą pustego łącza, węzła-atrapy, węzła wskazującego pierwszy element listy (lista cykliczna), itp. Węzły listy (wszystkie na liście jednocześnie) mogą posiadać więcej niż jedno łącze. W listach połączonych podwójnie każdy węzeł posiada łącza do elementu poprzedniego i następnego.
Drzewo jest niepustym zbiorem węzłów i krawędzi, spełniającym pewne wymagania. Wierzchołek (węzeł) jest obiektem prostym, który może przechowywać pewne dane. Krawędź to element łączący dwa wierzchołki. Ścieżka jest listą różnych wierzchołków, w której kolejne wierzchołki są połączone krawędziami. W drzewie dwa dowolne węzły łączy dokładnie jedna ścieżka. W przeciwnym razie mamy do czynienia z grafem, który nie jest drzewem.
Drzewo z korzeniem to takie drzewo, w którym jeden z węzłów oznacza się jako korzeń. W informatyce termin drzewo zwykle oznacza drzewo z korzeniem. Zwykle drzewa z korzeniem rysuje się tak, aby korzeń znajdował się najwyżej. Nad każdym węzłem (oprócz korzenia) znajduje się dokładnie jeden węzeł, zwany ojcem (rodzicem). Węzły znajdujące się bezpośrednio pod danym węzłem nazywamy dziećmi (potomkami). Węzły, które nie mają potomków, nazywane są liśćmi lub węzłami końcowymi.
W drzewie uporządkowanym (z korzeniem) kolejność potomków każdego węzła jest ściśle określona. Drzewo, w którym każdy węzeł musi mieć określoną liczbę potomków uporządkowanych w określony sposób, nazywane jest m-drzewem. Przykłady: drzewa binarne, drzewa trójkowe. W dalszych rozważaniach skupimy się na drzewach binarnych.
Zastosowania struktur drzewiastych:
Przykładowe drzewa:
Algorytm DSW (Day, Stout, Warren, 1986) jest to algorytm równoważący BST [Wikipedia].