AVL Ağacı
Son güncelleme
AVL ağacı, kendini dengeleyen bir ikili arama ağacıdır. Normal bir BST gibi çalışır, ancak her eklemeden sonra her atanın denge faktörünü - sol ve sağ alt ağaçları arasındaki yükseklik farkını - kontrol eder ve herhangi bir düğüm dengesiz hale gelirse (1'den büyük bir fark), dengeyi yeniden sağlamak için dönüşler gerçekleştirir. Değerlerin eklendiğini ve ağacın kendini tekrar şekle sokmak için döndüğünü görmek için yukarıdaki oynat düğmesine basın.
Ağacın hafifçe bile fazla eğilmesine asla izin vermediği için, bir AVL ağacı O(log n) yükseklik garanti eder, böylece arama, ekleme ve silme her zaman O(log n) olur - sıradan bir BST'yi mahvedecek sıralı girdiler için bile. Bunun bedeli, her eklemedeki ekstra dönüşler ve yükseklik kayıtlarıdır.
Zaman ve alan karmaşıklığı
| İşlem | Karmaşıklık | Notlar |
|---|---|---|
| Arama | O(log n) | Yükseklik her zaman ~1.44 log n |
| Ekleme | O(log n) | Artı O(1) dönüş |
| Silme | O(log n) | Artı O(log n) dönüş |
| Alan | O(n) | Düğüm başına bir yükseklik alanı |
Dört dönüş durumu
| Durum | Dengesizlik | Düzeltme |
|---|---|---|
| Sol-Sol | Sol çocuğun solunda ağır | Bir sağa dönüş |
| Sağ-Sağ | Sağ çocuğun sağında ağır | Bir sola dönüş |
| Sol-Sağ | Sol çocuğun sağında ağır | Sola, sonra sağa dönüş |
| Sağ-Sol | Sağ çocuğun solunda ağır | Sağa, sonra sola dönüş |
Çözümlü örnek
[10, 20, 30, 40, 50, 25] değerlerini teker teker ekleme:
| Adım | Yapı | Eylem |
|---|---|---|
10 ekle | 10 | İlk düğüm kök olur; dengeli |
20 ekle | 10(_, 20) | 10'un sağına gider; hâlâ dengeli |
30 ekle | 20(10, 30) | 10'da Sağ-Sağ, bu yüzden bir sola dönüş 20'yi köke çıkarır |
40 ekle | 20(10, 30(_, 40)) | 30'un sağına gider; tüm denge faktörleri ±1 içinde kalır |
50 ekle | 20(10, 40(30, 50)) | 30'da Sağ-Sağ, bu yüzden 30'daki bir sola dönüş 40'ı yükseltir |
25 ekle | 30(20(10, 25), 40(_, 50)) | 20'de Sağ-Sol: 40'ın alt ağacını sağa döndür, sonra 20'yi sola döndür |
AVL ağacını ne zaman kullanmalı
| Şu durumda kullanın | Şu durumda kaçının |
|---|---|
| Aramalar eklemelerden çok daha fazlaysa ve mümkün olan en sıkı yüksekliği istiyorsanız | Eklemeler ve silmeler baskınsa - ekstra dönüşler ve yeniden dengeleme, kırmızı-siyah ağaçtan daha pahalıya mal olur |
Düşmanca veya sıralı girdiler için bile garantili O(log n) en kötü duruma ihtiyacınız varsa | Düz bir hash tablosu yeterliyse - sıralı gezinme veya aralık sorgularına ihtiyacınız yoksa |
| Sıralı işlemlere ihtiyacınız varsa: sıralı gezinme, öncül/ardıl, aralık sorguları | Veri kümesi çok küçükse - düz bir BST veya sıralı dizi daha basit ve yeterince hızlıdır |
| Veriler zaten sıralı gelebiliyorsa, bu dengesiz bir BST'yi bağlı listeye dönüştürür | Çok dar bir alanda düğüm başına yükseklik alanının ekstra belleğini karşılayamıyorsanız |
AVL Tree kodu
Python, JavaScript, Java, C++, C dillerinde temiz ve çalıştırılabilir bir AVL Tree uygulaması. Bir dil seçin, kodu kopyalayın veya Coddy Playground'da hazır yüklenmiş olarak açın.
Python ile AVL Tree kodu
Python
1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6 self.height = 17
8
9def height(node):10 return node.height if node else 011
12
13def update(node):14 node.height = 1 + max(height(node.left), height(node.right))15
16
17def rotate_right(y):18 x = y.left19 y.left = x.right20 x.right = y21 update(y)22 update(x)23 return x24
25
26def rotate_left(x):27 y = x.right28 x.right = y.left29 y.left = x30 update(x)31 update(y)32 return y33
34
35def insert(node, key):36 if node is None:37 return Node(key)38 if key < node.key:39 node.left = insert(node.left, key)40 else:41 node.right = insert(node.right, key)42 update(node)43 balance = height(node.left) - height(node.right)44 # Four imbalance cases: LL, RR, LR, RL45 if balance > 1 and key < node.left.key:46 return rotate_right(node)47 if balance < -1 and key > node.right.key:48 return rotate_left(node)49 if balance > 1:50 node.left = rotate_left(node.left)51 return rotate_right(node)52 if balance < -1:53 node.right = rotate_right(node.right)54 return rotate_left(node)55 return node56
57
58def inorder(node):59 if node is None:60 return []61 return inorder(node.left) + [node.key] + inorder(node.right)62
63
64root = None65for key in [10, 20, 30, 40, 50, 25]:66 root = insert(root, key)67
68print("Inorder:", inorder(root))69print("Root:", root.key, "| tree height:", root.height)JavaScript ile AVL Tree kodu
JavaScript
1class Node {2 constructor(key) {3 this.key = key;4 this.left = null;5 this.right = null;6 this.height = 1;7 }8}9
10const height = (n) => (n ? n.height : 0);11const update = (n) => {12 n.height = 1 + Math.max(height(n.left), height(n.right));13};14const balance = (n) => height(n.left) - height(n.right);15
16function rotateRight(y) {17 const x = y.left;18 y.left = x.right;19 x.right = y;20 update(y);21 update(x);22 return x;23}24
25function rotateLeft(x) {26 const y = x.right;27 x.right = y.left;28 y.left = x;29 update(x);30 update(y);31 return y;32}33
34function insert(node, key) {35 if (!node) return new Node(key);36 if (key < node.key) node.left = insert(node.left, key);37 else node.right = insert(node.right, key);38 update(node);39 const b = balance(node);40 // Four rebalancing cases: LL, RR, LR, RL41 if (b > 1 && key < node.left.key) return rotateRight(node);42 if (b < -1 && key > node.right.key) return rotateLeft(node);43 if (b > 1) {44 node.left = rotateLeft(node.left);45 return rotateRight(node);46 }47 if (b < -1) {48 node.right = rotateRight(node.right);49 return rotateLeft(node);50 }51 return node;52}53
54function inorder(node, out = []) {55 if (!node) return out;56 inorder(node.left, out);57 out.push(node.key);58 inorder(node.right, out);59 return out;60}61
62let root = null;63for (const key of [10, 20, 30, 40, 50, 25]) root = insert(root, key);64console.log("Root after rebalancing:", root.key);65console.log("Inorder:", inorder(root).join(" "));Java ile AVL Tree kodu
Java
1public class Main {2 static class Node {3 int key, height = 1;4 Node left, right;5 Node(int key) { this.key = key; }6 }7
8 static int height(Node n) { return n == null ? 0 : n.height; }9 static int balance(Node n) { return n == null ? 0 : height(n.left) - height(n.right); }10 static void update(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); }11
12 static Node rotateRight(Node y) {13 Node x = y.left;14 y.left = x.right;15 x.right = y;16 update(y); update(x);17 return x;18 }19
20 static Node rotateLeft(Node x) {21 Node y = x.right;22 x.right = y.left;23 y.left = x;24 update(x); update(y);25 return y;26 }27
28 static Node insert(Node node, int key) {29 if (node == null) return new Node(key);30 if (key < node.key) node.left = insert(node.left, key);31 else node.right = insert(node.right, key);32 update(node);33 int b = balance(node);34 // Four imbalance cases: LL, RR, LR, RL35 if (b > 1 && key < node.left.key) return rotateRight(node);36 if (b < -1 && key > node.right.key) return rotateLeft(node);37 if (b > 1) { node.left = rotateLeft(node.left); return rotateRight(node); }38 if (b < -1) { node.right = rotateRight(node.right); return rotateLeft(node); }39 return node;40 }41
42 static void inorder(Node n, StringBuilder sb) {43 if (n == null) return;44 inorder(n.left, sb);45 sb.append(n.key).append(" ");46 inorder(n.right, sb);47 }48
49 public static void main(String[] args) {50 Node root = null;51 int[] keys = {10, 20, 30, 40, 50, 25};52 for (int k : keys) root = insert(root, k);53 StringBuilder sb = new StringBuilder();54 inorder(root, sb);55 System.out.println("Inorder: " + sb.toString().trim());56 System.out.println("Root after rebalancing: " + root.key + " (height " + root.height + ")");57 }58}C++ ile AVL Tree kodu
C++
1#include <algorithm>2#include <iostream>3
4struct Node {5 int value;6 int height = 1;7 Node* left = nullptr;8 Node* right = nullptr;9 explicit Node(int v) : value(v) {}10};11
12int height(const Node* n) { return n ? n->height : 0; }13int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }14void updateHeight(Node* n) {15 n->height = 1 + std::max(height(n->left), height(n->right));16}17
18Node* rotateRight(Node* y) {19 Node* x = y->left;20 y->left = x->right;21 x->right = y;22 updateHeight(y);23 updateHeight(x);24 return x;25}26
27Node* rotateLeft(Node* x) {28 Node* y = x->right;29 x->right = y->left;30 y->left = x;31 updateHeight(x);32 updateHeight(y);33 return y;34}35
36Node* insert(Node* node, int value) {37 if (node == nullptr) return new Node(value);38 if (value < node->value) node->left = insert(node->left, value);39 else node->right = insert(node->right, value);40 updateHeight(node);41 int balance = balanceFactor(node);42 // Four rebalancing cases: LL, RR, LR, RL43 if (balance > 1 && value < node->left->value) return rotateRight(node);44 if (balance < -1 && value > node->right->value) return rotateLeft(node);45 if (balance > 1) {46 node->left = rotateLeft(node->left);47 return rotateRight(node);48 }49 if (balance < -1) {50 node->right = rotateRight(node->right);51 return rotateLeft(node);52 }53 return node;54}55
56void inorder(const Node* n) {57 if (n == nullptr) return;58 inorder(n->left);59 std::cout << n->value << "(h" << n->height << ") ";60 inorder(n->right);61}62
63int main() {64 Node* root = nullptr;65 for (int value : {10, 20, 30, 40, 50, 25}) root = insert(root, value);66 std::cout << "Root after rebalancing: " << root->value << "\n";67 std::cout << "In-order: ";68 inorder(root);69 std::cout << "\n";70 return 0;71}C ile AVL Tree kodu
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value, height;6 struct Node* left;7 struct Node* right;8} Node;9
10int height(const Node* n) { return n ? n->height : 0; }11int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }12int maxInt(int a, int b) { return a > b ? a : b; }13
14Node* newNode(int value) {15 Node* n = calloc(1, sizeof(Node));16 n->value = value;17 n->height = 1;18 return n;19}20
21void updateHeight(Node* n) {22 n->height = 1 + maxInt(height(n->left), height(n->right));23}24
25Node* rotateRight(Node* y) {26 Node* x = y->left;27 y->left = x->right;28 x->right = y;29 updateHeight(y);30 updateHeight(x);31 return x;32}33
34Node* rotateLeft(Node* x) {35 Node* y = x->right;36 x->right = y->left;37 y->left = x;38 updateHeight(x);39 updateHeight(y);40 return y;41}42
43Node* insert(Node* node, int value) {44 if (node == NULL) return newNode(value);45 if (value < node->value) node->left = insert(node->left, value);46 else node->right = insert(node->right, value);47 updateHeight(node);48 int balance = balanceFactor(node);49 // Four rebalancing cases: LL, RR, LR, RL50 if (balance > 1 && value < node->left->value) return rotateRight(node);51 if (balance < -1 && value > node->right->value) return rotateLeft(node);52 if (balance > 1) {53 node->left = rotateLeft(node->left);54 return rotateRight(node);55 }56 if (balance < -1) {57 node->right = rotateRight(node->right);58 return rotateLeft(node);59 }60 return node;61}62
63void inorder(const Node* n) {64 if (n == NULL) return;65 inorder(n->left);66 printf("%d(h%d) ", n->value, n->height);67 inorder(n->right);68}69
70int main(void) {71 int values[] = {10, 20, 30, 40, 50, 25};72 Node* root = NULL;73 for (int i = 0; i < 6; i++) root = insert(root, values[i]);74 printf("Root after rebalancing: %d\n", root->value);75 printf("In-order: ");76 inorder(root);77 printf("\n");78 return 0;79}AVL Ağacı SSS
AVL ağacında denge faktörü nedir?
Bir düğümün denge faktörü, sol alt ağacının yüksekliği eksi sağ alt ağacının yüksekliğidir. Bir AVL ağacı her düğümün denge faktörünü -1, 0 veya +1'de tutar; bir ekleme onu bu aralığın dışına iterse, bir dönüş dengeyi yeniden sağlar.
AVL ağacı ile kırmızı-siyah ağaç arasındaki fark nedir?
Her ikisi de
O(log n) işlemlere sahip kendini dengeleyen BST'lerdir. AVL ağaçları daha katı biçimde dengelidir, bu yüzden aramalar biraz daha hızlıdır, ancak ekleme/silmede daha fazla dönüş yapabilirler. Kırmızı-siyah ağaçlar daha gevşek dengelidir ve daha az dönüşü tercih eder - bu yüzden birçok standart kütüphane bunları haritalar ve kümeler için kullanır.Neden düz bir ikili arama ağacı yerine AVL ağacı kullanılır?
Düz bir BST, değerler sıralı gelirse eğik bir zincir oluşturarak
O(n) işlemlere düşebilir. Bir AVL ağacı dengeli kalmak için döner ve ekleme sırasından bağımsız olarak O(log n) yükseklik ve işlemleri garanti eder.Bir veritabanı dizini için AVL ağacı kırmızı-siyah ağaçtan daha mı iyidir?
İş yüküne bağlıdır. AVL ağaçları daha katı biçimde dengelidir, bu yüzden okumalar baskın olduğunda ve mümkün olan en kısa arama yollarını istediğinizde kazanırlar. Ancak çoğu veritabanı ve dil kütüphanesi kırmızı-siyah ağaçları (veya B-ağaçlarını) seçer çünkü yazma ağırlıklı iş yüklerinde daha az dönüşle yeniden dengelenirler ki bu, eklemeler ve silmeler sık olduğunda daha önemlidir.
Tek bir AVL eklemesi kaç dönüşe ihtiyaç duyar?
Bir değer ekledikten sonra ağacı yeniden dengelemek için en fazla bir dönüş - ya tek ya da çift (iki adımlı) bir dönüş - gerekir. Bunun nedeni, bir eklemenin bir alt ağacın yüksekliğini en fazla bir artırmasıdır, bu yüzden en alttaki dengesiz atadaki tek bir düzeltme yeterlidir. Silme farklıdır: yeniden dengeleme köke doğru yayılırken
O(log n) kadar dönüş gerektirebilir.Her dönüşten sonra düğüm yüksekliklerini güncellemem gerekir mi?
Evet - yaygın bir hata, işaretçileri doğru döndürmek ama ilgili iki düğümün yüksekliğini yeniden hesaplamayı unutmaktır. Her dönüşten sonra önce indirilen düğümün yüksekliğini, sonra yükseltilen düğümünkini güncellemelisiniz, çünkü yükseltilen düğümün yüksekliği yeni çocuklarına bağlıdır. Bunu atlamak, gelecekteki yeniden dengeleme kararlarını bozan eski denge faktörleri bırakır.
İlgili kaynaklar
Daha fazla görselleştirme
