Önceki derste ikili arama ağacının zarif vaadini ve kırılgan yanını gördün: Dengeli olduğunda O(log n), sıralı veri eklendiğinde O(n). Sorun şu ki gerçek verilerin çoğu bir ölçüde sıralıdır — artan kimlik numaraları, zaman damgaları, alfabetik listeler. Yani dengesizlik istisna değil, beklenen durumdur.
1962'de iki Sovyet matematikçi, Georgy Adelson-Velsky ve Evgenii Landis, bu soruna ilk çözümü getirdi. Fikirleri şuydu: Her eklemeden ve silmeden sonra ağacın dengesini kontrol et, bozulmuşsa yerel bir düzeltme yaparak onar. Bu düzeltmeye dönüş (rotation) denir, ve tüm ağacı yeniden kurmak yerine yalnızca birkaç işaretçiyi değiştirdiği için O(1) sürer. İsimlerinin baş harfleriyle anılan AVL ağacı, tarihteki ilk kendini dengeleyen arama ağacıdır.
Bu derste dengenin neden bu kadar önemli olduğunu, denge faktörünü, dört dengesizlik durumunu ve bunları düzelten dönüşleri, tam bir AVL uygulamasını, ve modern sistemlerde kullanılan akrabalarını — kırmızı-siyah ağaçlar ile B-ağaçlarını — öğreneceksin.
Neden denge?
Dengesizliğin bedelini sayılarla görmek, konunun önemini en iyi anlatan şeydir:
n = 1.000.000 eleman
dengeli ağaç : yükseklik ≈ 20 → arama 20 adım
dejenere ağaç : yükseklik = 999999 → arama ~1.000.000 adım
50.000 kat farkAVL ağacının verdiği garanti şudur: Her düğümde, sol ve sağ alt ağacın yükseklikleri arasındaki fark en fazla 1'dir. Bu kısıt, yüksekliği matematiksel olarak sınırlar:
h yükseklikli bir AVL ağacında en az kaç düğüm olmalı?
N(h) = N(h-1) + N(h-2) + 1 ← Fibonacci benzeri bir bağıntı
N(0) = 1, N(1) = 2
h : 0 1 2 3 4 5 6 7
N(h): 1 2 4 7 12 20 33 54
Sonuç: h < 1.44 × log₂(n)Yani bir AVL ağacının yüksekliği, mükemmel dengeli bir ağacın yüksekliğinden en fazla %44 fazla olabilir. Bu, tüm işlemler için kesin O(log n) garantisi demektir — "ortalama" değil, her zaman.
Aşağıdaki görselleştirmede dengeli kipte değer ekleyerek dönüşlerin nasıl devreye girdiğini izleyebilirsin. Sıralı değerler eklediğinde ağacın nasıl kendini toparladığına dikkat et:
Denge faktörü
Her düğüm için denge faktörü şöyle tanımlanır:
denge faktörü = yükseklik(sol alt ağaç) − yükseklik(sağ alt ağaç)
0 : mükemmel dengeli
+1 : sol biraz ağır ← kabul edilebilir
-1 : sağ biraz ağır ← kabul edilebilir
+2 : sol çok ağır ← DÜZELTME GEREKLİ
-2 : sağ çok ağır ← DÜZELTME GEREKLİDenge faktörü ±2 olduğu anda ağaç düzeltilir; bu yüzden hiçbir zaman ±3'e ulaşmaz. Her düğümde yüksekliği saklamak, denge faktörünü O(1) sürede hesaplamayı sağlar — her seferinde alt ağacı taramak gerekmez.
package main
import "fmt"
type Node struct {
Value int
Height int // bu düğümün yüksekliği (yaprak = 0)
Left, Right *Node
}
func height(n *Node) int {
if n == nil {
return -1
}
return n.Height
}
func balanceFactor(n *Node) int {
if n == nil {
return 0
}
return height(n.Left) - height(n.Right)
}
func updateHeight(n *Node) {
n.Height = 1 + max(height(n.Left), height(n.Right))
}
// Dengesiz bir ağacı elle kurup denge faktörlerini inceleyelim
func main() {
// Sıralı ekleme gibi sağa uzayan bir ağaç
leaf := &Node{Value: 30}
updateHeight(leaf)
mid := &Node{Value: 20, Right: leaf}
updateHeight(mid)
root := &Node{Value: 10, Right: mid}
updateHeight(root)
fmt.Println("sağa uzayan ağaç (10 → 20 → 30):")
for _, n := range []*Node{root, mid, leaf} {
fmt.Printf(" düğüm %-3d yükseklik=%d denge=%+d\n", n.Value, n.Height, balanceFactor(n))
}
fmt.Println("kökün dengesi bozuk mu:", balanceFactor(root) < -1 || balanceFactor(root) > 1)
// Dengeli hâli
l := &Node{Value: 10}
r := &Node{Value: 30}
updateHeight(l)
updateHeight(r)
balanced := &Node{Value: 20, Left: l, Right: r}
updateHeight(balanced)
fmt.Println()
fmt.Println("dengeli hâli (20 kök):")
fmt.Printf(" kök yükseklik=%d denge=%+d\n", balanced.Height, balanceFactor(balanced))
fmt.Println("aynı üç eleman, yükseklik farkı:", root.Height, "→", balanced.Height)
}sağa uzayan ağaç (10 → 20 → 30): düğüm 10 yükseklik=2 denge=-2 düğüm 20 yükseklik=1 denge=-1 düğüm 30 yükseklik=0 denge=+0 kökün dengesi bozuk mu: true dengeli hâli (20 kök): kök yükseklik=1 denge=+0 aynı üç eleman, yükseklik farkı: 2 → 1
Dönüşler
Dönüş, BST özelliğini bozmadan ağacın şeklini değiştiren yerel bir işlemdir. Yalnızca birkaç işaretçiyi yeniden bağladığı için O(1) sürer.
SAĞA DÖNÜŞ (sol ağır olduğunda)
y x
┌┴──┐ sağa dönüş ┌─┴──┐
x C ──────────► A y
┌─┴─┐ ┌─┴─┐
A B B C
Kontrol: A < x < B < y < C ← BST sırası KORUNDUSOLA DÖNÜŞ (sağ ağır olduğunda)
x y
┌─┴──┐ sola dönüş ┌─┴──┐
A y ──────────► x C
┌─┴─┐ ┌─┴─┐
B C A BDönüşün çalıştığını doğrulamanın yolu, inorder gezinmenin değişmediğini görmektir: Her iki şekilde de A x B y C sırası elde edilir.
package main
import (
"fmt"
"strings"
)
type Node struct {
Value int
Height int
Left, Right *Node
}
func height(n *Node) int {
if n == nil {
return -1
}
return n.Height
}
func updateHeight(n *Node) {
n.Height = 1 + max(height(n.Left), height(n.Right))
}
// rotateRight: sol ağır durumu düzeltir
func rotateRight(y *Node) *Node {
x := y.Left
b := x.Right
x.Right = y // x yeni kök olur
y.Left = b // y'nin solu, x'in eski sağ alt ağacı
updateHeight(y) // önce alttaki
updateHeight(x) // sonra yeni kök
return x
}
// rotateLeft: sağ ağır durumu düzeltir
func rotateLeft(x *Node) *Node {
y := x.Right
b := y.Left
y.Left = x
x.Right = b
updateHeight(x)
updateHeight(y)
return y
}
func inorder(n *Node, out *[]int) {
if n == nil {
return
}
inorder(n.Left, out)
*out = append(*out, n.Value)
inorder(n.Right, out)
}
func collect(n *Node) string {
var out []int
inorder(n, &out)
parts := make([]string, len(out))
for i, v := range out {
parts[i] = fmt.Sprint(v)
}
return strings.Join(parts, " ")
}
func main() {
// Sola dönüş örneği: 10 → 20 → 30 zinciri
a := &Node{Value: 30}
updateHeight(a)
b := &Node{Value: 20, Right: a}
updateHeight(b)
root := &Node{Value: 10, Right: b}
updateHeight(root)
fmt.Println("dönüş öncesi:")
fmt.Println(" kök:", root.Value, "yükseklik:", root.Height)
fmt.Println(" inorder:", collect(root))
root = rotateLeft(root)
fmt.Println("sola dönüş sonrası:")
fmt.Println(" kök:", root.Value, "yükseklik:", root.Height)
fmt.Println(" inorder:", collect(root), "← sıra korundu")
// Sağa dönüş örneği: 30 → 20 → 10 zinciri
c := &Node{Value: 10}
updateHeight(c)
d := &Node{Value: 20, Left: c}
updateHeight(d)
root2 := &Node{Value: 30, Left: d}
updateHeight(root2)
fmt.Println()
fmt.Println("sağa dönüş öncesi yükseklik:", root2.Height, "inorder:", collect(root2))
root2 = rotateRight(root2)
fmt.Println("sağa dönüş sonrası yükseklik:", root2.Height, "inorder:", collect(root2))
fmt.Println("yeni kök:", root2.Value)
}dönüş öncesi: kök: 10 yükseklik: 2 inorder: 10 20 30 sola dönüş sonrası: kök: 20 yükseklik: 1 inorder: 10 20 30 ← sıra korundu sağa dönüş öncesi yükseklik: 2 inorder: 10 20 30 sağa dönüş sonrası yükseklik: 1 inorder: 10 20 30 yeni kök: 20
updateHeight çağrılarının sırası kritiktir: Önce aşağıdaki düğümün yüksekliği güncellenmelidir, çünkü yeni kökün yüksekliği ona bağlıdır. Bu küçük detay, AVL uygulamalarındaki en yaygın hatalardan biridir.
Dört dengesizlik durumu
Dengesizlik her zaman dört şekilden birinde ortaya çıkar. Adları, yeni elemanın hangi yoldan eklendiğini anlatır.
LL (Sol-Sol) → tek sağa dönüş
z y
┌┴──┐ ┌─┴─┐
y D x z
┌─┴─┐ ┌─┴┐ ┌┴─┐
x C A B C D
┌─┴─┐
A B
RR (Sağ-Sağ) → tek sola dönüş
z y
┌┴──┐ ┌─┴─┐
A y z x
┌─┴─┐ ┌─┴┐ ┌┴─┐
B x A B C D
┌─┴─┐
C D
LR (Sol-Sağ) → önce sola, sonra sağa
z z x
┌─┴─┐ ┌─┴─┐ ┌─┴─┐
y D sola x D sağa y z
┌─┴─┐ ───► ┌─┴─┐ ───► ┌┴┐ ┌┴┐
A x y C A B C D
┌─┴─┐ ┌─┴─┐
B C A B
RL (Sağ-Sol) → önce sağa, sonra sola
z z x
┌┴─┐ ┌─┴─┐ ┌─┴─┐
A y sağa A x sola z y
┌─┴─┐ ───► ┌──┴─┐ ───► ┌┴┐ ┌┴┐
x D B y A B C D
┌─┴─┐ ┌─┴─┐
B C C DHangi durumda olduğunu anlamak iki karşılaştırmayla yapılır: Önce düğümün denge faktörüne bak (sol mu sağ mı ağır), sonra o taraftaki çocuğun denge faktörüne bak (aynı yönde mi, ters yönde mi).
AVL ekleme uygulaması
Şimdi hepsini birleştirelim. Ekleme sıradan BST eklemesiyle başlar; fark, özyineleme geri dönerken her düğümde yüksekliğin güncellenmesi ve dengenin kontrol edilmesidir.
package main
import (
"fmt"
"strings"
)
type Node struct {
Value int
Height int
Left, Right *Node
}
type AVL struct {
root *Node
size int
rotations int
}
func height(n *Node) int {
if n == nil {
return -1
}
return n.Height
}
func balanceFactor(n *Node) int {
if n == nil {
return 0
}
return height(n.Left) - height(n.Right)
}
func updateHeight(n *Node) {
n.Height = 1 + max(height(n.Left), height(n.Right))
}
func (t *AVL) rotateRight(y *Node) *Node {
t.rotations++
x := y.Left
y.Left = x.Right
x.Right = y
updateHeight(y)
updateHeight(x)
return x
}
func (t *AVL) rotateLeft(x *Node) *Node {
t.rotations++
y := x.Right
x.Right = y.Left
y.Left = x
updateHeight(x)
updateHeight(y)
return y
}
// rebalance: dört durumu da ele alır
func (t *AVL) rebalance(n *Node) *Node {
updateHeight(n)
bf := balanceFactor(n)
if bf > 1 { // sol ağır
if balanceFactor(n.Left) < 0 {
n.Left = t.rotateLeft(n.Left) // LR
}
return t.rotateRight(n) // LL veya LR'nin ikinci adımı
}
if bf < -1 { // sağ ağır
if balanceFactor(n.Right) > 0 {
n.Right = t.rotateRight(n.Right) // RL
}
return t.rotateLeft(n) // RR veya RL'nin ikinci adımı
}
return n // denge yerinde
}
func (t *AVL) Insert(v int) {
var insert func(*Node, int) *Node
insert = func(n *Node, v int) *Node {
if n == nil {
t.size++
return &Node{Value: v}
}
switch {
case v < n.Value:
n.Left = insert(n.Left, v)
case v > n.Value:
n.Right = insert(n.Right, v)
default:
return n // tekrar: yok say
}
return t.rebalance(n)
}
t.root = insert(t.root, v)
}
func (t *AVL) Delete(v int) {
var minValue func(*Node) int
minValue = func(n *Node) int {
for n.Left != nil {
n = n.Left
}
return n.Value
}
var del func(*Node, int) *Node
del = func(n *Node, v int) *Node {
if n == nil {
return nil
}
switch {
case v < n.Value:
n.Left = del(n.Left, v)
case v > n.Value:
n.Right = del(n.Right, v)
default:
t.size--
if n.Left == nil {
return n.Right
}
if n.Right == nil {
return n.Left
}
n.Value = minValue(n.Right)
t.size++ // aşağıdaki silme tekrar azaltacak
n.Right = del(n.Right, n.Value)
}
return t.rebalance(n)
}
t.root = del(t.root, v)
}
func (t *AVL) Height() int { return height(t.root) }
func (t *AVL) InOrder() []int {
var out []int
var walk func(*Node)
walk = func(n *Node) {
if n == nil {
return
}
walk(n.Left)
out = append(out, n.Value)
walk(n.Right)
}
walk(t.root)
return out
}
func (t *AVL) IsBalanced() bool {
var check func(*Node) bool
check = func(n *Node) bool {
if n == nil {
return true
}
bf := balanceFactor(n)
return bf >= -1 && bf <= 1 && check(n.Left) && check(n.Right)
}
return check(t.root)
}
func (t *AVL) String() string {
var sb strings.Builder
var draw func(*Node, string, string)
draw = func(n *Node, prefix, branch string) {
if n == nil {
return
}
draw(n.Right, prefix+" ", "┌── ")
fmt.Fprintf(&sb, "%s%s%d(%+d)\n", prefix, branch, n.Value, balanceFactor(n))
draw(n.Left, prefix+" ", "└── ")
}
draw(t.root, "", "")
return sb.String()
}
func main() {
// Sıralı ekleme: normal BST'de felaket, AVL'de sorun değil
var t AVL
for i := 1; i <= 7; i++ {
t.Insert(i)
}
fmt.Println("1..7 sırayla eklendi:")
fmt.Print(t.String())
fmt.Println("yükseklik:", t.Height(), "| dönüş sayısı:", t.rotations)
fmt.Println("dengeli mi:", t.IsBalanced())
fmt.Println("inorder:", t.InOrder())
// Büyük ölçekli karşılaştırma
var big AVL
for i := 1; i <= 1023; i++ {
big.Insert(i)
}
fmt.Println()
fmt.Println("1023 sıralı eleman eklendi:")
fmt.Println(" AVL yüksekliği:", big.Height())
fmt.Println(" sıradan BST olsaydı:", 1022)
fmt.Println(" teorik alt sınır (log₂ 1023):", 9)
fmt.Println(" toplam dönüş:", big.rotations)
fmt.Println(" dengeli mi:", big.IsBalanced())
// Silme sonrası da dengeli kalmalı
for i := 1; i <= 500; i++ {
big.Delete(i)
}
fmt.Println()
fmt.Println("500 eleman silindikten sonra:")
fmt.Println(" eleman sayısı:", big.size, "| yükseklik:", big.Height())
fmt.Println(" dengeli mi:", big.IsBalanced())
}1..7 sırayla eklendi:
┌── 7(+0)
┌── 6(+0)
└── 5(+0)
4(+0)
┌── 3(+0)
└── 2(+0)
└── 1(+0)
yükseklik: 2 | dönüş sayısı: 4
dengeli mi: true
inorder: [1 2 3 4 5 6 7]
1023 sıralı eleman eklendi:
AVL yüksekliği: 9
sıradan BST olsaydı: 1022
teorik alt sınır (log₂ 1023): 9
toplam dönüş: 1013
dengeli mi: true
500 eleman silindikten sonra:
eleman sayısı: 523 | yükseklik: 9
dengeli mi: true1023 sıralı eleman için sıradan BST'nin yüksekliği 1022 olurdu; AVL'de 9'da kalıyor. Bu, "her zaman O(log n)" garantisinin pratikte ne anlama geldiğinin somut karşılığıdır.
rebalance fonksiyonundaki sıra önemlidir: Önce yükseklik güncellenir, sonra denge faktörü hesaplanır, sonra gerekiyorsa iki adımlı dönüş yapılır. LR ve RL durumlarında ilk dönüş çocuk üzerinde, ikinci dönüş düğümün kendisi üzerinde yapılır.
Kırmızı-siyah ağaçlar
AVL ağacı katı bir denge kuralı uygular ve bu bir ödünleşme getirir: Aramalar çok hızlıdır çünkü ağaç sıkıca dengelidir, ama ekleme ve silmede daha fazla dönüş gerekir.
Kırmızı-siyah ağaçlar daha gevşek bir denge tanımı kullanır. Her düğüme bir renk atanır ve şu kurallar korunur: Kök siyahtır, kırmızı bir düğümün çocukları siyah olmalıdır, ve kökten her yaprağa giden yollarda aynı sayıda siyah düğüm bulunur. Bu kurallar, en uzun yolun en kısa yolun en fazla iki katı olmasını garanti eder.
Sonuç olarak kırmızı-siyah ağaçlar AVL'den bir miktar daha dengesiz olabilir — dolayısıyla aramalar biraz daha yavaştır — ama ekleme ve silmede daha az yeniden yapılandırma yapar. Bu yüzden yazma işlemlerinin yoğun olduğu genel amaçlı kütüphanelerde tercih edilirler. Java'nın sıralı map'i, C++'ın sıralı kapları ve Linux çekirdeğinin zamanlayıcısı kırmızı-siyah ağaç kullanır.
B-ağaçları ve veritabanları
İkili ağaçlar bellekte harika çalışır ama diskte tamamen farklı bir dünya vardır. Diskten okuma, bellekten okumaya göre on binlerce kat yavaştır ve disk verileri blok hâlinde okur — tipik olarak 4 ile 16 kilobayt arasında. Bu durumda ikili bir ağaçta her adımda tek bir düğüm okumak korkunç bir israftır: Koca bir bloğu getirip içindeki tek bir sayıyı kullanırsın.
B-ağacı bu gerçeğe göre tasarlanmıştır. Her düğümü bir disk bloğu kadar büyük yapar ve içine yüzlerce anahtar sığdırır. Bir düğümün yüzlerce çocuğu olduğunda ağacın yüksekliği çarpıcı biçimde düşer: Milyarlarca kaydı saklayan bir indekste bile kökten yaprağa yalnızca üç ya da dört adım vardır. Her adım bir disk okuması demek olduğundan, bu fark performansta her şeyi belirler.
B-ağacının bir türevi olan ve tüm gerçek verileri yalnızca yaprak seviyesinde tutan varyantı, veritabanı dünyasının fiilî standardıdır. Yapraklar birbirine bağlı olduğu için aralık taramaları da çok verimlidir: İlk kaydı bulup zincir boyunca ilerlemen yeterlidir. Kullandığın hemen her ilişkisel veritabanının birincil anahtar indeksi bu yapıyı kullanır.
Buradan çıkarılacak genel ders şudur: Bir veri yapısının "iyi" olup olmadığı, üzerinde çalıştığı donanımdan bağımsız düşünülemez. Karmaşıklık analizi tüm bellek erişimlerini eşit sayar; gerçek dünyada önbellek, disk ve ağ arasındaki uçurumlar tasarımı belirler.
Hangi dengeli yapıyı seçmeli?
Kendini dengeleyen ağaçların birden çok ailesi vardır ve aralarındaki fark, çoğu zaman sanıldığından daha az önemlidir. Yine de bir seçim yapman gerektiğinde aşağıdaki ölçütler yol gösterir.
Yük deseni neye benziyor? Okuma ile yazma oranı, en belirleyici ölçüttür. Neredeyse hiç değişmeyen ama sürekli sorgulanan bir yapıda sıkı dengeli bir ağaç kazandırır; sürekli güncellenen bir yapıda ise gevşek dengeli olan, daha az yeniden yapılandırma yaptığı için öne geçer.
Veri nerede duruyor? Bellekte duran yapılarla diskte duranlar tamamen farklı tasarımlar ister. Bellek için ikili ağaçlar uygundur; disk veya ağ üzerinden erişilen veriler için her düğümün çok sayıda çocuğu olan yapılar gerekir, çünkü asıl maliyet erişim sayısıdır.
Gerçekten bir ağaca ihtiyacın var mı? Bu soru genelde atlanır ama en önemlisidir. Veri kümesi değişmiyorsa, sıralı bir dilim üzerinde ikili arama yapmak her ağaçtan hızlıdır: Bellek bitişiktir, işaretçi yoktur, önbellek davranışı kusursuzdur. Eklemeler seyrekse ve toplu yapılabiliyorsa, listeyi yeniden sıralamak bile ağaç bakımından ucuza gelebilir.
Karmaşıklığı kim taşıyacak? Kendini dengeleyen bir ağacı doğru yazmak, özellikle silme tarafında, ciddi dikkat ister. Kendi uygulamanı yazacaksan test yükünü de hesaba kat; olgun bir kütüphane kullanabiliyorsan onu tercih et. Öğrenme amacıyla yazmak ise bambaşka bir konudur ve fazlasıyla değerlidir — dengeleme mantığını bir kez kendi ellerinle kurduğunda, bu yapıların neden böyle tasarlandığını bir daha unutmazsın.
Son bir not: Go'nun standart kütüphanesinde sıralı bir map ya da dengeli ağaç yoktur. Bu bilinçli bir sadelik tercihidir. İhtiyaç duyduğunda ya kendin yazarsın, ya bir kütüphane kullanırsın, ya da çoğu zaman olduğu gibi sıralı bir dilim ile ikili aramanın yeterli olduğunu fark edersin.
Sık yapılan hatalar
- Dönüşten sonra yükseklikleri güncellememek. Denge faktörleri yanlış hesaplanır ve ağaç bozulur.
- Yükseklik güncelleme sırasını karıştırmak. Önce eski kökün, sonra yeni kökün yüksekliği güncellenmelidir.
- LR ve RL durumlarını tek dönüşle çözmeye çalışmak. Zigzag şekiller iki dönüş gerektirir.
- Dönen yeni kökü ebeveyne bağlamayı unutmak.
n.Left = rebalance(n.Left)atamasının yapılması zorunludur. - Silmede dengelemeyi atlamak. Silme de dengeyi bozabilir; geri dönüş yolunda her düğüm kontrol edilmelidir.
- Yüksekliği her seferinde yeniden hesaplamak. Düğümde saklanmazsa her kontrol O(n) olur ve tüm avantaj kaybolur.
- Her durumda AVL kullanmak. Veri sabitse sıralı dilim + ikili arama daha hızlı ve çok daha basittir.
Alıştırmalar
Sola ve sağa dönüş fonksiyonlarını yaz ve her dönüşten sonra inorder gezinmenin değişmediğini doğrula. En az üç farklı ağaç şekliyle dene.
İpucu
Dönüş BST sırasını korumalıdır. Dönüşten önce ve sonra inorder dizilerini karşılaştır.
Çözümü göster
package main
import (
"fmt"
"slices"
)
type Node struct {
Value int
Height int
Left, Right *Node
}
func height(n *Node) int {
if n == nil {
return -1
}
return n.Height
}
func updateHeight(n *Node) {
n.Height = 1 + max(height(n.Left), height(n.Right))
}
func newNode(v int, left, right *Node) *Node {
n := &Node{Value: v, Left: left, Right: right}
updateHeight(n)
return n
}
func rotateRight(y *Node) *Node {
x := y.Left
y.Left = x.Right
x.Right = y
updateHeight(y)
updateHeight(x)
return x
}
func rotateLeft(x *Node) *Node {
y := x.Right
x.Right = y.Left
y.Left = x
updateHeight(x)
updateHeight(y)
return y
}
func inorder(n *Node) []int {
if n == nil {
return nil
}
out := inorder(n.Left)
out = append(out, n.Value)
return append(out, inorder(n.Right)...)
}
func main() {
trees := []struct {
name string
tree *Node
left bool // true: sola dönüş
}{
{"sağa uzayan", newNode(10, nil, newNode(20, nil, newNode(30, nil, nil))), true},
{"sola uzayan", newNode(30, newNode(20, newNode(10, nil, nil), nil), nil), false},
{"dolu ağaç", newNode(50,
newNode(30, newNode(20, nil, nil), newNode(40, nil, nil)),
newNode(70, nil, nil)), false},
}
for _, tc := range trees {
before := inorder(tc.tree)
hBefore := tc.tree.Height
var after *Node
var dir string
if tc.left {
after, dir = rotateLeft(tc.tree), "sola"
} else {
after, dir = rotateRight(tc.tree), "sağa"
}
afterOrder := inorder(after)
fmt.Printf("%-14s %s dönüş: kök %d→%d yükseklik %d→%d sıra korundu=%t\n",
tc.name, dir, before[len(before)/2], after.Value,
hBefore, after.Height, slices.Equal(before, afterOrder))
fmt.Printf(" inorder: %v\n", afterOrder)
}
}sağa uzayan sola dönüş: kök 20→20 yükseklik 2→1 sıra korundu=true inorder: [10 20 30] sola uzayan sağa dönüş: kök 20→20 yükseklik 2→1 sıra korundu=true inorder: [10 20 30] dolu ağaç sağa dönüş: kök 40→30 yükseklik 2→2 sıra korundu=true inorder: [20 30 40 50 70]
Dönüşün BST sırasını koruması tesadüf değil, tanımının bir sonucudur: Dönüş yalnızca hangi düğümün "üstte" olduğunu değiştirir; hangi değerin hangi değerden küçük olduğu bilgisine dokunmaz. Bu yüzden dengeleme, aramanın doğruluğunu hiçbir zaman bozmaz.
LL, RR, LR ve RL durumlarının her birini tetikleyen üçer elemanlı ekleme sıraları bul. Her durumda hangi dönüşlerin yapıldığını ve son ağacın kökünü raporla.
İpucu
LL: azalan sıra. RR: artan sıra. LR: önce büyük, sonra küçük, sonra ortadaki. RL: önce küçük, sonra büyük, sonra ortadaki.
Çözümü göster
package main
import "fmt"
type Node struct {
Value int
Height int
Left, Right *Node
}
type AVL struct {
root *Node
applied []string
}
func height(n *Node) int {
if n == nil {
return -1
}
return n.Height
}
func bf(n *Node) int {
if n == nil {
return 0
}
return height(n.Left) - height(n.Right)
}
func updateHeight(n *Node) {
n.Height = 1 + max(height(n.Left), height(n.Right))
}
func (t *AVL) rotateRight(y *Node) *Node {
x := y.Left
y.Left = x.Right
x.Right = y
updateHeight(y)
updateHeight(x)
return x
}
func (t *AVL) rotateLeft(x *Node) *Node {
y := x.Right
x.Right = y.Left
y.Left = x
updateHeight(x)
updateHeight(y)
return y
}
func (t *AVL) rebalance(n *Node) *Node {
updateHeight(n)
switch b := bf(n); {
case b > 1 && bf(n.Left) >= 0:
t.applied = append(t.applied, "LL: sağa dönüş")
return t.rotateRight(n)
case b > 1:
t.applied = append(t.applied, "LR: sola + sağa dönüş")
n.Left = t.rotateLeft(n.Left)
return t.rotateRight(n)
case b < -1 && bf(n.Right) <= 0:
t.applied = append(t.applied, "RR: sola dönüş")
return t.rotateLeft(n)
case b < -1:
t.applied = append(t.applied, "RL: sağa + sola dönüş")
n.Right = t.rotateRight(n.Right)
return t.rotateLeft(n)
}
return n
}
func (t *AVL) Insert(v int) {
var ins func(*Node, int) *Node
ins = func(n *Node, v int) *Node {
if n == nil {
return &Node{Value: v}
}
if v < n.Value {
n.Left = ins(n.Left, v)
} else if v > n.Value {
n.Right = ins(n.Right, v)
}
return t.rebalance(n)
}
t.root = ins(t.root, v)
}
func inorder(n *Node) []int {
if n == nil {
return nil
}
out := inorder(n.Left)
out = append(out, n.Value)
return append(out, inorder(n.Right)...)
}
func main() {
cases := []struct {
name string
values []int
}{
{"LL", []int{30, 20, 10}},
{"RR", []int{10, 20, 30}},
{"LR", []int{30, 10, 20}},
{"RL", []int{10, 30, 20}},
}
for _, c := range cases {
var t AVL
for _, v := range c.values {
t.Insert(v)
}
fmt.Printf("%s durumu %v → kök=%d yükseklik=%d\n",
c.name, c.values, t.root.Value, t.root.Height)
fmt.Printf(" uygulanan: %v\n", t.applied)
fmt.Printf(" inorder: %v\n", inorder(t.root))
}
}LL durumu [30 20 10] → kök=20 yükseklik=1 uygulanan: [LL: sağa dönüş] inorder: [10 20 30] RR durumu [10 20 30] → kök=20 yükseklik=1 uygulanan: [RR: sola dönüş] inorder: [10 20 30] LR durumu [30 10 20] → kök=20 yükseklik=1 uygulanan: [LR: sola + sağa dönüş] inorder: [10 20 30] RL durumu [10 30 20] → kök=20 yükseklik=1 uygulanan: [RL: sağa + sola dönüş] inorder: [10 20 30]
Dört durumun da aynı sonuca ulaştığına dikkat et: Kök 20, yükseklik 1, mükemmel dengeli bir ağaç. Giriş sırası ne olursa olsun AVL aynı dengeli şekle yakınsar. Bu, kendini dengeleyen yapıların temel vaadidir: Performans, verinin geliş sırasına bağlı olmaktan çıkar.
Aynı veri kümesini hem sıradan BST'ye hem AVL'ye ekleyip yükseklik, arama adımı ve ekleme maliyetini karşılaştıran bir ölçüm programı yaz. Üç farklı veri deseni kullan: sıralı, ters sıralı ve rastgele (sabit tohumlu).
İpucu
math/rand/v2 paketindeki rand.New(rand.NewPCG(1, 2)) sabit tohumlu ve deterministik bir üreteç verir.
Çözümü göster
package main
import (
"fmt"
"math/rand/v2"
)
type Node struct {
Value int
Height int
Left, Right *Node
}
func height(n *Node) int {
if n == nil {
return -1
}
return n.Height
}
func bf(n *Node) int {
if n == nil {
return 0
}
return height(n.Left) - height(n.Right)
}
func updateHeight(n *Node) {
n.Height = 1 + max(height(n.Left), height(n.Right))
}
func rotateRight(y *Node) *Node {
x := y.Left
y.Left = x.Right
x.Right = y
updateHeight(y)
updateHeight(x)
return x
}
func rotateLeft(x *Node) *Node {
y := x.Right
x.Right = y.Left
y.Left = x
updateHeight(x)
updateHeight(y)
return y
}
// plainInsert: dengeleme yok
func plainInsert(n *Node, v int) *Node {
if n == nil {
return &Node{Value: v}
}
if v < n.Value {
n.Left = plainInsert(n.Left, v)
} else if v > n.Value {
n.Right = plainInsert(n.Right, v)
}
updateHeight(n)
return n
}
// avlInsert: dengeleyerek ekler
func avlInsert(n *Node, v int, rotations *int) *Node {
if n == nil {
return &Node{Value: v}
}
if v < n.Value {
n.Left = avlInsert(n.Left, v, rotations)
} else if v > n.Value {
n.Right = avlInsert(n.Right, v, rotations)
} else {
return n
}
updateHeight(n)
switch b := bf(n); {
case b > 1 && bf(n.Left) >= 0:
*rotations++
return rotateRight(n)
case b > 1:
*rotations += 2
n.Left = rotateLeft(n.Left)
return rotateRight(n)
case b < -1 && bf(n.Right) <= 0:
*rotations++
return rotateLeft(n)
case b < -1:
*rotations += 2
n.Right = rotateRight(n.Right)
return rotateLeft(n)
}
return n
}
func searchSteps(n *Node, v int) int {
steps := 0
for n != nil {
steps++
switch {
case v < n.Value:
n = n.Left
case v > n.Value:
n = n.Right
default:
return steps
}
}
return steps
}
func totalSearchSteps(root *Node, values []int) int {
total := 0
for _, v := range values {
total += searchSteps(root, v)
}
return total
}
func main() {
const n = 511
r := rand.New(rand.NewPCG(1, 2))
sorted := make([]int, n)
reversed := make([]int, n)
random := make([]int, n)
for i := range n {
sorted[i] = i + 1
reversed[i] = n - i
random[i] = i + 1
}
r.Shuffle(n, func(i, j int) { random[i], random[j] = random[j], random[i] })
datasets := []struct {
name string
values []int
}{
{"sıralı", sorted},
{"ters sıralı", reversed},
{"rastgele", random},
}
fmt.Printf("%-14s %-8s %10s %14s %10s\n", "veri", "yapı", "yükseklik", "toplam arama", "dönüş")
for _, ds := range datasets {
var plain *Node
for _, v := range ds.values {
plain = plainInsert(plain, v)
}
var avl *Node
rotations := 0
for _, v := range ds.values {
avl = avlInsert(avl, v, &rotations)
}
fmt.Printf("%-14s %-8s %10d %14d %10s\n",
ds.name, "BST", height(plain), totalSearchSteps(plain, ds.values), "-")
fmt.Printf("%-14s %-8s %10d %14d %10d\n",
"", "AVL", height(avl), totalSearchSteps(avl, ds.values), rotations)
}
fmt.Println()
fmt.Println("teorik en iyi yükseklik (log₂ 511):", 8)
}veri yapı yükseklik toplam arama dönüş
sıralı BST 510 130816 -
AVL 8 4097 502
ters sıralı BST 510 130816 -
AVL 8 4097 502
rastgele BST 20 5939 -
AVL 10 4181 350
teorik en iyi yükseklik (log₂ 511): 8Sonuçlar üç önemli şeyi gösteriyor. Birincisi, sıralı ve ters sıralı verilerde sıradan BST tamamen çöküyor; AVL ise teorik en iyiye çok yakın kalıyor. İkincisi, rastgele veride sıradan BST şaşırtıcı derecede iyi çalışıyor — rastgele eklenen bir BST'nin beklenen yüksekliği yaklaşık 1,39 log n'dir, yani AVL'ye oldukça yakın. Üçüncüsü, AVL'nin bedeli dönüşlerdir; sıralı veride her eklemede bir dönüş gerekiyor.
Pratik sonuç şudur: Verinin rastgele olduğundan emin olabiliyorsan sıradan BST yeterlidir. Ama bu varsayım gerçek sistemlerde nadiren geçerlidir ve bir kez bozulduğunda bedeli çok ağırdır. Kendini dengeleyen yapılar, bu riski tamamen ortadan kaldırdıkları için tercih edilir.
Kısa sınav
AVL ağacında denge faktörü nasıl tanımlanır?
Bir dönüş (rotation) işlemi ne kadar sürer?
LR (sol-sağ) dengesizliği nasıl düzeltilir?
AVL ağacının yüksekliği için üst sınır nedir?
Kırmızı-siyah ağaçlar AVL'ye göre hangi durumda tercih edilir?
Veritabanı indekslerinde ikili ağaçlar yerine B-ağaçları neden kullanılır?
Özet
- AVL ağacı, her düğümde sol ve sağ alt ağaç yüksekliklerinin farkını en fazla 1 ile sınırlar.
- Bu kısıt, yüksekliği 1,44 log₂ n ile sınırlar ve tüm işlemler için kesin O(log n) garantisi verir.
- Denge faktörü = sol yükseklik − sağ yükseklik; ±2 olduğunda düzeltme yapılır.
- Dönüşler BST sırasını bozmadan ağacın şeklini değiştirir ve O(1) sürer.
- Dört dengesizlik durumu vardır: LL ve RR tek dönüşle, LR ve RL iki dönüşle düzeltilir.
- Dönüşten sonra yükseklikler doğru sırada güncellenmeli; önce alttaki düğüm, sonra yeni kök.
- Silme de dengeyi bozabilir; geri dönüş yolunda her düğüm yeniden dengelenmelidir.
- Kırmızı-siyah ağaçlar daha gevşek dengelidir: aramada biraz yavaş, yazmada daha ucuz.
- B-ağaçları disk blokları için tasarlanmıştır; veritabanı indekslerinin standart yapısıdır.