Bölüm 10: Arama Ağaçları

10.1Arama ağaçları

Bir telefon rehberinde “Yılmaz” soyadını arayan kimse rehberi ilk sayfadan okumaya başlamaz. Rehberi ortadan açar, soyadın o sayfadan önce mi sonra mı geldiğine bakar ve aramayı yarısına indirir. Bu yöntem rehber sıralı olduğu için işler. Bilgisayarda aynı yöntemin adı ikili aramadır ve sıralı bir dizide n öğe arasında aranan öğeyi yaklaşık log₂ n karşılaştırmada bulur.

Sıralı dizinin zayıf yanı güncellemedir. Rehbere yeni bir kişi eklemek için ondan sonra gelen bütün kayıtların bir sıra kaydırılması gerekir; bu, en kötü durumda n kaydırma demektir. Bağlı listede ekleme ve silme ucuzdur, ama listenin ortasına doğrudan atlanamaz; arama baştan başlayıp öğe öğe ilerler. Arama ağaçları bu iki yapının arasında durur. Bağlı yapıları sayesinde ekleme ve silme yalnız birkaç bağı değiştirir. Sıralı düzenleri sayesinde de arama her adımda kalan adayların bir kısmını eler.

10.1.1Arama ağacı nedir?

Ağaçla ilgili temel kavramları kısaca hatırlayalım. Bir ağaç, düğümlerden ve düğümleri birbirine bağlayan kenarlardan oluşur. En üstteki düğüme kök (root), çocuğu olmayan düğümlere yaprak (leaf) denir. Bir düğümün derinliği (depth), kökten o düğüme inen yoldaki kenar sayısıdır; kökün derinliği 0'dır. Ağacın yüksekliği (height) ise en derin düğümün derinliğidir. Yükseklik genellikle h ile gösterilir. Tek düğümlü ağacın yüksekliği 0, boş ağacınki ise −1 kabul edilir.

Arama ağacında her düğüm bir öğe taşır ve her öğenin bir anahtarı (key) vardır. Anahtar, öğeyi ötekilerden ayıran ve karşılaştırılabilen değerdir: öğrenci kaydında öğrenci numarası, sözlükte kelimenin kendisi, rehberde soyadı. Öğenin geri kalanı (ad, adres, not ortalaması) anahtara bağlı olarak saklanır. Bu notta örnekleri sade tutmak için anahtar çoğunlukla bir tamsayıdır ve düğümde yalnız o tamsayı vardır.

Tanımın son cümlesi bölümün bütün hikâyesini özetler. Arama, ekleme ve silme kökten aşağı tek bir yol izler. Yolun uzunluğu en çok ağacın yüksekliği kadardır. Öyleyse bu işlemlerin maliyeti O(h)'dir. Yükseklik küçük kalırsa işlemler hızlı olur, büyürse yavaşlar.

n düğümlü bir ağacın yüksekliği ne kadar olabilir? İki uç durum vardır. En kötü durumda her düğümün tek çocuğu olur ve ağaç bir zincire dönüşür; bu durumda yükseklik n − 1'dir. En iyi durumda her düzey tamamen doludur. Derinliği d olan düzeyde en çok 2^d düğüm bulunabilir. Öyleyse yüksekliği h olan ikili ağaçta en çok 1 + 2 + 4 + … + 2^h = 2^h+1 − 1 düğüm vardır. n ≤ 2^h+1 − 1 eşitsizliğinden h ≥ log₂(n + 1) − 1 çıkar; yani en iyi durumda yükseklik yaklaşık log₂ n'dir.

Bu fark, bölümün geri kalanındaki bütün yapıların varlık nedenidir. Düz ikili arama ağacı yükseklik için hiçbir söz vermez. AVL ve kırmızı-siyah ağaçlar, her güncellemeden sonra ağacı küçük yerel değişikliklerle düzelterek h = O(log n) garantisi verir. Splay ağacı tek tek işlemler için söz vermez, ama uzun işlem dizilerinin ortalamasında aynı sınıra ulaşır. B-ağacı ise düğüm başına çok anahtar tutarak ağacı hem kısa hem geniş yapar.

10.1.2Temel işlemler

Bir arama ağacından beklenen işlemler, sıralı bir koleksiyondan beklenenlerle aynıdır. Tablo 10.1 bunları ve bu notta kullanılan metot adlarını verir.

Sıralı düzen birkaç sorguyu daha mümkün kılar. En küçük ve en büyük anahtar bunların ilk ikisidir. Bir anahtarın ardılı kendisinden büyük en küçük anahtar, öncülü ise kendisinden küçük en büyük anahtardır. Son sorgu, belli bir aralığa düşen bütün anahtarları ister. Bu sorguların ortak noktası, hepsinin de kökten tek bir yol izlemesidir. Gezinme dışındaki bütün işlemler bu yüzden O(h) sürer. Gezinme ise her düğümü bir kez ziyaret ettiği için O(n)'dir.

Hash tablosu da arama ve eklemeyi ortalama sabit sürede yapar. Arama ağacını ondan ayıran şey bu sıralı sorgulardır. Hash tablosu anahtarları dağıtarak saklar. “50'den büyük en küçük anahtar hangisi?” ya da “20 ile 45 arasındaki anahtarları sırayla ver” gibi sorular için bütün tabloyu taraması gerekir. Arama ağacı ise bu soruları da O(h) ya da O(h + s) sürede cevaplar; s burada döndürülen anahtar sayısıdır.

10.1.3Arama ağacı türleri

Bölümde dört ikili arama ağacı türü ve iki çok yollu ağaç işlenir. İkili türlerin hepsinde aynı sıralama kuralı geçerlidir; farkları, yüksekliği nasıl ve ne ölçüde denetledikleridir. Şekil 10.2 dört ikili türün küçük birer örneğini gösterir.

• İkili arama ağacı (binary search tree, kısaca BST): Her düğümün anahtarı, sol alt ağacındaki anahtarların hepsinden büyük, sağ alt ağacındakilerin hepsinden küçüktür. Denge garantisi yoktur; şekli ekleme sırasına bağlıdır.
• AVL ağacı: Her düğümde iki alt ağacın yükseklik farkı, yani denge faktörü en çok 1'dir. Bu koşul bozulunca döndürmelerle düzeltilir.
• Kırmızı-siyah ağaç (red-black tree): Düğümler kırmızı ya da siyaha boyanır. Renk kuralları yüksekliği en çok 2 log₂(n + 1) ile sınırlar.
• Splay ağacı (splay tree): Erişilen düğümü döndürmelerle köke taşır. Tek bir işlem pahalı olabilir, ama işlem başına amortize maliyet O(log n)'dir.

Çok yollu ağaçlarda (B-ağacı ve B+ ağacı) bir düğüm birden çok anahtar ve ikiden çok çocuk taşır. Bu ağaçlar özellikle verinin diskte durduğu durumlar için tasarlanmıştır ve 10.7'nin konusudur.

10.2İkili arama ağacı

İkili ağaçta her düğümün en çok iki çocuğu vardır: sol çocuk ve sağ çocuk. İkili arama ağacı, ikili ağaca bir sıralama kuralı ekler. Bu kural sayesinde ağaç, sıralı bir dizinin “bağlı” bir karşılığı gibi davranır.

10.2.1BST özelliği

Tanımdaki “bütün” sözcüğü önemlidir. Koşul yalnız düğüm ile çocukları arasında değil, düğüm ile bütün torunları arasında da geçerlidir. Kökün sol alt ağacındaki en derin yaprak bile kökten küçük olmak zorundadır. Şekil 10.3 bu farkı gösterir. Soldaki ağaç geçerli bir BST'dir. Sağdakinde 4'ün sağ çocuğu olarak 7 eklenmiştir. Yalnız 4 ile 7'ye bakılırsa sorun yoktur: 7, 4'ün sağındadır ve 4'ten büyüktür. Ama 7, 6'nın sol alt ağacındadır ve 6'dan büyüktür. Bu yüzden sağdaki ağaç BST değildir.

BST özelliğinin doğrudan bir sonucu şudur: bir düğümün anahtarı, ağacın kalanını iki parçaya böler. Küçük anahtarların hepsi solda, büyüklerin hepsi sağdadır. Bu, sıralı dizide ortadaki öğenin diziyi ikiye bölmesine benzer. İkili aramanın her adımda aralığı yarıya indirmesi gibi, BST'de de her düğümde aramanın gideceği taraf kesinleşir ve öbür taraf tamamen elenir.

Aynı anahtar ağaçta iki kez bulunabilir mi? Tanım katı eşitsizlik kullandığı için hayır. Uygulamada iki yol vardır. Birincisi, tekrarlayan anahtarları reddetmektir; bu notun kodları böyle davranır. İkincisi, eşit anahtarları tutarlı biçimde hep aynı tarafa, örneğin hep sağa koymaktır. Hangisi seçilirse seçilsin, arama, ekleme ve silme aynı kurala uymalıdır. Yoksa eklenen bir anahtar sonra bulunamayabilir.

10.2.2Düğüm yapısı

BST'nin her düğümü üç alandan oluşur: veri (anahtar), sol çocuğa bir referans ve sağ çocuğa bir referans (Şekil 10.4). Çocuğu olmayan tarafta referans null'dır. Yaprakta iki referans da null'dır. Bağlı listedeki düğümle karşılaştırırsak tek fark, bir “sonraki” yerine iki çocuk referansının bulunmasıdır.

Sunumda düğüm iki biçimde yazılır. İlki yalnız int anahtar tutan sade bir sınıftır:

class AgacDugumu {
    int veri;
    AgacDugumu sol, sag;

    AgacDugumu(int veri) {
        this.veri = veri;
        this.sol = null;
        this.sag = null;
    }
}

Yapıcı, veriyi yazar ve iki çocuğu açıkça null yapar. Java'da referans türündeki alanlar zaten null ile başladığı için son iki atama zorunlu değildir; okuyana niyeti göstermek için yazılmıştır. Ardıl, aralık sorgusu ve BST doğrulama kodları bu sınıfı kullanır; alan adları kısadır: sol ve sag.

İkinci biçim jenerik (generic) sınıftır. Anahtar tamsayı olmak zorunda değildir; karşılaştırılabilen her tür olabilir:

class IkiliAgacDugum<E extends Comparable<E>> {
    E veri;                    // nesne
    IkiliAgacDugum<E> solCocuk; // sol çocuk
    IkiliAgacDugum<E> sagCocuk; // sağ çocuk

    IkiliAgacDugum(E veri) {
        this.veri = veri;
        // çocuklar başlangıçta null
    }
}

Tür parametresi E extends Comparable<E> biçiminde sınırlanmıştır. Bu, “E türünden iki nesne compareTo ile karşılaştırılabilmelidir” demektir. Integer, String ve LocalDate gibi sınıflar Comparable'ı gerçekler; bu yüzden hepsi anahtar olabilir. a.compareTo(b) çağrısı a < b ise negatif, eşitse 0, a > b ise pozitif bir sayı döndürür. Arama, ekleme ve silme kodları karar verirken yalnız bu işarete bakar. Bu sınıfta alan adları solCocuk ve sagCocuk'tur.

Bellek açısından her düğüm, verinin yanında iki referans taşır. n düğümlü ağaç bu yüzden O(n) bellek kullanır. Dengeli ağaç türleri düğüme küçük bir ek bilgi ekler: AVL ağacında yükseklik, kırmızı-siyah ağaçta bir bitlik renk. Bu ekler de düğüm başına sabittir; toplam bellek yine O(n) kalır.

10.2.3En küçük ve en büyük anahtar

BST özelliğinden ilk çıkan sonuç, en küçük ve en büyük anahtarın yeridir. Bir düğümün sol alt ağacında ondan küçük anahtarlar vardır. Öyleyse sol çocuğu olan bir düğüm en küçük olamaz; daha küçüğü solundadır. Bu akıl yürütme en küçük anahtara kökten başlayıp hep sola inerek ulaşıldığını gösterir. İniş, sol çocuğu olmayan ilk düğümde durur; o düğüm en küçüktür. En büyük için aynı yol sağa doğru izlenir (Şekil 10.5).

Sunumdaki kod iki metodu bir arada verir:

IkiliAgacDugum<E> minDeger(
        IkiliAgacDugum<E> dugum) {
    while (dugum.solCocuk != null)
        dugum = dugum.solCocuk; // sola in
    return dugum;  // en küçük
}
IkiliAgacDugum<E> maxDeger(
        IkiliAgacDugum<E> dugum) {
    while (dugum.sagCocuk != null)
        dugum = dugum.sagCocuk; // sağa in
    return dugum;  // en büyük
}

minDeger, kendisine verilen düğümden başlar. Döngü koşulu “bu düğümün sol çocuğu var mı?” sorusudur. Varsa dugum sol çocuğa geçer. Sol çocuk null olunca döngü biter ve o anki düğüm döndürülür. maxDeger aynı işi sağ çocuklarla yapar. İki metodun da ön koşulu ağacın boş olmamasıdır; dugum başlangıçta null olursa dugum.solCocuk ifadesi NullPointerException fırlatır.

Metotlar hiç anahtar karşılaştırması yapmaz; yalnız bağları izler. Her döngü turunda bir düzey aşağı inilir. En çok h tur dönülür, dolayısıyla süre O(h)'dir. Ek bellek olarak yalnız bir değişken kullanılır: O(1).

