Drzewo BST (binarne drzewo poszukiwań)
Ostatnia aktualizacja
Binarne drzewo poszukiwań przechowuje wartości w posortowanym porządku: dla każdego węzła wszystkie wartości w lewym poddrzewie są mniejsze, a wszystkie wartości w prawym poddrzewie większe. Aby wstawić lub znaleźć wartość, zaczynasz od korzenia i w zależności od wyniku porównania idziesz w lewo lub w prawo, więc każdy krok zmniejsza przestrzeń wyszukiwania o połowę. Kliknij odtwarzanie powyżej i zobacz, jak wartości trafiają na miejsce przez porównania, a wyszukiwanie schodzi w dół drzewa.
W zrównoważonym drzewie te operacje działają w czasie O(log n). Haczyk: wstawianie już posortowanych danych sprawia, że drzewo degeneruje się do listy jednokierunkowej z operacjami w O(n), i właśnie dlatego istnieją samorównoważące się warianty, takie jak drzewa AVL i czerwono-czarne.
Złożoność czasowa i pamięciowa
| Operacja | Zrównoważone | Najgorszy przypadek (przekrzywione) |
|---|---|---|
| Wyszukiwanie | O(log n) | O(n) |
| Wstawianie | O(log n) | O(n) |
| Usuwanie | O(log n) | O(n) |
| Pamięć | O(n) | O(n) |
Krok po kroku (wstawianie)
| Krok | Co się dzieje |
|---|---|
| 1 | Jeśli drzewo jest puste, nowa wartość zostaje korzeniem. |
| 2 | W przeciwnym razie zacznij od korzenia. |
| 3 | Jeśli wartość jest mniejsza, przejdź do lewego dziecka; jeśli większa, idź w prawo. |
| 4 | Powtarzaj, aż dotrzesz do pustego miejsca. |
| 5 | Dołącz tam nową wartość jako liść. |
Przykład krok po kroku
Wstawianie [5, 3, 8, 1, 4] do pustego drzewa, po jednej wartości:
| Wstawiana wartość | Przebyta ścieżka | Działanie |
|---|---|---|
5 | - | Drzewo jest puste, więc 5 zostaje korzeniem. |
3 | 5 | 3 < 5, idź w lewo; miejsce jest puste, dołącz 3 jako lewe dziecko 5. |
8 | 5 | 8 > 5, idź w prawo; miejsce jest puste, dołącz 8 jako prawe dziecko 5. |
1 | 5 -> 3 | 1 < 5 idź w lewo, potem 1 < 3 idź w lewo; dołącz 1 jako lewe dziecko 3. |
4 | 5 -> 3 | 4 < 5 idź w lewo, potem 4 > 3 idź w prawo; dołącz 4 jako prawe dziecko 3. |
Kiedy używać binarnego drzewa poszukiwań
| Używaj, gdy | Unikaj, gdy |
|---|---|
| Potrzebujesz porządku i szybkiego wyszukiwania, a wstawienia przychodzą w losowej kolejności. | Dane przychodzą już posortowane: niezrównoważone drzewo BST degraduje się do O(n) na operację. |
| Chcesz, aby przejście in-order za darmo zwracało wartości w posortowanej kolejności. | Potrzebujesz tylko sprawdzania przynależności bez porządku: tablica haszująca daje średnio O(1) na wyszukiwanie. |
| Potrzebujesz zapytań o zakres albo następnika lub poprzednika klucza. | Potrzebujesz gwarantowanych ograniczeń O(log n): sięgnij po samorównoważące się drzewo AVL lub czerwono-czarne. |
| Zbiór danych często się zmienia, a aktualizacja statycznej posortowanej tablicy byłaby kosztowna. | Zbiór danych jest stały i tylko do odczytu: posortowana tablica z wyszukiwaniem binarnym jest prostsza i przyjazna dla pamięci podręcznej. |
Binary Search Tree: kod
Przejrzysta, gotowa do uruchomienia implementacja algorytmu Binary Search Tree w językach: Python, JavaScript, Java, C++, C. Wybierz język, skopiuj kod albo otwórz go od razu w edytorze online Coddy.
Binary Search Tree: kod (Python)
Python
1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6
7
8def insert(node, key):9 if node is None:10 return Node(key)11 if key < node.key:12 node.left = insert(node.left, key)13 elif key > node.key:14 node.right = insert(node.right, key)15 return node # duplicates are ignored16
17
18def search(node, key):19 if node is None:20 return False21 if key == node.key:22 return True23 if key < node.key:24 return search(node.left, key)25 return search(node.right, key)26
27
28def inorder(node):29 if node is None:30 return []31 return inorder(node.left) + [node.key] + inorder(node.right)32
33
34root = None35for key in [8, 3, 10, 1, 6, 14, 4, 7]:36 root = insert(root, key)37
38print("Inorder (sorted):", inorder(root))39print("search(6): ", search(root, 6))40print("search(5): ", search(root, 5))Binary Search Tree: kod (JavaScript)
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.left = null;5 this.right = null;6 }7}8
9class BinarySearchTree {10 constructor() {11 this.root = null;12 }13
14 insert(value) {15 const attach = (node) => {16 if (!node) return new Node(value);17 if (value < node.value) node.left = attach(node.left);18 else node.right = attach(node.right);19 return node;20 };21 this.root = attach(this.root);22 }23
24 search(value) {25 let current = this.root;26 while (current) {27 if (value === current.value) return true;28 current = value < current.value ? current.left : current.right;29 }30 return false;31 }32
33 // Inorder traversal of a BST visits values in sorted order34 inorder(node = this.root, out = []) {35 if (!node) return out;36 this.inorder(node.left, out);37 out.push(node.value);38 this.inorder(node.right, out);39 return out;40 }41}42
43const bst = new BinarySearchTree();44for (const value of [8, 3, 10, 1, 6, 14, 4]) bst.insert(value);45console.log("Inorder:", bst.inorder().join(" "));46console.log("search(6):", bst.search(6));47console.log("search(7):", bst.search(7));Binary Search Tree: kod (Java)
Java
1public class Main {2 static class Node {3 int key;4 Node left, right;5 Node(int key) { this.key = key; }6 }7
8 static Node insert(Node node, int key) {9 if (node == null) return new Node(key);10 // Smaller keys go left, larger keys go right11 if (key < node.key) node.left = insert(node.left, key);12 else if (key > node.key) node.right = insert(node.right, key);13 return node;14 }15
16 static boolean search(Node node, int key) {17 if (node == null) return false;18 if (key == node.key) return true;19 return key < node.key ? search(node.left, key) : search(node.right, key);20 }21
22 static void inorder(Node node, StringBuilder sb) {23 if (node == null) return;24 inorder(node.left, sb);25 sb.append(node.key).append(" ");26 inorder(node.right, sb);27 }28
29 public static void main(String[] args) {30 Node root = null;31 int[] keys = {8, 3, 10, 1, 6, 14, 4};32 for (int k : keys) root = insert(root, k);33
34 StringBuilder sb = new StringBuilder();35 inorder(root, sb);36 System.out.println("Inorder (sorted): " + sb.toString().trim());37 System.out.println("search 6: " + search(root, 6));38 System.out.println("search 7: " + search(root, 7));39 }40}Binary Search Tree: kod (C++)
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* left = nullptr;6 Node* right = nullptr;7 explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11 if (root == nullptr) return new Node(value);12 if (value < root->value) root->left = insert(root->left, value);13 else if (value > root->value) root->right = insert(root->right, value);14 return root; // duplicates are ignored15}16
17bool contains(const Node* root, int value) {18 // Walk down: smaller goes left, larger goes right19 while (root != nullptr) {20 if (value == root->value) return true;21 root = value < root->value ? root->left : root->right;22 }23 return false;24}25
26void inorder(const Node* node) {27 if (node == nullptr) return;28 inorder(node->left);29 std::cout << node->value << " ";30 inorder(node->right);31}32
33int main() {34 Node* root = nullptr;35 for (int value : {50, 30, 70, 20, 40, 60, 80}) {36 root = insert(root, value);37 }38 std::cout << "Sorted: ";39 inorder(root);40 std::cout << "\n" << std::boolalpha;41 std::cout << "contains(40): " << contains(root, 40) << "\n";42 std::cout << "contains(45): " << contains(root, 45) << "\n";43 return 0;44}Binary Search Tree: kod (C)
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* left;8 struct Node* right;9} Node;10
11Node* newNode(int value) {12 Node* n = malloc(sizeof(Node));13 n->value = value;14 n->left = n->right = NULL;15 return n;16}17
18Node* insert(Node* root, int value) {19 if (root == NULL) return newNode(value);20 if (value < root->value) root->left = insert(root->left, value);21 else if (value > root->value) root->right = insert(root->right, value);22 return root; // duplicates are ignored23}24
25bool contains(const Node* root, int value) {26 // Walk down: smaller goes left, larger goes right27 while (root != NULL) {28 if (value == root->value) return true;29 root = value < root->value ? root->left : root->right;30 }31 return false;32}33
34void inorder(const Node* node) {35 if (node == NULL) return;36 inorder(node->left);37 printf("%d ", node->value);38 inorder(node->right);39}40
41int main(void) {42 int values[] = {50, 30, 70, 20, 40, 60, 80};43 Node* root = NULL;44 for (int i = 0; i < 7; i++) root = insert(root, values[i]);45 printf("Sorted: ");46 inorder(root);47 printf("\n");48 printf("contains(40): %s\n", contains(root, 40) ? "true" : "false");49 printf("contains(45): %s\n", contains(root, 45) ? "true" : "false");50 return 0;51}Drzewo BST: najczęstsze pytania
Jaka jest złożoność czasowa binarnego drzewa poszukiwań?
Wyszukiwanie, wstawianie i usuwanie mają złożoność
O(log n) w zrównoważonym drzewie, bo każde porównanie odrzuca połowę pozostałych węzłów. W najgorszym przypadku, gdy posortowane wstawienia przekrzywią drzewo w łańcuch, degradują się do O(n).Czym różni się drzewo binarne od binarnego drzewa poszukiwań?
Drzewo binarne to dowolne drzewo, w którym każdy węzeł ma najwyżej dwoje dzieci, bez reguły porządku. Binarne drzewo poszukiwań dodaje niezmiennik: wartości w lewym poddrzewie są mniejsze, a w prawym większe od węzła, i właśnie to umożliwia szybkie wyszukiwanie.
Dlaczego binarne drzewo poszukiwań może działać wolno?
Jeśli wartości są wstawiane w kolejności posortowanej (lub odwrotnie posortowanej), każdy nowy węzeł trafia na tę samą stronę, co tworzy wysokie, przekrzywione drzewo zachowujące się jak lista jednokierunkowa, czyli
O(n) na operację. Drzewa samorównoważące się (AVL, czerwono-czarne) wykonują rotacje węzłów, aby temu zapobiec.Czym różni się binarne drzewo poszukiwań od tablicy haszującej?
Tablica haszująca daje średnio
O(1) na wyszukiwanie, ale przechowuje klucze bez określonego porządku, więc nie odpowie na zapytania o zakres ani o następnika. Binarne drzewo poszukiwań jest nieco wolniejsze, O(log n), ale utrzymuje klucze w porządku, co pozwala przechodzić je w posortowanej kolejności i znajdować najbliższe wartości. Wybierz BST, gdy liczy się porządek, a tablicę haszującą, gdy potrzebujesz tylko sprawdzania przynależności.Kiedy użyć drzewa samorównoważącego się zamiast zwykłego BST?
Używaj drzewa samorównoważącego się (AVL, czerwono-czarnego) zawsze, gdy nie kontrolujesz kolejności wstawiania i potrzebujesz gwarantowanej wydajności
O(log n). Zwykłe drzewo BST sprawdzi się w nauce, przy małych zbiorach danych lub gdy klucze przychodzą w losowej kolejności, ale nie chroni przed przekrzywionym najgorszym przypadkiem.Czy przejście in-order drzewa BST zwraca posortowane wartości?
Tak. Odwiedzenie lewego poddrzewa, potem węzła, a potem prawego poddrzewa zwraca klucze w kolejności rosnącej, co wynika bezpośrednio z niezmiennika BST. Częsty błąd to oczekiwanie tego samego od zwykłego drzewa binarnego: bez reguły porządku przejście in-order nie daje żadnej sensownej sekwencji.
Powiązane materiały
Więcej wizualizacji
