İkili Arama Ağacı (BST)
Son güncelleme
Bir ikili arama ağacı değerlerini sıralı tutar: her düğüm için sol alt ağaçtaki tüm değerler daha küçük, sağ alt ağaçtaki tüm değerler daha büyüktür. Bir değer eklemek veya bulmak için kökten başlar ve karşılaştırmaya göre tekrar tekrar sola ya da sağa gidersiniz, böylece her adım arama alanını yarıya indirir. Değerlerin karşılaştırmayla yerleştirilişini ve ağaçta aşağı inen bir aramayı izlemek için yukarıdaki oynat düğmesine basın.
Dengeli bir ağaçta bu işlemler O(log n) sürede çalışır. Sorun şu: zaten sıralı verileri eklemek ağacı O(n) işlemlerle çalışan bir bağlı listeye dönüştürür - AVL ve kırmızı-siyah ağaç gibi kendi kendini dengeleyen türlerin var olma sebebi tam olarak budur.
Zaman ve alan karmaşıklığı
| İşlem | Dengeli | En kötü durum (dengesiz) |
|---|---|---|
| Arama | O(log n) | O(n) |
| Ekleme | O(log n) | O(n) |
| Silme | O(log n) | O(n) |
| Alan | O(n) | O(n) |
Adım adım (ekleme)
| Adım | Ne olur |
|---|---|
| 1 | Ağaç boşsa, yeni değer kök olur. |
| 2 | Aksi halde kökten başla. |
| 3 | Değer küçükse sol çocuğa git; büyükse sağa git. |
| 4 | Boş bir yere ulaşana kadar tekrarla. |
| 5 | Yeni değeri oraya bir yaprak olarak ekle. |
Çözümlü örnek
Boş bir ağaca [5, 3, 8, 1, 4] değerlerini birer birer ekleme:
| Eklenen | İzlenen yol | İşlem |
|---|---|---|
5 | - | Ağaç boş, bu yüzden 5 kök olur. |
3 | 5 | 3 < 5, sola git; yer boş, 3'ü 5'in sol çocuğu olarak ekle. |
8 | 5 | 8 > 5, sağa git; yer boş, 8'i 5'in sağ çocuğu olarak ekle. |
1 | 5 -> 3 | 1 < 5 sola git, sonra 1 < 3 sola git; 1'i 3'ün sol çocuğu olarak ekle. |
4 | 5 -> 3 | 4 < 5 sola git, sonra 4 > 3 sağa git; 4'ü 3'ün sağ çocuğu olarak ekle. |
İkili arama ağacını ne zaman kullanmalı
| Şu durumda kullan | Şu durumda kaçın |
|---|---|
| Sıralı düzen ve hızlı aramalara ihtiyacın var ve eklemeler rastgele sırada geliyor. | Verilerin zaten sıralı geliyor: dengesiz bir BST işlem başına O(n)'e düşer. |
| Sıralı (in-order) dolaşmanın değerleri sıralı dizide bedavaya vermesini istiyorsun. | Yalnızca üyelik testine ihtiyacın var ve sıra önemli değil: bir hash tablosu ortalama O(1) arama sunar. |
| Aralık sorgularına veya bir anahtarın ardılına/öncülüne ihtiyacın var. | Garantili O(log n) sınırlarına ihtiyacın var: bunun yerine kendi kendini dengeleyen AVL veya kırmızı-siyah ağaca yönel. |
| Veri kümesi sık değişiyor ve statik bir sıralı diziyi güncellemek maliyetli olurdu. | Veri kümesi sabit ve salt okunur: ikili aramalı sıralı bir dizi daha basit ve önbellek dostudur. |
Binary Search Tree kodu
Python, JavaScript, Java, C++, C dillerinde temiz ve çalıştırılabilir bir Binary Search Tree uygulaması. Bir dil seçin, kodu kopyalayın veya Coddy Playground'da hazır yüklenmiş olarak açın.
Python ile Binary Search Tree kodu
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))JavaScript ile Binary Search Tree kodu
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));Java ile Binary Search Tree kodu
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}C++ ile Binary Search Tree kodu
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}C ile Binary Search Tree kodu
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}İkili Arama Ağacı SSS
İkili arama ağacının zaman karmaşıklığı nedir?
Arama, ekleme ve silme dengeli bir ağaçta
O(log n)'dir, çünkü her karşılaştırma kalan düğümlerin yarısını eler. En kötü durumda - sıralı eklemelerle zincire dönüşmüş dengesiz bir ağaç - O(n)'e düşerler.İkili ağaç ile ikili arama ağacı arasındaki fark nedir?
İkili ağaç, her düğümün en fazla iki çocuğu olduğu ve sıralama kuralı bulunmayan herhangi bir ağaçtır. İkili arama ağacı, sol alt ağaç değerlerinin daha küçük, sağ alt ağaç değerlerinin düğümden daha büyük olduğu değişmezi ekler; hızlı aramayı mümkün kılan da budur.
İkili arama ağacı neden yavaşlayabilir?
Değerler sıralı (veya ters sıralı) eklenirse, her yeni düğüm aynı tarafa gider ve bağlı liste gibi davranan uzun, dengesiz bir ağaç oluşur: işlem başına
O(n). Kendi kendini dengeleyen ağaçlar (AVL, kırmızı-siyah) bunu önlemek için düğümleri döndürür.İkili arama ağacı ile hash tablosu arasındaki fark nedir?
Bir hash tablosu ortalama
O(1) arama sunar ama anahtarları hiçbir sırada tutmaz, bu yüzden aralık veya ardıl sorgularını yanıtlayamaz. İkili arama ağacı O(log n) ile biraz daha yavaştır ama anahtarları sıralı tutar; bu da onları sıralı dolaşmanı ve en yakın değerleri bulmanı sağlar. Sıra önemliyse BST'yi, yalnızca üyelik testine ihtiyacın varsa hash tablosunu seç.Düz bir BST yerine ne zaman kendi kendini dengeleyen ağaç kullanmalıyım?
Ekleme sırasını kontrol edemediğinde ve garantili
O(log n) performansa ihtiyacın olduğunda kendi kendini dengeleyen bir ağaç (AVL, kırmızı-siyah) kullan. Düz bir BST öğretim için, küçük veri kümeleri için veya anahtarlar rastgele sırada geldiğinde uygundur ama dengesiz en kötü duruma karşı koruma sağlamaz.Bir BST'nin sıralı (in-order) dolaşması sıralı değerler döndürür mü?
Evet. Önce sol alt ağacı, sonra düğümü, ardından sağ alt ağacı ziyaret etmek anahtarları artan sırada verir; bu doğrudan BST değişmezinden gelir. Yaygın bir hata, aynısını düz bir ikili ağaçtan beklemektir: sıralama kuralı olmadan sıralı dolaşma anlamlı bir dizi üretmez.
İlgili kaynaklar
Daha fazla görselleştirme