Metotların parametre olarak kökü değil herhangi bir düğümü alması bilinçli bir seçimdir. Silme kodu, iki çocuklu bir düğümün yerine koyacağı değeri bulmak için minDeger'i o düğümün sağ alt ağacının kökünden başlatır. Yani aynı metot “bütün ağacın en küçüğü” için de “bir alt ağacın en küçüğü” için de kullanılır.

10.2.4Kod izleme: minDeger ve maxDeger

İzleme, Şekil 10.5'teki ağaç üzerinde yapılır. Ağaç 6, 2, 8, 1, 4, 3 sırasıyla eklenerek oluşmuştur: kök 6; solunda 2, sağında 8; 2'nin çocukları 1 ve 4; 4'ün sol çocuğu 3. Tablo 10.2 her döngü turunda dugum'ın nerede olduğunu ve koşulun nasıl değerlendirildiğini verir.

İzlemede dikkat çekici bir nokta vardır. Ağaçtaki en derin düğüm 3'tür, ama 3 en küçük değildir. 3, 4'ün solundadır; 4 de 2'nin sağındadır. Yani 3, 2'den büyüktür. En küçük anahtar en derin düğümde değil, en soldaki düğümdedir. Şekil 10.6 minDeger'in üç anını gösterir.

10.2.5Kök ortada gezinme

Gezinme, ağacın bütün düğümlerini belli bir sırayla ziyaret etmektir. İkili ağaçta üç klasik özyinelemeli sıra vardır: kök başta (preorder), kök ortada (inorder) ve kök sonda (postorder). Adlar, kökün iki alt ağaca göre ne zaman ziyaret edildiğini söyler. Kök ortada gezinmede önce sol alt ağaç, sonra kök, en son sağ alt ağaç gezilir.

void inorder(IkiliAgacDugum<E> d) {
    if (d == null) return;
    inorder(d.solCocuk);  // sol
    System.out.print(d.veri + " ");
    inorder(d.sagCocuk);  // sağ
}

Metot üç satırdan oluşur ve her satır sıranın bir parçasıdır. Boş alt ağaçta (d == null) hiçbir şey yapmadan döner; bu, özyinelemenin taban durumudur. Boş değilse önce sol alt ağacı bütünüyle gezer, sonra kendi verisini yazar, en son sağ alt ağacı gezer.

BST'de bu sıra çok değerli bir sonuç verir: anahtarlar küçükten büyüğe sıralı yazılır. Nedenini bir düğüm için düşünelim. Düğüm yazılmadan önce sol alt ağacının tamamı yazılmıştır ve oradaki her anahtar düğümden küçüktür. Düğümden sonra sağ alt ağaç yazılır ve oradaki her anahtar düğümden büyüktür. Her düğüm, kendinden küçüklerin hepsinden sonra ve kendinden büyüklerin hepsinden önce yazılır. Bu da tam olarak sıralı çıktının tanımıdır.

Teoremin tersi de doğrudur: kök ortada gezinmesi kesin artan sıra veren ikili ağaç bir BST'dir. Bu yüzden bir ağacın BST olup olmadığını denetlemenin bir yolu, kök ortada gezinip çıktının artan olduğuna bakmaktır.

Gezinme her düğümü bir kez yazar. Her düğüm için iki özyinelemeli çağrı yapılır; bunların toplam sayısı da O(n)'dir (n dolu düğüm için n + 1 boş çağrı vardır). Süre bu yüzden O(n)'dir. Bellek açısından çağrı yığınında en çok h + 1 çerçeve birikir: O(h).

10.2.6Kod izleme: inorder

Aynı altı düğümlü ağaçta inorder(kok) çağrıldığında olaylar Tablo 10.3'teki sırayla gelişir. “Bekleyenler” sütunu, o anda çağrı yığınında duran ve sol alt ağaçlarının bitmesini bekleyen düğümleri alttan üste sıralar.

Çıktı 1 2 3 4 6 8'dir ve sıralıdır. İzlemede her düğümün “bekleme” süresi dikkat çekicidir. 6 ilk çağrılan düğümdür, ama beşinci yazılır; çünkü kendisinden küçük dört anahtarın hepsi sol alt ağacındadır. 8 en son çağrılır ve en son yazılır. Şekil 10.7 izlemenin dört anını gösterir.

10.3BST işlemleri

BST'nin bütün güncelleme ve sorgu işlemleri aynı iskelete dayanır: kökten başla, aranan anahtarı düğümün anahtarıyla karşılaştır, küçükse sola, büyükse sağa in. İşlemleri birbirinden ayıran, bu inişin nerede durduğu ve durduktan sonra ne yapıldığıdır. Arama, eşit anahtarı bulunca ya da boş bir bağa düşünce durur. Ekleme boş bağa düşünce oraya yeni bir düğüm bağlar. Silme, bulduğu düğümü çocuk sayısına göre üç farklı biçimde ağaçtan çıkarır.

10.3.1Arama

Arama algoritması üç kuraldan oluşur:

1. Kökten başla. Düğümün anahtarı aranan anahtara eşitse arama başarıyla biter.
2. Aranan anahtar küçükse sol alt ağaçta, büyükse sağ alt ağaçta aynı işi tekrarla.
3. null bir bağa ulaşılırsa anahtar ağaçta yoktur.

Üçüncü kuralın doğruluğu BST özelliğinden gelir. Aranan anahtar ağaçta olsaydı, her adımda seçilen alt ağaçta olmak zorundaydı; çünkü öbür alt ağaçtaki anahtarların hepsi ya ondan küçük ya da ondan büyüktür. Seçilen alt ağaç boş çıktıysa anahtarın bulunabileceği başka yer kalmamıştır.

Sunumdaki kod jenerik düğüm sınıfıyla yazılmıştır ve özyinelemelidir:

boolean ara(IkiliAgacDugum<E> kok, E veri) {
    if (kok == null)
        return false;            // yok
    int k = veri.compareTo(kok.veri);
    if (k == 0)
        return true;             // bulundu
    else if (k < 0)
        return ara(kok.solCocuk, veri);
    else
        return ara(kok.sagCocuk, veri);
}

İlk if taban durumudur: boş alt ağaçta hiçbir anahtar yoktur, sonuç false'tur. Sonra aranan veri düğümün verisiyle bir kez karşılaştırılır ve sonuç k'de saklanır. k == 0 ise anahtar bulunmuştur. k < 0 ise aranan daha küçüktür ve arama sol alt ağaçta, k > 0 ise sağ alt ağaçta sürer. Özyinelemeli çağrının döndürdüğü değer, hiç değiştirilmeden yukarı aktarılır.

Karşılaştırmanın bir kez yapılıp sonucun bir değişkende tutulması hem okunabilirliği hem de verimi artırır. compareTo bir String ya da karmaşık bir nesne için pahalı olabilir; iki ayrı if'te iki kez çağırmak gereksizdir.

Maliyet açısından her çağrı bir düzey aşağı iner ve sabit iş yapar. Başarılı arama, bulunan düğümün derinliğinin bir fazlası kadar düğüme bakar. Başarısız arama bir yaprağın boş çocuğuna kadar iner ve en çok h + 1 düğüme bakar. İkisi de O(h)'dir. Özyinelemeli sürüm çağrı yığınında O(h) bellek kullanır. Aynı algoritma bir while döngüsüyle de yazılabilir; o zaman ek bellek O(1)'e iner. Özyinelemeli çağrı metodun son işi olduğu için bu dönüşüm mekaniktir: kok = kok.solCocuk ya da kok = kok.sagCocuk atanıp döngü başa döner.

10.3.2Kod izleme: ara

İki çağrıyı Şekil 10.8'deki ağaçta izleyelim: başarılı ara(kok, 5) ve başarısız ara(kok, 10). Şekildeki ağaç 6(4(2, 5), 8(7, 9)) biçimindedir. Tablo satırlarındaki her çağrı, çağrı yığınında yeni bir çerçeve açar.

Başarılı aramada üç düğümle karşılaştırma yapıldı. Bu sayı, 5'in derinliği olan 2'nin bir fazlasıdır. Başarısız aramada da üç düğüme bakıldı (6, 8, 9) ve dördüncü çağrı boş bir bağa düştü. Ağacın yüksekliği 2 olduğu için en çok h + 1 = 3 düğüme bakılabilirdi; iki arama da bu sınıra ulaştı. Yedi düğümlü ağaçta hiçbir arama üç karşılaştırmayı geçmez. Aynı yedi anahtar bir dizide sırasız dursaydı, başarısız bir arama yedi karşılaştırma isterdi.

10.3.3Ekleme

Yeni bir anahtar nereye eklenmelidir? Cevap aramanın kendisidir. Anahtar ağaçta aranıyormuş gibi kökten aşağı inilir. Anahtar ağaçta yoksa arama bir null bağda biter. Bu bağ, anahtarın BST özelliğini bozmadan durabileceği tek yerdir; çünkü yol boyunca her düğümde doğru tarafa dönülmüştür. Yeni düğüm oraya yaprak olarak bağlanır.

IkiliAgacDugum<E> ekle(
        IkiliAgacDugum<E> kok, E veri) {
    if (kok == null)
        return new IkiliAgacDugum<>(veri);
    int k = veri.compareTo(kok.veri);
    if (k < 0)
        kok.solCocuk = ekle(kok.solCocuk, veri);
    else if (k > 0)
        kok.sagCocuk = ekle(kok.sagCocuk, veri);
    // k == 0: anahtar zaten var, eklenmez
    return kok;
}
// kullanım: kok = ekle(kok, 5);

Kodun en önemli özelliği dönüş değeridir. ekle, kendisine verilen alt ağacın ekleme sonrasındaki kökünü döndürür. Boş bir alt ağaca ekleme yapılınca yeni düğüm oluşturulur ve döndürülür; artık o alt ağacın kökü bu yeni düğümdür. Boş olmayan alt ağaçta kök değişmez; metot çocuk bağını özyinelemeli çağrının sonucuyla günceller ve kendi kökünü döndürür.

kok.solCocuk = ekle(kok.solCocuk, veri) satırı ilk okumada gereksiz görünebilir: sol çocuk zaten oradadır, neden yeniden atanıyor? Atamanın tek gerçek işi, inişin sonunda yapılan atamadır. Yeni düğümün ebeveyni olacak düğümde kok.sagCocuk o ana kadar null'dır; çağrı yeni düğümü döndürür ve atama onu bağlar. Yol üzerindeki öteki atamalar bağı kendi değerine yeniden yazar ve hiçbir şeyi değiştirmez. Bu “gereksiz” atamalar sayesinde kod, yeni düğümün ebeveynini ayrıca hatırlamak zorunda kalmaz.

Aynı desen kullanımda da sürer: ağaca ekleme her zaman kok = ekle(kok, 5); biçiminde yazılır. Ağaç boşken (kok == null) ilk ekleme yeni bir kök oluşturur ve onu ancak bu atama kok değişkenine yazar.

Eşit anahtar geldiğinde (k == 0) iki if de atlanır ve metot hiçbir şeyi değiştirmeden kok'u döndürür; anahtar ikinci kez eklenmez. Eklemenin maliyeti aramayla aynıdır: kökten bir yaprağa inilir, her düzeyde sabit iş yapılır. Süre O(h), özyinelemeli sürümde çağrı yığını O(h)'dir. Yeni düğüm her zaman bir yaprak olarak eklenir; var olan düğümlerin yeri değişmez. Bu basitlik, düz BST'nin şeklinin bütünüyle ekleme sırasına bağlı olmasının da nedenidir.

10.3.4Kod izleme: ekle

Şekil 10.10'daki ağaca kok = ekle(kok, 5) çağrısıyla 5 eklenir. Tablo 10.5 hem inişi hem dönüşü gösterir. Dönüş satırlarında, her çerçevenin çocuk bağına hangi değeri atadığı yazılmıştır.

Sonuç ağacı 6(2(1, 4(3, 5)), 8)'dir ve kök ortada gezinmesi 1 2 3 4 5 6 8 verir. Üç düzey inildi, üç çerçeve açıldı ve geri dönüldü. Gerçekte değişen tek bağ 4'ün sağ bağıdır. Şekil 10.11, yeni düğümün oluştuğu ve bağlandığı anları gösterir.

10.3.5Ardıl, öncül, tavan ve taban

Sıralı bir listede her öğenin bir “sonraki” ve bir “önceki” komşusu vardır. BST'de bu komşulara ardıl ve öncül denir.

x ağaçtaysa ardılını bulmak için iki durum vardır (Şekil 10.12):

1. Sağ alt ağaç varsa, ardıl sağ alt ağacın en küçüğüdür: bir kez sağa, sonra hep sola inilir. x'ten büyük ve ona en yakın anahtarlar onun sağ alt ağacındadır; oradaki en küçük olan da ardıldır.
2. Sağ alt ağaç yoksa, ardıl, kökten x'e inerken solundan geçilen en yakın atadır. Örneğin 5'e 6 → 4 → 5 yoluyla inilir. Bu yolda 6'dan sola dönülmüştür; yani 5, 6'nın sol alt ağacındadır ve 6'dan küçüktür. 4'ten ise sağa dönülmüştür; 4, 5'ten küçüktür ve ardıl olamaz. Ardıl 6'dır.

Ardılın iki yüzlü bu tarifi koda geçirilirken birleştirilebilir. Kökten başlayıp aşağı inen tek bir döngü, yol boyunca “şimdiye kadarki en iyi aday”ı tutar:

AgacDugumu ardil(AgacDugumu kok, int x) {
    AgacDugumu aday = null; // x'ten büyük en küçük
    while (kok != null) {
        if (x < kok.veri) {
            aday = kok;     // kok bir aday
            kok = kok.sol;  // daha küçüğü solda
        } else
            kok = kok.sag;  // x'ten büyükler sağda
    }
    return aday;
}

Her düğümde iki olasılık vardır. x < kok.veri ise bu düğüm x'ten büyüktür ve bir ardıl adayıdır. Daha iyi bir aday, yani x'ten büyük ama bu düğümden küçük bir anahtar, ancak düğümün solunda olabilir; aday kaydedilir ve sola inilir. x ≥ kok.veri ise bu düğüm ve bütün sol alt ağacı x'ten küçük ya da ona eşittir; hiçbiri ardıl olamaz. x'ten büyükler ancak sağdadır; sağa inilir. Döngü boş bir bağda biter ve son aday döndürülür. Hiç aday bulunmadıysa sonuç null'dır; bu, x'in ağaçtaki en büyük anahtar ya da ondan büyük olduğu anlamına gelir.

Kod iki durumu kendiliğinden kapsar. Sağ alt ağaç varsa döngü x'i geçtikten sonra bir kez sağa, sonra adaylar toplayarak hep sola iner; son aday sağ alt ağacın en küçüğüdür. Sağ alt ağaç yoksa x'ten sonra döngü hemen biter ve son aday, solundan geçilen en yakın atadır. Üstelik kod x'in ağaçta bulunmasını da gerektirmez.

Ardılın akrabası üç sorgu daha vardır. Tablo 10.6 dördünü bir arada verir. Java'nın TreeMap ve TreeSet sınıfları bu sorguları hazır metotlar olarak sunar.

Öncül, ardılın aynadaki görüntüsüdür: x > kok.veri ise düğüm bir adaydır ve sağa inilir, değilse sola inilir. Tavan ile ardıl arasındaki tek fark eşitliktir: x ağaçta varsa tavan x'in kendisidir, ardıl ise ondan sonraki anahtardır. Taban da öncülün eşitliği kabul eden sürümüdür. Örnek ağaçta 3 yoktur; bu yüzden tavan(3) ardıl gibi 4'ü, taban(3) öncül gibi 2'yi verir. Dört sorgunun hepsi kökten tek bir yol izler ve O(h) sürer.

10.3.6Kod izleme: ardil

ardil(kok, 5) ve ardil(kok, 6) çağrıları, ardılın iki durumunu sırasıyla örnekler. Tablo 10.7'de her satır döngünün bir turudur.

İlk çağrıda aday kökte bulundu ve bir daha değişmedi: 5'in sağ alt ağacı yoktur, ardıl solundan geçilen ata 6'dır. İkinci çağrıda aday önce 8, sonra 7 oldu: 6'nın sağ alt ağacı vardır ve ardıl onun en küçüğüdür. Her iki çağrıda da üç düğüme bakıldı. Şekil 10.13 izlemenin dört anını gösterir.

10.3.7Silme: üç durum

Silme, BST işlemlerinin en dikkat isteyenidir. Önce silinecek düğüm aramayla bulunur; bu O(h) sürer. Ardından düğüm, çocuk sayısına göre ağaçtan çıkarılır. Amaç, BST özelliğini bozmadan düğümü koparmaktır. Örneklerde Şekil 10.14'teki ağaç kullanılır: kök 50; 40'ın çocukları 30 ve 45; 45'in sol çocuğu 42; 60'ın sağ çocuğu 70.

1. Yaprak. Silinecek düğümün çocuğu yoktur. Ebeveynin ona giden bağı null yapılır. Örnek: 70'in silinmesi; 60'ın sağ bağı null olur.
2. Tek çocuk. Düğüm atlanır: ebeveyn, doğrudan düğümün tek çocuğuna bağlanır. Örnek: 45 silinirken 40'ın sağ bağı 42'ye yönelir; 60 silinirken 50'nin sağ bağı 70'e yönelir.
3. İki çocuk. Düğüm doğrudan çıkarılamaz, çünkü ebeveyninin onun yerine bağlayabileceği tek bir bağ vardır, oysa düğümün iki çocuğu vardır. Bunun yerine düğümün değeri, kök ortada ardılının (sağ alt ağacın en küçüğü) ya da öncülünün (sol alt ağacın en büyüğü) değeriyle değiştirilir. Sonra ardıl ya da öncül kendi yerinden silinir. Örnek: 40'ın silinmesi.

Tek çocuk durumunun neden BST özelliğini koruduğunu görmek kolaydır. 45, 40'ın sağ alt ağacındadır; 45'in bütün torunları da öyledir ve 40'tan büyüktür. 42'yi 40'ın sağına bağlamak bu ilişkiyi değiştirmez. Aynı biçimde 42, 50'nin sol alt ağacında kalır ve 50'den küçüktür. Alt ağaç olduğu gibi bir düzey yukarı çekilmiş, sırası değişmemiştir.

İki çocuk durumunda neden ardıl seçilir? Silinen değerin yerine konacak değer, sol alt ağacın hepsinden büyük ve sağ alt ağacın hepsinden küçük olmalıdır. Kök ortada sırada silinen anahtarın hemen yanındaki iki anahtar bu koşulu sağlar: öncül ve ardıl. 40'ın ardılı 42'dir. 42, 40'ın sağ alt ağacındaki en küçük anahtardır; yani sağ alt ağaçtaki öteki anahtarlardan küçüktür. 40'tan büyük olduğu için de sol alt ağaçtaki her anahtardan büyüktür. 42, 40'ın yerine konduğunda BST özelliği korunur.

Geriye ardılı eski yerinden silmek kalır. Bu silme her zaman kolay durumlardan birine düşer. Ardıl, sağ alt ağaçta hep sola inilerek bulunur ve sol çocuğu olmayan ilk düğümde durulur. Sol çocuğu yoktur; ya yapraktır ya da yalnız sağ çocuğu vardır. Yani ardılın silinmesi Durum 1 ya da Durum 2'dir; özyineleme bir daha iki çocuklu bir düğüme rastlamaz.

10.3.8Silme kodu

Üç durum, eklemedeki “alt ağacın yeni kökünü döndür” deseniyle tek bir özyinelemeli metotta toplanır:

IkiliAgacDugum<E> sil(
        IkiliAgacDugum<E> kok, E veri) {
    if (kok == null) return null;   // yok
    int k = veri.compareTo(kok.veri);
    if (k < 0)
        kok.solCocuk = sil(kok.solCocuk, veri);
    else if (k > 0)
        kok.sagCocuk = sil(kok.sagCocuk, veri);
    else if (kok.solCocuk == null)
        return kok.sagCocuk;  // yaprak/sağ çocuk
    else if (kok.sagCocuk == null)
        return kok.solCocuk;  // yalnız sol çocuk
    else {                    // iki çocuk
        kok.veri = minDeger(kok.sagCocuk).veri;
        kok.sagCocuk = sil(kok.sagCocuk, kok.veri);
    }
    return kok;
}

Metodun ilk yarısı aramadır. Anahtar bulunamazsa (kok == null) null döner; boş alt ağaçtan silme yapılınca alt ağaç boş kalır ve ağaç değişmez. k < 0 ya da k > 0 ise silme ilgili alt ağaçta sürer ve sonuç çocuk bağına atanır.

k == 0 olduğunda silinecek düğüm bulunmuştur ve üç durum üç dalda ele alınır:

• kok.solCocuk == null ise kok.sagCocuk döndürülür. Bu dal iki durumu birden kapsar. Düğüm yapraksa sağ çocuk da null'dır ve null döner; ebeveynin bağı boşalır. Düğümün yalnız sağ çocuğu varsa o çocuk döner; ebeveyn doğrudan ona bağlanır.
• kok.sagCocuk == null ise (sol çocuk var, sağ yok) sol çocuk döndürülür.
• İki çocuk varsa minDeger(kok.sagCocuk) ardılı bulur ve değeri düğüme kopyalanır. Sonra sil(kok.sagCocuk, kok.veri) ardılı sağ alt ağaçtan siler. Burada kok.veri artık ardılın değeridir.

Düğümün ağaçtan kopması, döndürülen değerin ebeveynin bağına atanmasıyla olur. Yaprak ya da tek çocuk durumunda metot silinen düğümü değil, onun yerine geçecek olanı döndürür. Ebeveyn bu değeri kendi bağına yazar ve silinen düğüme giden referans kaybolur. Java'nın çöp toplayıcısı (garbage collector) artık hiçbir referansın göstermediği düğümü bir süre sonra temizler. Kullanım her zaman kok = sil(kok, 40); biçimindedir; kök silinirse yeni kök ancak bu atamayla kok değişkenine yazılır.

Maliyeti bulalım. Silinecek düğüme kadar iniş O(h)'dir. İki çocuk durumunda minDeger aynı yoldan aşağı devam eder. İkinci sil çağrısı da ardıla kadar yeniden iner. Bu iki iniş silinen düğümün altında kalır ve toplamları O(h)'yi geçmez. Silme O(h) zamanda yapılır.

10.3.9Kod izleme: üç silme

Üç silme de Şekil 10.14'teki orijinal ağaçtan başlar. Tablo 10.8 her çerçevenin karşılaştırmasını ve dönüşte bağına atadığı değeri verir.

Üç sonucun kök ortada gezinmeleri sırasıyla 30 40 42 45 50 60, 30 40 42 50 60 70 ve 30 42 45 50 60 70'tir. Her birinde silinen anahtar kaybolmuş, kalanların sırası korunmuştur. Üç izlemede kök hiç değişmedi; main'deki kok = sil(…) ataması her seferinde yine 50'yi yazdı.

Üçüncü izleme ayrıntılı incelenmeye değer, çünkü iki ayrı silme iç içe çalışır. Tablo 10.9 bu çağrıyı adım adım verir.

Dikkat edilirse 40'ı tutan düğüm nesnesi ağaçtan hiç çıkmadı; yalnız içindeki değer 42 oldu. Ağaçtan kopan nesne, eski 42'yi tutan yapraktır. Şekil 10.17 bu iki anı ve sonucu gösterir.

10.3.10BST işlemlerinin analizi

Buraya kadar görülen işlemlerin hepsi aynı sonuca vardı: arama, ekleme ve silmenin maliyeti, işlemin eriştiği en derin düğümün derinliğiyle orantılıdır. En kötü durumda bu derinlik ağacın yüksekliğidir; maliyet O(h)'dir. Öyleyse asıl soru şudur: n anahtarlı bir BST'nin yüksekliği ne kadardır?

Cevap, anahtarların ekleme sırasına bağlıdır. Aynı yedi anahtar 4, 2, 6, 1, 3, 5, 7 sırasıyla eklenirse yüksekliği 2 olan mükemmel bir ağaç oluşur. 1, 2, 3, 4, 5, 6, 7 sırasıyla eklenirse her yeni anahtar bir öncekinin sağına düşer ve ağaç sağa uzanan bir zincire dönüşür; yükseklik 6 olur. Böyle bir ağaca devrik (degenerate) ağaç denir. Devrik ağaç, fazladan bellek harcayan bir bağlı listeden farksızdır.

Tablonun orta satırı umut vericidir. Anahtarlar rastgele bir sırayla eklenirse, bir düğümün ortalama derinliği yaklaşık 2 ln n ≈ 1,39 log₂ n'dir. Bir milyon anahtarda bu, ortalama 28 civarında karşılaştırma demektir; en iyi durumdan yalnız %40 kadar fazladır. Bu sonuç, hızlı sıralamanın ortalama karşılaştırma sayısıyla aynı hesaptan çıkar: her anahtar kök olarak seçildiğinde kalan anahtarları rastgele iki gruba ayırır.

Sorun, gerçek verinin çoğu zaman rastgele olmamasıdır. Bir dosyadan okunan kayıtlar zaten sıralı olabilir; öğrenci numaraları kayıt sırasıyla artar; zaman damgaları hep büyür. Böyle bir girdi düz BST'yi en kötü duruma iter ve her işlem O(n) olur. n anahtarı sıralı biçimde eklemek de toplam 1 + 2 + … + (n − 1) = n(n − 1)/2, yani O(n²) karşılaştırma ister. Bir milyon anahtar için bu yarım trilyon karşılaştırmadır.

10.3.11Aralık sorgusu

Aralık sorgusu, [lo, hi] aralığına düşen bütün anahtarları sıralı olarak verir. “5 ile 10 arasındaki anahtarlar” ya da “not ortalaması 2,5 ile 3,0 arasındaki öğrenciler” bu tür sorgulardır. Basit bir çözüm, bütün ağacı kök ortada gezip aralıktakileri yazmaktır; ama bu, aralıkta kaç anahtar olursa olsun O(n) sürer. BST özelliği çok daha iyisini yapmaya izin verir: aralığa giremeyecek alt ağaçlara hiç inmemek. Buna budama (pruning) denir.

void aralik(AgacDugumu k, int lo, int hi) {
    if (k == null) return;
    if (lo < k.veri)           // solda aday var
        aralik(k.sol, lo, hi);
    if (lo <= k.veri && k.veri <= hi)
        System.out.print(k.veri + " ");
    if (k.veri < hi)           // sağda aday var
        aralik(k.sag, lo, hi);
}

Kod, kök ortada gezinmenin iki koşulla budanmış hâlidir. Sol alt ağaçtaki anahtarların hepsi k.veri'den küçüktür. lo < k.veri değilse, yani k.veri ≤ lo ise, sol alt ağaçtaki her anahtar lo'dan küçüktür ve hiçbiri aralığa giremez; sol alt ağaç atlanır. Aynı biçimde k.veri ≥ hi ise sağ alt ağaçtaki her anahtar hi'den büyüktür; sağ alt ağaç atlanır. Ortadaki if düğümün kendisini aralıktaysa yazar. Sıra sol–düğüm–sağ olduğu için çıktı sıralıdır.

Tablo 10.11, 8(4(2, 6(5, 7)), 12(10, 14)) ağacında aralik(kok, 5, 10) çağrısını izler.

Çıktı 5 6 7 8 10'dur ve sıralıdır. Ziyaret edilen düğümler 8, 4, 6, 5, 7, 12 ve 10'dur. 2 ve 14 hiç ziyaret edilmedi: 2, 4'ün solundaydı ve 4 zaten alt sınırdan küçüktü; 14, 12'nin sağındaydı ve 12 zaten üst sınırdan büyüktü. Şekil 10.19 izlemenin başını ve sonunu gösterir.

Maliyeti bulmak için ziyaret edilen düğümleri iki gruba ayıralım. Birinci grup aralıktaki düğümlerdir; s tane yazılır. İkinci grup aralığın dışında kalıp yine de ziyaret edilen düğümlerdir. Bunlar, aralığın sol ve sağ sınırına doğru inen iki yolun üzerindedir ve her yol en çok h + 1 düğüm içerir. Toplam maliyet O(h + s) olur. Dengeli bir ağaçta bir milyon anahtar arasından 10 anahtarlık bir aralık, yalnızca birkaç düzine düğüm ziyaret edilerek bulunur.

10.3.12Bir ağaç BST mi?

Bir ikili ağacın BST olup olmadığını denetlemek, BST özelliğinin “bütün alt ağaç için” geçerli olduğunu iyi anlamayı gerektirir. Her düğüm yalnız ebeveyniyle değil, bütün atalarıyla da uyumlu olmalıdır. Sol alt ağaca inerken bir üst sınır, sağ alt ağaca inerken bir alt sınır kazanılır. Bir düğüm, kökten ona inen yoldaki bütün bu sınırların içinde kalmalıdır.

boolean bstMi(AgacDugumu k, long min, long max) {
    if (k == null) return true;
    if (k.veri <= min || k.veri >= max)
        return false;          // aralık dışında
    return bstMi(k.sol, min, k.veri)
        && bstMi(k.sag, k.veri, max);
}
// ilk çağrı: bstMi(kok, Long.MIN_VALUE,
//                  Long.MAX_VALUE)

Metot her düğüme bir izinli aralık (min, max) taşır. Kök için aralık sınırsızdır; Long.MIN_VALUE ve Long.MAX_VALUE değerleri eksi ve artı sonsuzun yerine kullanılır. Anahtarlar int olduğu için long türündeki bu uç değerler hiçbir anahtara eşit olamaz. Düğüm aralığın dışındaysa false döner. İçindeyse sol çocuk için üst sınır düğümün kendi değeri olur, sağ çocuk için alt sınır. İki alt ağacın sonuçları && ile birleşir.

Tablo 10.12, sağdaki hatalı ağacı, yani 6(2(1, 4(3, 7)), 8) ağacını denetler.

7 için izinli aralık (4, 6)'dır. Alt sınır 4, 7'nin 4'ün sağında olmasından gelir. Üst sınır 6 ise 7'nin 6'nın sol alt ağacında olmasından gelir; bu sınır kökten iki düzey aşağı taşınmıştır. Yalnız ebeveyn–çocuk çiftlerine bakan bir denetim 4 < 7 olduğu için bu ağaca yanlışlıkla “BST” derdi. Doğru denetim her düğümü bir kez ziyaret eder; süre O(n), çağrı yığını O(h)'dir.

10.3.13Uygulama: öğrenci kayıtları

Gerçek uygulamalarda düğüm yalnız bir sayı değil, bütün bir kayıt taşır. Sunumdaki örnekte anahtar öğrenci numarasıdır ve düğüm öğrenci nesnesinin tamamını tutar:

public class Ogrenci {
    int ogrenciNo;     // anahtar
    String adSoyad;

    public Ogrenci(int ogrenciNo,
                   String adSoyad) {
        this.ogrenciNo = ogrenciNo;
        this.adSoyad = adSoyad;
    }
}

public class OgrenciDugum {
    Ogrenci ogr;           // veri
    OgrenciDugum solCocuk;
    OgrenciDugum sagCocuk;

    public OgrenciDugum(Ogrenci ogr) {
        this.ogr = ogr;
        // çocuklar başlangıçta null
    }
}

Ogrenci sınıfı veriyi, OgrenciDugum ise ağaç yapısını taşır. Bu ayrım, aynı öğrenci nesnesinin başka bir yapıda da (örneğin bir listede) kullanılabilmesini sağlar. Ekleme ve arama, tamsayı anahtarlı sürümlerle aynı mantıkla çalışır:

OgrenciDugum ekle(OgrenciDugum kok, Ogrenci ogr) {
    if (kok == null) return new OgrenciDugum(ogr);
    if (ogr.ogrenciNo < kok.ogr.ogrenciNo)
        kok.solCocuk = ekle(kok.solCocuk, ogr);   // soldan devam
    else if (ogr.ogrenciNo > kok.ogr.ogrenciNo)
        kok.sagCocuk = ekle(kok.sagCocuk, ogr);   // sağdan devam
    return kok;                                   // aynı numara eklenmez
}

Ogrenci ara(OgrenciDugum kok, int numara) {
    if (kok == null) return null;                // kayıt yok
    if (numara == kok.ogr.ogrenciNo) return kok.ogr; // bulundu
    if (numara < kok.ogr.ogrenciNo)
        return ara(kok.solCocuk, numara);         // soldan devam
    return ara(kok.sagCocuk, numara);             // sağdan devam
}

İki fark dikkat çeker. Birincisi, anahtar int olduğu için karşılaştırmalar <, > ve == ile doğrudan yapılır; compareTo gerekmez. İkincisi, ara boolean yerine öğrenci nesnesini döndürür. Bulunursa ad-soyad gibi bilgilere de erişilir; bulunamazsa null döner.

Aynı işi Java'da hazır bir sınıf görür: TreeMap<Integer, Ogrenci>. TreeMap anahtardan değere bir eşleme tutar ve içeride dengeli bir arama ağacı, kırmızı-siyah ağaç kullanır. put, get ve remove O(log n) sürer; higherKey, floorKey ve subMap gibi metotlar da ardıl, taban ve aralık sorgularını yapar. Elle yazılan BST'den farkı, sıralı girdiyle bile zincire dönüşmemesidir.

10.4Denge ve AVL ağaçları

BST işlemlerinin hepsi O(h) sürer ve h, en kötü durumda n − 1'e çıkar. Bu kesimin sorusu, yüksekliği her koşulda O(log n)'de tutmanın ucuz bir yolunun olup olmadığıdır. Cevap evettir ve ilk yolu 1962'de Adelson-Velsky ile Landis gösterdi.

10.4.1Denge ihtiyacı

Düz BST'nin şekli ekleme sırasına bağlıdır. 1, 2, 3, 4 sırayla eklenirse ağaç sağa uzanan bir zincir olur ve yüksekliği 3'tür. Oysa aynı dört anahtar, yüksekliği 2 olan ağaçlarda da durabilir. Şekil 10.21 iki seçeneği gösterir: kökü 2 olan 2(1, 3(—, 4)) ve kökü 3 olan 3(1(—, 2), 4). Üç ağacın da kök ortada gezinmesi 1 2 3 4'tür. Yani üçü de aynı sıralı kümeyi tutar; yalnız biçimleri farklıdır.

Tanımdaki “yerel” sözcüğü önemlidir. Bozulmuş bir ağacı tamamen yıkıp kök ortada sırasından dengeli biçimde yeniden kurmak mümkündür; ama bu her güncellemede O(n) sürer ve ağacın bütün avantajını yok eder. Dengeli ağaçlar yalnız ekleme ya da silmenin geçtiği yol üzerindeki birkaç düğüme dokunur. Bu yol O(log n) uzunluktadır ve her düğümde yapılan iş sabittir; güncellemenin toplam maliyeti yine O(log n) kalır.

10.4.2Dengeleme örneği

Daha büyük bir örnek, yerel düzeltmenin nasıl işlediğini gösterir. Şekil 10.22'nin solundaki ağaçta 11 anahtar vardır. 9 → 14 → 12 ve 76 → 54 → 72 → 67 kolları uzamıştır ve yükseklik 4'tür. Bu iki kolun alt ağaçları yeniden düzenlenince aynı 11 anahtar yüksekliği 3 olan bir ağaca sığar. Yeni alt ağaç kökleri 12 ve 72'dir.

Yeniden düzenleme sırasında kök ortada sıra değişmez: iki ağaç da 9 12 14 17 19 23 50 54 67 72 76 verir. Değişen yalnız hangi anahtarın hangisinin ebeveyni olduğudur. 17'nin sol alt ağacında 9, 14 ve 12 vardı; bunların ortancası 12 alt ağacın kökü yapıldı, 9 ve 14 onun çocukları oldu. Sağda 76'nın sol alt ağacındaki 54, 72, 67 ve 76'nın kendisi yeniden dizildi; ortadaki 72 köke çıktı. Kökün öbür tarafına, 17'nin sağ alt ağacına ya da 50'ye dokunulmadı.

AVL ve kırmızı-siyah ağaçlar bu tür düzeltmeleri kendiliğinden yapar. Bir ekleme ya da silme yalnız kendi geçtiği yolu bozabilir; düzeltme de yalnız o yol üzerinde, aşağıdan yukarı doğru yapılır.

10.4.3AVL ağacı ve denge faktörü

AVL ağacı, adını Sovyet matematikçiler Georgy Adelson-Velsky ve Evgenii Landis'in soyadlarının baş harflerinden alır. 1962'de yayımlanan AVL, kendini dengeleyen ilk ikili arama ağacıdır. Fikri sadedir: her düğümün iki alt ağacının yükseklikleri arasındaki fark en çok 1 olsun.

Pozitif denge faktörü düğümün “sol ağır” olduğunu, negatif değer “sağ ağır” olduğunu söyler. Yaprakta iki alt ağaç da boştur: bf = −1 − (−1) = 0. Yalnız sol çocuğu olan bir düğümde bf = 0 − (−1) = 1'dir. Bu yüzden boş alt ağacın yüksekliğinin −1 alınması önemlidir; 0 alınsaydı yaprakla tek çocuklu düğüm aynı görünürdü.

Sağdaki ağaçta iki düğüm dengesizdir. Böyle durumlarda en alttaki dengesiz düğüm, yani yeni eklenen düğüme en yakın olan, düzeltilir. Bu örnekte o düğüm 20'dir. 20 düzeltildiğinde alt ağacının yüksekliği bir azalır ve 30 da kendiliğinden dengeye gelir.

AVL ağacında her düğüm kendi yüksekliğini bir alanda saklar. Denge faktörü gerektiğinde iki çocuğun yüksekliğinden hesaplanır. Ekleme ve silme önce düz BST gibi yapılır. Sonra özyineleme geri dönerken yol üzerindeki her düğümün yüksekliği güncellenir ve denge faktörü denetlenir. |bf| = 2 olan bir düğüme rastlanırsa döndürmeyle düzeltilir.

10.4.4AVL yüksekliği neden O(log n)?

AVL koşulu yerel bir koşuldur; her düğüm yalnız iki çocuğunun yüksekliğine bakar. Bu yerel koşulun bütün ağacın yüksekliğini sınırladığını göstermek için soruyu tersinden soralım: yüksekliği h olan bir AVL ağacında en az kaç düğüm vardır? Bu sayıya N(h) diyelim. En az düğümlü, yani “en seyrek” AVL ağacında kökün bir alt ağacının yüksekliği h − 1 olmak zorundadır (yoksa ağacın yüksekliği h olmazdı). Öbür alt ağaç, AVL koşulunun izin verdiği en kısa yükseklikte, h − 2'de olur. İki alt ağaç da kendi yüksekliklerinde en seyrek ağaçlardır. Buradan bir yineleme bağıntısı çıkar:

N(0) = 1,   N(1) = 2,   N(h) = 1 + N(h − 1) + N(h − 2)

Sayılar Fibonacci sayıları gibi büyür; gerçekten de N(h) = F(h + 3) − 1'dir (F(1) = F(2) = 1). Fibonacci sayıları üstel büyüdüğü için N(h) de üstel büyür. Kesin bir alt sınır şöyle bulunur. N(h − 1) > N(h − 2) olduğundan N(h) = 1 + N(h − 1) + N(h − 2) > 2 · N(h − 2)'dir. Her iki düzeyde düğüm sayısı en az iki katına çıkar. Bunu h/2 kez uygulayınca N(h) > 2^h/2 bulunur.

Sonuç şunu söyler: AVL ağacı mükemmel dengeli bir ağaçtan en kötü durumda yalnız %44 kadar daha yüksektir. Bir milyon anahtarlı AVL ağacının yüksekliği 28'i geçmez. Düz BST'deki milyonluk zincirle karşılaştırılınca fark çok büyüktür.

10.4.5Döndürme

Dengesizliği düzeltmenin temel aracı döndürmedir (rotation). Döndürme, bir düğüm ile çocuklarından birinin ebeveyn–çocuk ilişkisini tersine çevirir. Çocuk bir düzey yukarı çıkar, eski ebeveyn onun altına iner. Bu sırada BST özelliğinin bozulmaması için bir alt ağacın sahibi değişir.

Sağa döndürmeyi ayrıntılı inceleyelim. Başlangıçta y ebeveyndir ve x onun sol çocuğudur. x'in iki alt ağacı T1 ve T2, y'nin sağ alt ağacı T3'tür. BST özelliğine göre kök ortada sıra şudur: T1'deki anahtarlar, x, T2'deki anahtarlar, y, T3'teki anahtarlar. Döndürmeden sonra x yukarıdadır ve y onun sağ çocuğudur. T1 x'in solunda kalır, T3 y'nin sağında kalır. T2'nin yeri değişir: x'ten büyük ve y'den küçük olduğu için y'nin sol alt ağacı olur. Kök ortada sıra yine T1 · x · T2 · y · T3'tür.

Üç bağ değişir. y'nin sol bağı artık T2'yi, x'in sağ bağı artık y'yi gösterir. Ebeveynden gelen bağ da y yerine x'i gösterir. Ağacın büyüklüğü ne olursa olsun bu üç atama yeter; döndürme sabit sürelidir. Yükseklik açısından bakıldığında T1 bir düzey yukarı çıkar, T3 bir düzey aşağı iner, T2 aynı düzeyde kalır. Sol ağır bir düğümde ağır taraf T1 ise sağa döndürme ağırlığı dengeler.

10.4.6Tek döndürmeler: LL ve RR

Bir eklemeden sonra en alttaki dengesiz düğüm z olsun. Dengesizliğin dört biçimi vardır. Adlar, yeni düğüme z'den inen yolun ilk iki adımını söyler: L sol (left), R sağ (right) demektir. LL'de yeni düğüm z'nin sol çocuğunun sol alt ağacına eklenmiştir. RR bunun simetriğidir. Bu iki durumda z ile çocuğu aynı yöne eğiktir ve tek döndürme yeter.

LL durumu denge faktörlerinden tanınır. bf(z) = 2'dir, yani z sol ağırdır. Sol çocuğun denge faktörü de 1 ya da 0'dır; çocuk sola eğik ya da dengelidir. Çözüm z'de sağa döndürmedir. RR'de bf(z) = −2 ve sağ çocuğun denge faktörü −1 ya da 0'dır; çözüm z'de sola döndürmedir.

Ekleme sonrasında tek döndürmenin güzel bir sonucu vardır: döndürülen alt ağacın yüksekliği, eklemeden önceki değerine geri döner. Şekil 10.26'da 30'un alt ağacının yüksekliği 10 eklenmeden önce 1'di (30 ve 20); ekleme 2'ye çıkardı; döndürme yeniden 1'e indirdi. Daha yukarıdaki atalar yüksekliğin değiştiğini hiç görmez. Bu yüzden eklemede tek bir düzeltme yeterlidir.

10.4.7Çift döndürmeler: LR ve RL

Kalan iki durumda yeni düğüm “zikzak” bir yolun sonundadır. LR'de yeni düğüm z'nin sol çocuğunun sağ alt ağacına eklenmiştir. z sola, çocuğu sağa eğiktir; üç düğüm bir üçgen çizer. Bu durumda z'de tek sağa döndürme işe yaramaz: üçgeni ters yöne çevirir ve ağaç yine dengesiz kalır.

Çözüm iki adımlıdır. Önce çocukta sola döndürülür; üçgen düz bir çizgiye, yani LL durumuna dönüşür. Sonra z'de sağa döndürülür. Sonuçta üç anahtarın ortancası köke çıkar, küçüğü sola, büyüğü sağa yerleşir. RL bunun simetriğidir: önce çocukta sağa, sonra z'de sola döndürülür.

10.4.8AVL kodu

AVL düğümü anahtar, yükseklik ve iki çocuk referansı taşır. Sunumdaki kod, önce üç küçük yardımcı ile sağa döndürmeyi verir:

int h(AvlDugum d) {
    return d == null ? -1 : d.yukseklik;
}
int bf(AvlDugum d) {
    return h(d.sol) - h(d.sag);
}
void guncelle(AvlDugum d) {
    d.yukseklik = 1 +
        Math.max(h(d.sol), h(d.sag));
}
AvlDugum sagaDondur(AvlDugum y) {
    AvlDugum x = y.sol;
    y.sol = x.sag;  // T2 → y.sol
    x.sag = y;      // y → x.sag
    guncelle(y);    // önce alttaki
    guncelle(x);
    return x;       // yeni kök
}

h, boş alt ağaç için −1 döndürür; böylece öteki metotlar null kontrolüyle uğraşmaz. bf, iki çocuğun yükseklik farkıdır. guncelle, bir düğümün yüksekliğini çocuklarınınkinden yeniden hesaplar. Bu hesap, çocukların yüksekliğinin doğru olmasına dayanır. Bu yüzden yükseklikler her zaman aşağıdan yukarı güncellenir.

sagaDondur(y), Şekil 10.25'teki adımları kodlar. x, yukarı çıkacak sol çocuktur. y.sol = x.sag T2'yi taşır; x.sag = y ilişkiyi tersine çevirir. Sonra iki düğümün yüksekliği güncellenir: önce y, sonra x. Döndürmeden sonra y, x'in çocuğudur; x'in yüksekliği y'nin yeni yüksekliğine bağlıdır. Sıra ters olsaydı x eski, yanlış bir değerden hesaplanırdı. Metot yeni alt ağaç kökünü, x'i döndürür. Üçüncü bağı, yani ebeveynden gelen bağı, çağıran bu dönüş değerini kendi bağına atayarak değiştirir.

Sola döndürme simetriktir; sunumda “sol ↔ sag simetriği” diye kısaltılan kod açık hâliyle şöyledir:

AvlDugum solaDondur(AvlDugum x) {
    AvlDugum y = x.sag;
    x.sag = y.sol;  // T2 → x.sag
    y.sol = x;      // x → y.sol
    guncelle(x);    // önce alttaki
    guncelle(y);
    return y;       // yeni kök
}

Dört durumu bir araya getiren metot dengele'dir:

AvlDugum dengele(AvlDugum d) {
    guncelle(d);
    if (bf(d) > 1) {       // sol ağır
        if (bf(d.sol) < 0)  // LR
            d.sol = solaDondur(d.sol);
        return sagaDondur(d); // LL
    }
    if (bf(d) < -1) {      // sağ ağır
        if (bf(d.sag) > 0)  // RL
            d.sag = sagaDondur(d.sag);
        return solaDondur(d); // RR
    }
    return d;
}
// solaDondur: sol ↔ sag simetriği
// ekle/sil BST gibi; dönüşte:
//   return dengele(kok);

dengele(d) önce d'nin yüksekliğini günceller. Denge faktörü 1'den büyükse düğüm sol ağırdır. Sol çocuk sağa eğikse (bf(d.sol) < 0) durum LR'dir; önce sol çocukta sola döndürülür ve sonuç d.sol'a yazılır. Ardından her iki durumda da d'de sağa döndürülür. Denge faktörü −1'den küçükse aynı mantık simetrik olarak işler. Denge bozuk değilse d olduğu gibi döner.

Ekleme, düz BST eklemesinin son satırını değiştirerek elde edilir:

AvlDugum ekle(AvlDugum d, int k) {
    if (d == null) return new AvlDugum(k);
    if (k < d.anahtar)
        d.sol = ekle(d.sol, k);
    else if (k > d.anahtar)
        d.sag = ekle(d.sag, k);
    else return d;          // tekrar yok
    return dengele(d);
}

Fark tek satırdadır: return d yerine return dengele(d). Özyineleme geri dönerken yeni yapraktan köke kadar yol üzerindeki her düğümde dengele çağrılır. Böylece yükseklikler aşağıdan yukarı güncellenir ve dengesiz bir düğüm bulunursa hemen düzeltilir. Silme de aynı biçimde düz BST silmesinin dönüşlerine dengele eklenerek yazılır.

Maliyet: iniş O(log n) düzeydir. Dönüşte her düzeyde dengele sabit iş yapar; döndürmeler de sabit sürelidir. Ekleme ve silme O(log n) sürer. Eklemede en çok bir düzeltme (bir tek ya da bir çift döndürme) gerekir. Silmede bir düzeltme alt ağacın yüksekliğini azaltabilir ve dengesizlik yukarıya taşınabilir; en kötü durumda yolun her düzeyinde, yani O(log n) kez döndürme yapılır.

10.4.9Kod izleme: sagaDondur ve solaDondur

İlk izleme LL durumudur. Ağaç 40(20(10, 30), 50)'dir ve 5 eklenir. 5, 40 → 20 → 10 yolundan inip 10'un soluna yerleşir. Dönüşte dengele(10) ve dengele(20) döndürme gerektirmez (bf sırasıyla 1 ve 1). dengele(40) ise bf = 2 bulur; sol çocuk 20'nin bf'si 1'dir, durum LL'dir ve sagaDondur(40) çağrılır.

Sonuç ağacı 20(10(5, —), 40(30, 50))'dir. Denge faktörleri: 20'de 0, 10'da 1, 40'ta 0, yapraklarda 0. Kök ortada sıra 5 10 20 30 40 50'dir ve döndürmeden önceki sırayla aynıdır. 40'ın yüksekliği 3'ten 1'e indi, alt ağacın kökü 20'nin yüksekliği ise 2 oldu; ekleme öncesindeki alt ağacın yüksekliği de 2'ydi.

İkinci izleme RR durumudur ve öncekinin aynadaki görüntüsüdür. Ağaç 20(10, 40(30, 50))'dir ve 60 eklenir. dengele(20) bf = −2 bulur, sağ çocuk 40'ın bf'si −1'dir ve solaDondur(20) çağrılır. y = x.sag 40'ı tutar. x.sag = y.sol 20'nin sağ bağını 30'a yöneltir. y.sol = x 20'yi 40'ın sol çocuğu yapar. guncelle(x) 20'nin yüksekliğini 1 + max(0, 0) = 1 bulur (önceden 3), guncelle(y) 40'ınkini 1 + max(1, 1) = 2 bulur. Sonuç 40(20(10, 30), 50(—, 60))'tır.

10.4.10Kod izleme: dengele

Çift döndürmenin kodda nasıl işlediğini LR örneğinde izleyelim. Ağaç 50(20(10, 30), 60)'tır ve 25 eklenir. 25, 50 → 20 → 30 yolundan inip 30'un soluna yerleşir. Özyineleme geri dönerken dengele yol üzerindeki her düğümde çağrılır.

Sonuç 30(20(10, 25), 50(—, 60))'tır. Yükseklik 3'ten 2'ye indi; ekleme öncesindeki değer de 2'ydi. Denge faktörleri 30'da 0, 20'de 0, 50'de −1, yapraklarda 0'dır. İlk döndürmenin sonucunun d.sol'a atanması şarttır: solaDondur(20) yeni alt ağaç kökü olarak 30'u döndürür ve 50'nin sol bağı ancak bu atamayla 30'u gösterir.

10.4.11AVL'ye ekleme örneği

Boş bir AVL ağacına sırasıyla 10, 20, 30, 40, 50, 25 eklensin. Düz BST bu girdiyle (son anahtar dışında) sağa uzanan bir zincir kurardı. Tablo 10.17 her eklemeden sonraki ağacı ve yapılan döndürmeleri verir.

50 eklendiğinde 30 ve 20 aynı anda dengesiz görünebilir mi? Hayır. Dönüşte önce dengele(40), sonra dengele(30) çağrılır. 30 dengesizdir ve düzeltilir; alt ağacın yüksekliği eski değeri olan 1'e iner. dengele(20) çağrıldığında yükseklik 2 → 2 kalır, bf(20) = −1'dir. En alttaki dengesiz ata düzeltildiği için yukarısı etkilenmez.

Son eklemede 25, 30'un soluna düşer. Dönüşte bf(30) = 1 ve bf(40) = 1 sorun değildir. bf(20) = h(10) − h(40) = 0 − 2 = −2'dir ve sağ çocuk 40 sola eğiktir: RL. Önce 40'ta sağa döndürülür (30 yukarı çıkar), sonra 20'de sola döndürülür. 30 köke çıkar; 25, 20'nin sağına geçer. Altı ekleme sonunda ağacın yüksekliği 2'dir; düz BST'de aynı sıra 4 yüksekliğinde bir ağaç verirdi.

10.5Kırmızı-siyah ağaçlar

AVL ağacı dengeyi sıkı tutar: her düğümde iki alt ağacın yükseklik farkı en çok 1'dir. Bu sıkılığın bedeli, silmede dengesizliğin köke kadar yayılabilmesi ve her düzeyde döndürme gerekebilmesidir. Kırmızı-siyah ağaç daha gevşek bir denge kabul eder. Karşılığında güncellemelerde çok az döndürme yapar ve çoğu düzeltmeyi yalnız renk değiştirerek halleder. Yapı, Guibas ve Sedgewick'in 1978'deki çalışmasında bugünkü renk diliyle tanımlanmıştır. Java'nın TreeMap ve TreeSet sınıfları ile C++'ın std::map'i bu yapıyı kullanır.

10.5.1Kurallar

Üçüncü kural ilk bakışta tuhaf gelir: boş bir çocuğun rengi ne demektir? Kural, kodda null çocukların siyah sayılacağını söyler. Böylece kural 4 ve 5, çocuğu eksik düğümlerde de anlamlı kalır. Notta siyah düğüm sayılırken kök sayılır, NIL yapraklar sayılmaz.

Kuralları Şekil 10.32 üzerinde denetleyelim. Kırmızı 8'in çocukları 1 ve 11 siyahtır; kırmızı 17'nin çocukları 15 ve 25 siyahtır. Kırmızı yaprakların (6, 22, 27) çocukları NIL'dir ve siyah sayılır. Kural 4 sağlanır. Kural 5 için birkaç yol sayalım: 13 → 8 → 1 → NIL yolunda siyahlar 13 ve 1'dir; 13 → 8 → 1 → 6 → NIL yolunda da 13 ve 1'dir, 6 kırmızıdır. 13 → 17 → 25 → 27 → NIL yolunda siyahlar 13 ve 25'tir. Her yolda iki siyah vardır.

10.5.2Kurallar dengeyi nasıl garanti eder?

Kurallar ağacın yüksekliğini doğrudan sınırlamaz. Sınır iki kuralın birlikte çalışmasından çıkar. Kökün siyah yüksekliği b olsun. Kökten bir NIL'e giden en kısa yol ne kadar kısa olabilir? Her yolda tam b siyah düğüm vardır; en kısa yol yalnız siyah düğümlerden oluşur ve b düğümlüdür. En uzun yol ne kadar uzun olabilir? Yine b siyah düğüm içerir, ama araya kırmızılar girebilir. Kural 4 iki kırmızının art arda gelmesini yasaklar; en fazla her siyahın altına bir kırmızı girer. En uzun yol en çok 2b düğümlüdür.

Sonuç olarak kırmızı-siyah ağaçta arama, ekleme ve silme O(log n) sürer. Ekleme sonrası düzeltmede en çok 2, silme sonrası düzeltmede en çok 3 döndürme yapılır; geri kalan iş renk değiştirmektir. Yükseklik sınırı AVL'ninkinden (yaklaşık 1,44 log₂ n) gevşektir; yani kırmızı-siyah ağaç biraz daha uzun olabilir. Buna karşılık güncellemeleri daha ucuzdur ve düğüm başına ek bilgi yalnız bir bitlik renktir.

10.5.3Ekleme ve düzeltme durumları

Ekleme iki aşamalıdır. Birinci aşamada yeni düğüm düz BST eklemesiyle yaprak olarak bağlanır ve kırmızıya boyanır. Neden kırmızı? Siyah eklenseydi, yeni düğümün bulunduğu yollarda siyah sayısı bir artar ve kural 5 bozulurdu. Kırmızı düğüm siyah yüksekliği değiştirmez. Bozulabilecek tek kural 4'tür: yeni düğümün ebeveyni de kırmızıysa art arda iki kırmızı oluşur. İkinci aşama bu bozukluğu gidermektir.

Düzeltmede dört düğüm rol alır (Şekil 10.34): yeni düğüm x, ebeveyni p, dedesi g ve amcası u, yani ebeveynin kardeşi. Ebeveyn kırmızıysa kök olamaz (kök siyahtır); demek ki bir dede vardır ve dede siyahtır (yoksa ağaçta önceden art arda iki kırmızı olurdu). Neyin yapılacağına amcanın rengi karar verir.

Ebeveyn siyahsa hiçbir şey yapılmaz; art arda kırmızı yoktur. En sonda kök her zaman siyaha boyanır. NIL amca siyah sayılır.

Renk değiştirmenin neden kural 5'i koruduğunu görelim. Önce g siyah, p ve u kırmızıdır. Sonra g kırmızı, p ve u siyahtır. g'den aşağı inen her yol, p ya da u'dan tam birinden geçer. Önce bu yolda bir siyah vardı (g), şimdi yine bir siyah var (p ya da u). Siyah sayıları değişmez. Ama g kırmızı olduğu için onun ebeveyni de kırmızıysa kural 4 bu kez yukarıda bozulur. Bu yüzden döngü g'den devam eder. Sorun her adımda iki düzey yukarı çıkar; en kötü durumda köke ulaşır ve kökün siyaha boyanmasıyla biter.

Amca siyahken renk değiştirmek işe yaramaz. Amca zaten siyahtır; g'yi kırmızı yapmak ise amcanın tarafındaki yollarda bir siyah eksiltir. Bunun yerine döndürme yapılır. Çizgi durumunda (x ile p aynı yönde çocuk) g'de döndürülür; p yukarı çıkar ve siyah olur, g aşağı iner ve kırmızı olur. Üçgen durumunda önce p'de döndürülerek çizgi elde edilir. Bu iki adım, AVL'deki tek ve çift döndürmelerin aynısıdır. Döndürmeden sonra alt ağacın kökü siyahtır ve döngü biter.

10.5.4Düzeltme kodu

Kırmızı-siyah ağaç düğümünde anahtar ve iki çocuğun yanında bir renk alanı ve ebeveyne bir referans vardır. Ebeveyn referansı, düzeltmenin aşağıdan yukarı yürüyebilmesi içindir. Sunumdaki düzeltme kodu şöyledir:

void duzelt(Dugum x) {      // x: yeni, kırmızı
    while (x != kok && kirmizi(x.ebeveyn)) {
        Dugum p = x.ebeveyn, g = p.ebeveyn;
        Dugum u = (p == g.sol) ? g.sag : g.sol;
        if (kirmizi(u)) {         // amca kırmızı
            p.renk = u.renk = SIYAH;
            g.renk = KIRMIZI;
            x = g;                // sorun dedeye
        } else {                  // amca siyah
            if (ucgen(x, p, g)) { // zikzak
                dondur(p, x);     // çizgiye çevir
                Dugum t = x; x = p; p = t;
            }
            dondur(g, p);         // çizgi
            p.renk = SIYAH; g.renk = KIRMIZI;
        }
    }
    kok.renk = SIYAH;
}

Yardımcılar ve eklemenin bütünü yorum satırlarıyla verilmiştir:

// Ekleme: BST gibi yaprağa ekle,
// ebeveyni bağla, kırmızı boya:
//   x = bstEkle(anahtar);
//   x.renk = KIRMIZI; duzelt(x);

// NIL (null) siyah sayılır
boolean kirmizi(Dugum n) {
    return n != null
        && n.renk == KIRMIZI;
}
// x–p–g zikzak (üçgen) mı?
boolean ucgen(Dugum x, Dugum p,
              Dugum g) {
    return (p == g.sol)
        != (x == p.sol);
}
// dondur(a, b): b, a'nın çocuğu;
// b'yi a'nın yerine çıkarır (b
// soldaysa sağa, sağdaysa sola
// döndürme; ebeveyn bağları dahil)

kirmizi(n), null'ı siyah sayar; böylece NIL amca ayrıca ele alınmaz. ucgen(x, p, g), “p dedenin sol çocuğu mu?” ile “x ebeveynin sol çocuğu mu?” sorularının cevaplarını karşılaştırır. Cevaplar farklıysa x–p–g zikzaktır. dondur(a, b), a'nın çocuğu olan b'yi a'nın yerine çıkarır; b soldaysa sağa, sağdaysa sola döndürür ve ebeveyn bağlarını da günceller. İzlemelerde duzelt'in satır numaraları kullanılır. Satır 2 döngü koşulu, satır 5 amca kontrolü, satır 10 üçgen kontrolüdür. Satır 14 dedede döndürür, satır 18 kökü siyaha boyar.

Döngüdeki Dugum t = x; x = p; p = t; satırı üçgen durumundan sonra rolleri değiştirir. p'de döndürmeden sonra x yukarı, p aşağı geçmiştir. Çizgi durumundaki dondur(g, p) çağrısının doğru düğümü döndürmesi için p değişkeninin artık yukarıdaki düğümü göstermesi gerekir.

Maliyet: BST eklemesi O(log n)'dir. Düzeltme döngüsü her turda en az iki düzey yukarı çıkar; en çok O(log n) tur döner. Döndürme yalnız döngünün son turunda yapılır (amca siyah dalı döngüyü bitirir) ve en çok iki tanedir.

10.5.5Kod izleme: 10, 20, 30, 15

Boş bir kırmızı-siyah ağaca sırasıyla 10, 20, 30 ve 15 eklensin. Metinde renk, düğümün yanına yazılan K (kırmızı) ve S (siyah) harfleriyle gösterilir: K, S.

30 eklenirken amca NIL'dir ve siyah sayılır. 30, 20'nin sağ çocuğu; 20 de 10'un sağ çocuğudur. Üçü düz bir çizgi oluşturur; ucgen yanlış döner ve doğrudan satır 14'e geçilir. Dedede sola döndürme, AVL'deki RR düzeltmesinin aynısıdır. Renkler değiştirilince alt ağacın kökü (20) siyah olur ve döngü biter.

15 eklendiğinde amca 30 kırmızıdır; döndürme gerekmez, renk değiştirmek yeter. Dede 20 kırmızı olur ve döngü 20'den devam eder. 20 kök olduğu için döngü koşulu yanlıştır. Satır 18 kökü yeniden siyaha boyar. Bu ekleme, ağacın siyah yüksekliğini 1'den 2'ye çıkardı: artık kökten her NIL'e giden yolda iki siyah düğüm vardır.

10.5.6Kod izleme: 12 ve 5

Aynı ağaca, 20S(10S(—, 15K), 30S), önce 12, sonra 5 eklensin. 12 üçgen durumunu, 5 ise renk değiştirmenin bir düzey yukarı taşınmasını gösterir.

12 eklenirken 15, 10'un sağ çocuğudur; 12 ise 15'in sol çocuğudur. Yol zikzak çizer. Önce 15'te sağa döndürülür: 12 yukarı, 15 aşağı geçer ve 10 → 12 → 15 düz çizgisi oluşur; ama art arda iki kırmızı hâlâ vardır. Roller değiştirildikten sonra 10'da sola döndürülür. 12 alt ağacın köküne çıkar ve siyah olur, 10 kırmızı olur. Bu, AVL'deki RL düzeltmesinin aynısıdır.

5 eklenirken amca 15 kırmızıdır. Renk değiştirme 12'yi kırmızı yapar ve döngü 12'den devam eder. 12'nin ebeveyni 20 siyah olduğu için döngü biter; kök zaten siyahtır. Son ağaçta her yolda 2 siyah düğüm vardır. 20 → 12 → 10 → 5 → NIL yolundaki siyahlar 20 ve 10'dur. 20 → 30 → NIL yolunda da 20 ve 30 siyahtır.

10.5.7Dengeli ağaçlarda silme

AVL ve kırmızı-siyah ağaçlarda silme aynı biçimde başlar: önce düz BST silmesi uygulanır. İki çocuklu düğüm ardılı ya da öncülüyle değiştirilir; gerçekte ağaçtan kopan düğüm her zaman bir yaprak ya da tek çocuklu bir düğümdür. Düğümün kopması dengeyi bozabilir: AVL'de yükseklik farkı, kırmızı-siyah ağaçta siyah yükseklik kuralı ihlal edilebilir.

• AVL düzeltmesi: Kopan düğümden köke doğru yükseklikler güncellenir. |bf| = 2 olan her düğümde LL, RR, LR ya da RL döndürmesi uygulanır. Eklemenin tersine, bir döndürme alt ağacın yüksekliğini eski değerinin altına indirebilir; bu da üstteki bir atayı dengesizleştirebilir. Bu yüzden birden fazla atada düzeltme gerekebilir.
• Kırmızı-siyah düzeltmesi: Kırmızı bir düğümün silinmesi kolaydır; siyah sayıları değişmez. Siyah bir düğüm kopunca onun yolları bir siyah eksik kalır. Bu eksiklik, kardeşin rengine ve kardeşin çocuklarının renklerine göre yeniden renklendirme ve döndürmeyle giderilir. Bu düzeltmeye kitaplarda “çift siyah” düzeltmesi denir; eksik siyahlık köke kadar taşınabilir, ama döndürme sayısı en çok üçtür.

Ekleme ve silme BST sırasını korur. Dengeleme yalnız ağacın biçimini ve düğümlerdeki yardımcı bilgileri (yükseklik ya da renk) değiştirir; kök ortada gezinme her an aynı sıralı listeyi verir.

10.5.8AVL mi, kırmızı-siyah mı?

İki yapı da bütün işlemleri O(log n)'de yapar. Seçim, işlemlerin karışımına bağlıdır. Tablo 10.22 farkları özetler.

Uygulamada fark çoğu zaman küçüktür. Bir sözlük bir kez kurulup milyonlarca kez sorgulanacaksa AVL'nin daha kısa ağacı her aramada birkaç karşılaştırma kazandırır. Ekleme ve silmenin sık olduğu genel amaçlı bir kütüphane sınıfında kırmızı-siyah ağacın ucuz güncellemesi ağır basar. Java ve C++ standart kütüphanelerinin kırmızı-siyah ağacı seçmesinin nedeni budur.

10.6Splay ağaçları

AVL ve kırmızı-siyah ağaçlar her düğümde ek bilgi tutar ve her işlemden sonra dengeyi bu bilgiye bakarak düzeltir. Splay ağacı başka bir yol izler: hiçbir denge bilgisi tutmaz ve ağacın dengeli olmasına da çalışmaz. Bunun yerine her erişimde erişilen düğümü köke taşır. Yöntemi 1985'te Sleator ve Tarjan önerdi; yapıya kendini düzenleyen (self-adjusting) BST de denir.

10.6.1Kendini düzenleyen ağaç

Splay ağacının yüksekliği için hiçbir garanti yoktur; ağaç bir zincire bile dönüşebilir. Böyle bir ağaçta en alttaki düğüme erişmek O(n) sürer. Ama bu pahalı erişim ağacı da düzeltir: erişilen düğüm köke çıkarken yolu üzerindeki düğümlerin derinliği kabaca yarıya iner. Sleator ve Tarjan, boş ağaçtan başlayan m işlemlik her dizinin toplam O(m log n) sürdüğünü gösterdi. İşlem başına amortize maliyet O(log n)'dir. Amortize analiz, tek tek işlemlere değil, işlem dizisinin toplamına söz verir: bazı işlemler pahalı olabilir, ama ucuz işlemler onların maliyetini dengeler.

Yapının üç belirgin özelliği vardır:

• Yerellik: Sık erişilen anahtarlar köke yakın durur. Ağaç bir önbellek gibi davranır. Erişimlerin küçük bir anahtar kümesinde yoğunlaştığı uygulamalarda splay ağacı dengeli ağaçlardan hızlı olabilir.
• Basitlik: Ek alan gerekmez. Tek bir splay yordamı bütün işlemlere yeter: arama bulduğu düğümü, ekleme yeni düğümü, silme ise silinecek düğümü önce köke taşır.
• Dezavantaj: Arama bile ağacı değiştirir. Bu, birden çok iş parçacığının aynı ağacı okuduğu durumlarda sorun çıkarır. Tek bir işlemin süresi için garanti yoktur; gerçek zamanlı sistemlerde bu kabul edilemeyebilir.

10.6.2Zig, zig-zig ve zig-zag

Splay, erişilen düğüm x kök olana kadar üç tür adımı tekrarlar. Adımın türünü x'in ebeveyni p ve dedesi g belirler.

• Zig: x'in ebeveyni köktür (dede yoktur). p'de tek bir döndürme yapılır ve x kök olur. Bu adım yalnız splay'in son adımında görülebilir.
• Zig-zig: x ve p aynı yönde çocuktur (ikisi de sol ya da ikisi de sağ). Önce dedede, sonra ebeveynde döndürülür.
• Zig-zag: x ve p zıt yönde çocuktur. Önce ebeveynde, sonra dedede döndürülür. Bu, AVL'deki çift döndürmenin aynısıdır.

Zig-zig'deki sıra önemlidir ve AVL'den farklıdır. Önce dedede döndürmek, yoldaki düğümleri “katlar”: zincirin üst kısmı da kısalır. Önce ebeveynde döndürmek (yani x'i tek döndürmelerle yukarı itmek) x'i yine köke çıkarır, ama zincirin geri kalanı uzun kalabilir. Sleator ve Tarjan'ın amortize sınırı tam olarak bu dededen başlayan sıraya dayanır.

Sunumdaki splay kodu bu üç adımı bir döngüde toplar:

void splay(Dugum x) {
    while (x != kok) {
        Dugum p = x.ebeveyn, g = p.ebeveyn;
        if (g == null)                // zig
            dondur(p, x);
        else if (ayniYon(x, p, g)) {  // zig-zig
            dondur(g, p);   // önce dede
            dondur(p, x);
        } else {                      // zig-zag
            dondur(p, x);   // önce ebeveyn
            dondur(g, x);
        }
    }
}

dondur(a, b), kırmızı-siyah koddaki tek döndürmenin aynısıdır: a'nın çocuğu olan b'yi a'nın yerine çıkarır. ayniYon(x, p, g), x'in p'nin hangi tarafında olduğunu, p'nin g'nin hangi tarafında olduğuyla karşılaştırır. Zig-zag dalındaki ikinci çağrı dondur(g, x) biçimindedir: ilk döndürmeden sonra x, p'nin yerine geçmiştir ve artık g'nin çocuğudur.

10.6.3Kod izleme: splay(50) ve splay(10)

Başlangıç ağacı 80(40(20(10, 30), 60(50, 70)), 90)'dır. Önce 50'ye, sonra 10'a erişilsin.

splay(50)'den sonra ağaç 50(40(20(10, 30), —), 80(60(—, 70), 90))'dır. 50 derinlik 3'ten köke çıktı. Eski kök 80 bir düzey indi ve 90 da onunla birlikte 1'den 2'ye geçti. 40, 20, 60 ve 70'in derinlikleri değişmedi.

splay(10)'dan sonra ağaç 10(—, 50(20(—, 40(30, —)), 80(60(—, 70), 90)))'dır. 10 köke çıktı ve az önce erişilen 50 hâlâ köke yakındır: derinliği 1'dir. Zig-zig adımında önce 40'ta döndürüldüğü için 40, 20'nin altına inmiş ve 30'u sol çocuğu olarak almıştır.

Tek bir splay işleminin maliyeti, erişilen düğümün derinliğiyle orantılıdır; derin bir düğüm için O(n) olabilir. Ama ağaç bu işlemlerle sürekli yeniden şekillenir ve uzun bir işlem dizisinin ortalaması O(log n)'de kalır.

10.7Çok yollu arama ağaçları

Buraya kadar bütün ağaçlar ikiliydi: her düğümde bir anahtar ve en çok iki çocuk. Veri ana bellekte durduğunda bu yeterlidir; bir düğümden ötekine geçmek birkaç nanosaniye sürer. Veri diskte durduğunda durum değişir. Diskten bir blok okumak, bellekten bir değer okumaktan binlerce, eski dönen disklerde yüz binlerce kat yavaştır. Bir milyar kayıtlı bir veritabanı indisinde ikili ağacın yüksekliği en iyi durumda 30'dur. Her düğüm ayrı bir disk okuması isterse tek bir arama 30 disk erişimi tutar. Çok yollu ağaçlar bu sayıyı birkaç erişime indirir.

10.7.1B-ağacı

Düğüm içindeki anahtarlar, çocukların arasındaki sınırlar gibi çalışır. Şekil 10.39'daki kök [20, 40] üç çocuğa yön verir: 20'den küçükler sol çocukta, 20 ile 40 arasındakiler ortada, 40'tan büyükler sağdadır. Bu, BST özelliğinin çok yollu genellemesidir. İkili arama ağacı, derecesi 2 olan bir B-ağacı gibi düşünülebilir; ama B-ağacının asıl gücü, bütün yaprakların aynı derinlikte olması kuralından gelir. Bu kural ağacı her zaman mükemmel biçimde dengeli tutar.

Neden böyle bir yapı? Bir düğüm bir disk bloğuna denk getirilir. Bir blokta yüzlerce anahtar tutulabilir; derecesi örneğin 200 olan bir B-ağacında her düğüm 200'e kadar çocuğa yön verir. Yüksekliği 3 olan böyle bir ağaç 200⁴, yani bir milyardan fazla anahtar tutabilir. Bir arama dört blok okur; kök genellikle bellekte tutulduğu için diske gidilen sayı daha da azdır. Geniş ve alçak ağaç az disk erişimi demektir. Bu yüzden veritabanı ve dosya sistemi indislerinin temeli B-ağacıdır. Yapıyı 1972'de Bayer ve McCreight tanıttı.

Derecesi 4 olan B-ağacına 2-3-4 ağacı da denir; düğümleri 2, 3 ya da 4 çocukludur. 2-3-4 ağacı kırmızı-siyah ağacın eşdeğeridir. Kırmızı-siyah ağaçta her siyah düğüm kırmızı çocuklarıyla tek bir düğümde toplanırsa bir 2-3-4 ağacı elde edilir. Kırmızı-siyah ağacın “eşit siyah yükseklik” kuralı, 2-3-4 ağacının “bütün yapraklar aynı derinlikte” kuralının ta kendisidir.

10.7.2B-ağacında arama ve ekleme

Arama BST aramasının genellemesidir. Kökte, düğümün anahtarları sırayla aranan anahtarla karşılaştırılır. Anahtar bulunursa arama biter. Bulunamazsa, aranan anahtarın düştüğü aralığa karşılık gelen çocuğa inilir. Her düzeyde yalnız bir düğüm, yani bir disk bloğu okunur. Maliyet yükseklikle orantılıdır: O(log_m n) düğüm okuması. Düğüm içindeki arama da ikili aramayla O(log m) karşılaştırmada yapılabilir; toplam karşılaştırma sayısı O(log n)'dir.

Ekleme her zaman bir yaprakta başlar. Anahtar için aynı arama yolu izlenir ve anahtar yaprakta sıralı yerine konur. Yaprakta yer varsa iş biter. Yaprak taşarsa, yani m anahtara ulaşırsa, bölünür: ortanca anahtar ebeveyne çıkar, kalan anahtarlar iki ayrı düğüme ayrılır. Ebeveyne bir anahtar ve bir çocuk eklendiği için ebeveyn de taşabilir; o zaman o da bölünür. Bölünme köke kadar yayılabilir. Kök bölünürse yeni bir kök oluşur ve ağacın yüksekliği bir artar.

Dört anahtarlı [25, 30, 33, 35] yaprağının tam bir ortancası yoktur; iki ortadaki anahtardan biri seçilmelidir. Sunumdaki örnek sağdakini (33) seçer ve sol yarıda iki, sağ yarıda bir anahtar kalır. Soldakini seçmek de geçerlidir; önemli olan seçimin tutarlı olmasıdır. Derecesi tek olan ağaçlarda bu belirsizlik doğmaz: m = 3'te taşan düğümde üç anahtar vardır ve ortanca tektir.

Bölünmenin güzel bir sonucu vardır: B-ağacı aşağıdan yukarı büyür. İkili arama ağacında yeni düğümler aşağıya eklenir ve ağaç aşağı doğru uzar. B-ağacında ise yükseklik ancak kök bölünürken, yani en üstte artar. Bütün yapraklar aynı anda bir düzey aşağı itilmiş olur; bu yüzden hepsi her zaman aynı derinlikte kalır.

Silme eklemenin tersidir. Bir düğüm en az doluluk sınırının altına düşerse kardeşinden anahtar ödünç alır ya da kardeşiyle birleşir. Birleşme ebeveynden bir anahtar eksiltir ve eksiklik yukarı taşınabilir. Kökün son anahtarı inerse kök kaldırılır ve yükseklik bir azalır. Böylece hem denge hem doluluk sınırları korunur.

10.7.3Ekleme ve bölünme adım adım

Derecesi m = 3 olan boş bir B-ağacına sırasıyla 10, 20, 30, 40, 50, 60, 70 eklensin. Bu ağaçta bir düğüm en çok 2 anahtar ve 3 çocuk tutar; 3 anahtara ulaşan düğüm bölünür.

Sonuçta 7 anahtar 3 seviyeye yerleşti. Her iç düğümün 2 çocuğu vardır ve bütün yapraklar aynı derinliktedir. Kök iki kez bölündü ve yükseklik yalnız bu iki anda arttı. Sıralı girdi düz BST'yi zincire çevirirdi; B-ağacı ise aynı girdiden mükemmel dengeli bir ağaç kurdu.

10.7.4B+ ağacı

B+ ağacı, B-ağacının veritabanlarında en çok kullanılan çeşididir. İki yapı arasında üç fark vardır:

• Veri yapraklarda: Bütün anahtarlar ve kayıtlar yapraklarda bulunur. İç düğümler yalnız yönlendirme anahtarları tutar; bu anahtarların kopyası yapraklarda da vardır.
• Bağlı yapraklar: Yapraklar soldan sağa bir bağlı liste gibi birbirine bağlıdır. “20 ile 50 arası” gibi aralık sorguları bu zincir üzerinde hızla yürür.
• Daha geniş iç düğümler: İç düğümler kayıt taşımadığı için bir bloğa daha çok anahtar sığar. Derece büyür, ağaç alçalır.

Arama her zaman bir yaprakta biter, çünkü kayıt yalnız orada vardır. B-ağacında aranan anahtar bir iç düğümde bulunursa arama erken biterdi; B+ ağacında bu kısa yol yoktur. Buna karşılık her arama aynı sayıda düzey iner ve maliyet tahmin edilebilir. Çoğu ilişkisel veritabanı yönetim sisteminde tablo indisleri B+ ağacıdır.

10.7.5B+ ağacında aralık sorgusu

Şekil 10.42'deki ağaçta 10 ile 45 arasındaki anahtarlar istensin.

1. Kökten başlanır: 10 < 20 olduğu için alt sınır 10'u içeren yaprak en soldaki çocuktadır. Bu iniş bir aramadır ve O(log n) düzey sürer.
2. İlk yaprak [5, 10]: 5 < 10 olduğu için atlanır, 10 alınır. Yaprağın sonuna gelindi; yukarı çıkılmadan sonraki yaprak bağına geçilir.
3. İkinci yaprak [20, 25, 30]: üçü de aralıkta, alınır. Yine bağ izlenir.
4. Üçüncü yaprak [40, 50, 60]: 40 alınır; 50 > 45 olduğu için durulur.

Sonuç 10 20 25 30 40'tır ve sıralıdır. Maliyet, bir kez aşağı inmek (O(log n)) ile okunan yaprakların toplamıdır: O(log n + k), burada k sonuç sayısıdır. B-ağacında aynı sorgu, anahtarlar iç düğümlere de dağıldığı için ağaçta tekrar tekrar inip çıkmayı gerektirirdi. B+ ağacındaki yaprak zinciri bu gidiş gelişi ortadan kaldırır.

10.8Sık yapılan hatalar

Arama ağacı kodundaki hataların çoğu birkaç tipe ayrılır. Not boyunca konuların yanında verilen hatalar burada bir arada toplanmıştır; bir ağaç kodunu gözden geçirirken kontrol listesi olarak kullanılabilir.

Bu hataların arkasında iki ortak düşünce yanlışı vardır. Birincisi, ağacı yalnız “yerel” görmektir: bir düğümü yalnız ebeveyni ve çocuklarıyla düşünmek. Oysa BST özelliği, AVL koşulu ve siyah yükseklik kuralı bütün alt ağaçla ilgili koşullardır. İkincisi, Java'nın referans ve değer ayrımını unutmaktır. Ağaç metotları alt ağacın yeni kökünü döndürür ve çağıran bu değeri bir bağa ya da değişkene yazmadıkça hiçbir şey değişmez.

10.9Özet

• Arama ağacı, öğeleri anahtarlarına göre sıralı tutar; arama, ekleme ve silme kökten tek bir yol izler ve O(h) sürer. n düğümlü ağaçta h, en iyi durumda yaklaşık log₂ n, en kötü durumda n − 1'dir.
• BST özelliği: her düğümde sol alt ağacın bütün anahtarları küçük, sağ alt ağacın bütün anahtarları büyüktür. Özellik bütün alt ağaç için geçerlidir. Kök ortada gezinme anahtarları sıralı verir ve O(n) sürer. En küçük anahtar en soldaki, en büyük en sağdaki düğümdedir.
• Ekleme aranıyormuş gibi iner ve düştüğü boş bağa yeni bir yaprak bağlar. Metotlar alt ağacın yeni kökünü döndürür; kullanım kok = ekle(kok, x) biçimindedir.
• Ardıl x'ten büyük en küçük, öncül x'ten küçük en büyük anahtardır. Tavan ve taban eşitliği de kabul eder. Hepsi O(h)'dir.
• Silme üç durumludur: yaprak kaldırılır; tek çocuklu düğüm atlanır; iki çocuklu düğümün değeri ardılıyla (ya da öncülüyle) değiştirilir ve ardıl kendi yerinden silinir. Ardılın sol çocuğu olmadığı için bu ikinci silme her zaman kolay durumlardan birine düşer.
• Aralık sorgusu budamayla O(h + s) sürer. BST doğrulama, izinli aralığı kökten aşağı taşıyarak O(n)'de yapılır.
• Düz BST'nin şekli ekleme sırasına bağlıdır; sıralı girdi zincir verir. Rastgele sırada ortalama derinlik yaklaşık 1,39 log₂ n'dir. Dengeli ağaçlar küçük yerel değişikliklerle h = O(log n) garantisi verir.
• AVL ağacında her düğümde bf = h(sol) − h(sağ) ∈ {−1, 0, 1}'dir. En seyrek AVL ağacının düğüm sayısı Fibonacci gibi büyür ve h < 1,44 log₂(n + 2)'dir. Dengesizlik LL ve RR'de tek, LR ve RL'de çift döndürmeyle düzeltilir. Döndürme O(1)'dir ve kök ortada sırayı korur.
• Kırmızı-siyah ağaçta kök siyahtır, art arda iki kırmızı yoktur ve her yolda siyah sayısı eşittir. En uzun yol en kısanın en çok iki katıdır ve h ≤ 2 log₂(n + 1)'dir. Ekleme sonrası düzeltme amcanın rengine bakar: amca kırmızıysa renk değiştirilir, siyahsa en çok iki döndürme yapılır.
• Splay ağacı erişilen düğümü zig, zig-zig ve zig-zag adımlarıyla köke taşır. Denge bilgisi tutmaz; tek işlem O(n) olabilir, amortize maliyet O(log n)'dir.
• B-ağacında bir düğüm en çok m − 1 anahtar ve m çocuk tutar, bütün yapraklar aynı derinliktedir. Taşan düğüm bölünür ve ortanca anahtar yukarı çıkar; ağaç aşağıdan yukarı büyür. B+ ağacında veri yalnız yapraklardadır ve yapraklar bağlıdır; aralık sorgusu O(log n + k) sürer.

10.10Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• arama ağacı search tree
• ikili arama ağacı binary search tree (BST)
• anahtar key
• kök root
• yaprak leaf
• alt ağaç subtree
• derinlik depth
• yükseklik height
• kök ortada inorder
• gezinme traversal
• ardıl successor
• öncül predecessor
• ata ancestor
• kardeş sibling
• mükemmel ikili ağaç perfect binary tree
• denge faktörü balance factor
• AVL ağacı AVL tree
• döndürme rotation
• kırmızı-siyah ağaç red-black tree
• splay ağacı splay tree
• zig, zig-zig, zig-zag zig, zig-zig, zig-zag
• amortize analiz amortized analysis
• B-ağacı B-tree
• B+ ağacı B+ tree
• derece degree

10.11Kendini Dene

1. Boş bir BST'ye sırasıyla 35, 18, 52, 10, 25, 44, 60, 22, 48 ekleniyor. Ağacın yüksekliği nedir? Kök ortada gezinme ne verir? ara(kok, 48) kaç düğümle karşılaştırma yapar?

   Cevap

   Ağaç 35(18(10, 25(22, —)), 52(44(—, 48), 60))'tır. En derin düğümler 22 ve 48'dir (derinlik 3); yükseklik 3'tür. Kök ortada gezinme 10 18 22 25 35 44 48 52 60 verir. 48 aranırken 35 (sağa), 52 (sola), 44 (sağa) ve 48 ile karşılaştırılır: 4 düğüm, yani 48'in derinliği artı bir.

2. Aynı ağaçtan önce 18, sonra 35 siliniyor (iki çocuklu düğümde kök ortada ardıl kullanılıyor). Her silmeden sonra ağaç nasıl olur?

   Cevap

   18'in iki çocuğu vardır. Ardıl, sağ alt ağacın en küçüğüdür: 25'e geçilir, sonra sola 22'ye inilir. 22, 18'in düğümüne kopyalanır ve eski 22 (yaprak) silinir: 35(22(10, 25), 52(44(—, 48), 60)). 35'in de iki çocuğu vardır; ardıl 52'den sola 44'tür. 44 köke kopyalanır, eski 44 tek çocuklu olduğu için atlanır ve 52'nin sol bağı 48'e yönelir: 44(22(10, 25), 52(48, 60)).

3. 1. sorudaki ağaçta ardil(25), oncul(44), tavan(45) ve taban(21) nedir?

   Cevap

   ardil(25) = 35: 25'in sağ alt ağacı yoktur; solundan geçilen en yakın ata köktür. oncul(44) = 35: 44'ün sol alt ağacı yoktur; sağından geçilen en yakın ata köktür. tavan(45) = 48 (45 ağaçta yok, ≥ 45 olan en küçük anahtar). taban(21) = 18 (21 ağaçta yok, ≤ 21 olan en büyük anahtar).

4. 1. sorudaki ağaçta aralik(kok, 20, 46) ne yazdırır? Hangi düğümler hiç ziyaret edilmez?

   Cevap

   Çıktı 22 25 35 44'tür. Ziyaret sırası 35, 18, 25, 22, 52, 44, 48'dir. 18'de 20 < 18 yanlış olduğu için 10 budanır. 52'de 52 < 46 yanlış olduğu için 60 budanır. 48 ziyaret edilir (44'ün sağı, çünkü 44 < 46), ama aralık dışındadır. Hiç ziyaret edilmeyenler 10 ve 60'tır.

5. Boş bir AVL ağacına sırasıyla 30, 20, 10, 40, 50, 35 ekleniyor. Hangi eklemelerde hangi durum oluşur ve son ağaç nedir?

   Cevap

   10: bf(30) = 2, bf(20) = 1 → LL; 30'da sağa → 20(10, 30). 40: dengesizlik yok. 50: bf(30) = −2, bf(40) = −1 → RR; 30'da sola → 20(10, 40(30, 50)). 35: 30'un sağına düşer; bf(20) = −2, bf(40) = 1 → RL; 40'ta sağa, 20'de sola. Son ağaç 30(20(10, —), 40(35, 50)), yükseklik 2.

6. Boş bir kırmızı-siyah ağaca sırasıyla 30, 20, 10, 25, 27 ekleniyor. Düzeltme gerektiren eklemelerde hangi durum uygulanır? Son ağacı renkleriyle yazın.

   Cevap

   10: ebeveyn 20 kırmızı, amca NIL, 10–20–30 çizgi → 30'da sağa döndür; 20 siyah, 30 kırmızı: 20S(10K, 30K). 25: ebeveyn 30 kırmızı, amca 10 kırmızı → renk değiştir (10 ve 30 siyah, 20 kırmızı), 20 kök olduğu için yeniden siyah. 27: ebeveyn 25 kırmızı, amca NIL; 27 sağ, 25 sol çocuk → üçgen: 25'te sola, sonra 30'da sağa döndür; 27 siyah, 30 kırmızı. Son ağaç 20S(10S, 27S(25K, 30K)); her yolda 2 siyah düğüm.

7. Splay ağacı 50(30(20(10, —), 40), 70) olsun. splay(40) hangi adımla çalışır ve sonuç ağacı nedir?

   Cevap

   Arama yolu 50 → 30 → 40'tır; p = 30, g = 50. 40, 30'un sağ çocuğu; 30 ise 50'nin sol çocuğudur: zıt yön, zig-zag. Önce 30'da sola, sonra 50'de sağa döndürülür. Sonuç 40(30(20(10, —), —), 50(—, 70)). 40 tek adımda köke çıktı.

8. Derecesi 3 olan boş bir B-ağacına sırasıyla 5, 15, 25, 35, 45 ekleniyor. Hangi eklemelerde bölünme olur ve son ağaç nedir?

   Cevap

   25 eklenince [5, 15, 25] taşar; 15 yeni köke çıkar: [15]{[5] [25]}. 35 sağ yaprağa eklenir: [25, 35]. 45 eklenince [25, 35, 45] taşar; 35 köke çıkar ve kökte yer vardır: [15, 35]{[5] [25] [45]}. İki bölünme olur, kök bir kez bölünür; yükseklik 1'dir.

9. Kökünün siyah yüksekliği 3 olan bir kırmızı-siyah ağaçta kökten bir NIL'e giden en kısa ve en uzun yol en çok kaç düğüm içerebilir? Böyle bir ağaçta en az kaç düğüm vardır?

   Cevap

   Her yolda 3 siyah düğüm vardır. En kısa yol yalnız siyahlardan oluşur: 3 düğüm. En uzun yolda her siyahın altına bir kırmızı girebilir: en çok 6 düğüm (kök siyah olduğu için siyah, kırmızı, siyah, kırmızı, siyah, kırmızı). En az düğüm sayısı 2³ − 1 = 7'dir: bütün düğümleri siyah olan, yüksekliği 2 olan mükemmel ağaç.

10. Şekil 10.42'deki B+ ağacında 22 ile 55 arasındaki anahtarlar isteniyor. Sonuç nedir ve kaç yaprak okunur?

    Cevap

    Kökte 20 ≤ 22 < 40 olduğu için orta çocuğa, [20, 25, 30] yaprağına inilir. 20 atlanır; 25 ve 30 alınır. Bağ izlenerek [40, 50, 60] yaprağına geçilir; 40 ve 50 alınır, 60 > 55 olduğu için durulur. Sonuç 25 30 40 50'dir; 2 yaprak okunur ve köke bir daha çıkılmaz.

10.12İleri okuma

• M. T. Goodrich, R. Tamassia ve M. H. Goldwasser, Data Structures and Algorithms in Java (6. baskı, 2014), Bölüm 11: ikili arama ağaçlarını, AVL, splay, (2, 4) ve kırmızı-siyah ağaçları aynı sırayla işler. Kodları bu nottakilere yakın bir Java diliyle yazılmıştır.
• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Kesim 3.2 ve 3.3: BST'yi ve sola yatık kırmızı-siyah ağacı 2-3 ağaçlarıyla ilişkilendirerek anlatır; kırmızı-siyah ağacın neden çalıştığını görmenin en kolay yoludur.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (4. baskı, 2022), Bölüm 12, 13 ve 18: BST, kırmızı-siyah ağaç (silme dahil bütün durumlarıyla) ve B-ağaçlarını ispatlarıyla verir.
• D. D. Sleator ve R. E. Tarjan, “Self-Adjusting Binary Search Trees” (1985): splay ağacını tanıtan özgün makaledir; amortize O(log n) sınırının potansiyel fonksiyonuyla ispatını içerir.

10.13Kaynaklar

1. G. M. Adelson-Velsky, E. M. Landis, “An algorithm for the organization of information”, Soviet Mathematics Doklady, 3, 1259–1263, 1962.
2. R. Bayer, E. M. McCreight, “Organization and maintenance of large ordered indexes”, Acta Informatica, 1(3), 173–189, 1972.
3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022.
4. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6. baskı, Wiley, 2014.
5. L. J. Guibas, R. Sedgewick, “A dichromatic framework for balanced trees”, 19th Annual Symposium on Foundations of Computer Science, 8–21, 1978.
6. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011.
7. D. D. Sleator, R. E. Tarjan, “Self-adjusting binary search trees”, Journal of the ACM, 32(3), 652–686, 1985.

İlgili sayfalar: Bölüm 10 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.