BST'yi Java ile yazmak

Geçen hafta BST’yi kâğıt üzerinde işledin. Bu hafta aynı algoritmaları Java’ya döküyoruz. Sınavda iki tip soru gelir: verilen kodun çıktısı (insert/remove çağrıları sonrası gezinme) ve “write a method”: size, height, aralıktaki eleman sayısı, k. en küçük, BST kontrolü gibi kısa özyinelemeli metotlar. Bu sayfadaki kalıpları bilen biri yeni bir metodu da 5 dakikada yazar.

Üç altın kural:

1. Özyinelemeli metot düğüm döndürür, çağıran atar: t.left = insert(x, t.left);. Java’da referans değerle geçer.
2. Her metot önce t == null durumunu çözer. Temel durum (base case) yanlışsa gerisi çöker.
3. BST’de bir tarafı budayabiliyorsan buda. Arama, aralık ve floor gibi işlemler O(h), tüm ağacı gezen işlemler O(n).

Sınıfın iskeleti

Anahtar tipi generic. Karşılaştırma < ile değil compareTo ile yapılır, bu yüzden tip Comparable olmalı.

public class BinarySearchTree<T extends Comparable<? super T>> {

    private static class BinaryNode<T> {
        T element;
        BinaryNode<T> left, right;
        BinaryNode(T e) { element = e; }
    }

    private BinaryNode<T> root;   // boş ağaçta null

    public boolean isEmpty() { return root == null; }
    public void makeEmpty()  { root = null; }
}

• BinaryNode private static nested class: dışarıdan görünmez, ağaç nesnesine bağlı değil.
• <? super T>: T’nin kendisi değil de üst sınıfı Comparable olsa da kabul et demek. Ezberlemen yeterli.
• makeEmpty sadece kökü null yapar. Düğümleri çöp toplayıcı (garbage collector) temizler.

Public sürücü, private yardımcı

Her işlem iki metottan oluşur. Public olan kullanıcıya açık ve sadece kökü verir. Private olan asıl özyinelemeyi yapar ve bir alt ağacın kökünü parametre alır.

public void insert(T x)      { root = insert(x, root); }
public void remove(T x)      { root = remove(x, root); }
public boolean contains(T x) { return contains(x, root); }

Kullanıcı düğüm kavramını hiç görmez. Kökün değişebileceği işlemlerde (ilk ekleme, kökü silme) root = ... ataması şart.

contains, findMin, findMax

private boolean contains(T x, BinaryNode<T> t) {
    if (t == null) return false;
    int c = x.compareTo(t.element);
    if (c < 0) return contains(x, t.left);
    if (c > 0) return contains(x, t.right);
    return true;                         // c == 0: bulundu
}

private BinaryNode<T> findMin(BinaryNode<T> t) {
    if (t.left == null) return t;        // özyinelemeli
    return findMin(t.left);
}

private BinaryNode<T> findMax(BinaryNode<T> t) {
    while (t.right != null) t = t.right; // döngüyle
    return t;
}

compareTo negatif, sıfır ya da pozitif döner. == -1 diye kontrol etme: sözleşme sadece işaret garantiler. contains kuyruk özyinelemesi (tail recursion) olduğu için döngüye çevirmek kolay. findMin ve findMax private sürümleri düğüm döndürür, public sürümleri boş ağaçta istisna fırlatıp element döndürür.

insert

private BinaryNode<T> insert(T x, BinaryNode<T> t) {
    if (t == null) return new BinaryNode<>(x);   // yeni yaprak
    int c = x.compareTo(t.element);
    if (c < 0)      t.left  = insert(x, t.left);
    else if (c > 0) t.right = insert(x, t.right);
    // c == 0: tekrar, bir şey yapma
    return t;
}

Mantığı adım adım: insert(25, kök) çağrısı 40’tan 20’ye, 20’den 30’a iner. 30’un solu null, insert(25, null) yeni düğüm döndürür ve 30.left = yeni düğüm ataması yapılır. Yukarı dönerken diğer atamalar (20.right = 30, 40.left = 20) zaten olan bağlantıları yeniden yazar, bir şey bozmaz.

TUZAK · atamasız özyineleme. insert(x, t.left); yazıp dönen değeri atamazsan yeni düğüm havada kalır. Metodun içinde t = new BinaryNode<>(x) yapmak çağırandaki referansı değiştirmez. Sonuç: ağaçta sadece kök olur.

remove

private BinaryNode<T> remove(T x, BinaryNode<T> t) {
    if (t == null) return null;                  // yok: bir şey yapma
    int c = x.compareTo(t.element);
    if (c < 0)      t.left  = remove(x, t.left);
    else if (c > 0) t.right = remove(x, t.right);
    else if (t.left != null && t.right != null) {        // iki çocuk
        t.element = findMin(t.right).element;
        t.right = remove(t.element, t.right);
    } else {                                     // 0 ya da 1 çocuk
        t = (t.left != null) ? t.left : t.right;
    }
    return t;
}

Son satırdaki üçlü ifade iki durumu birden çözer. Yaprakta iki çocuk da null, t null olur ve ebeveynin referansı null’a atanır. Tek çocukta t o çocuğa döner ve ebeveyn doğrudan ona bağlanır.

İki çocuk durumunda sağ alt ağaçta ikinci bir arama yapılıyor. Toplam yine $O(h)$: bir kez aşağı inip successor’ı bulmak, bir kez de onu silmek.

Gezinmeler, size, height

private void inorder(BinaryNode<T> t, StringBuilder sb) {
    if (t == null) return;
    inorder(t.left, sb);
    sb.append(t.element).append(' ');
    inorder(t.right, sb);
}

private int size(BinaryNode<T> t) {
    return t == null ? 0 : 1 + size(t.left) + size(t.right);
}

private int height(BinaryNode<T> t) {
    return t == null ? -1 : 1 + Math.max(height(t.left), height(t.right));
}

size her çağrıda tüm ağacı gezdiği için $O(n)$. Sık çağrılıyorsa sınıfa bir int size alanı koyup insert ve remove’da güncellemek $O(1)$ verir. Ama o zaman insert’in gerçekten eklenip eklenmediğini (tekrar mı) bilmen gerekir.

Çalışan örnek

BinarySearchTree<Integer> bst = new BinarySearchTree<>();
int[] keys = {40, 20, 60, 10, 30, 50, 70, 25};
for (int k : keys) bst.insert(k);
System.out.println("inorder  : " + bst.inorder());
System.out.println("preorder : " + bst.preorder());
System.out.println("postorder: " + bst.postorder());
System.out.println("size=" + bst.size() + " height=" + bst.height()
        + " min=" + bst.findMin() + " max=" + bst.findMax());
System.out.println("contains 25? " + bst.contains(25)
        + ", contains 35? " + bst.contains(35));
bst.remove(20);
System.out.println("after remove(20): " + bst.preorder());

inorder  : 10 20 25 30 40 50 60 70
preorder : 40 20 10 30 25 60 50 70
postorder: 10 25 30 20 50 70 60 40
size=8 height=3 min=10 max=70
contains 25? true, contains 35? false
after remove(20): 40 25 10 30 60 50 70

  ekleme sonrası       remove(20) sonrası
       40                    40
     /    \                /    \
   20      60            25      60
  /  \    /  \          /  \    /  \
10   30  50   70      10   30  50   70
     /
   25

20’nin successor’ı sağ alt ağacın en küçüğü, yani 25. Aynı sınıf String ile de çalışır: "mango kiwi apple peach banana" eklenince inorder apple banana kiwi mango peach çıkar, çünkü String’in compareTo’su alfabetik.

Write-a-method kalıpları

Sınavda istenen metotların çoğu üç kalıptan birine uyar.

Bu sayfanın sorularında kullanılan örnek ağaç (50, 30, 70, 20, 40, 60, 80, 35, 45, 65 sırasıyla eklendi):

            50
          /    \
        30      70
       /  \    /  \
     20   40  60   80
         / \    \
       35  45    65

İPUCU · önce boş ağacı ve tek düğümü düşün. Yazdığın metodu null ve tek yaprakla kafanda çalıştır. Bu iki durum doğruysa özyineleme genelde gerisini halleder.

Sık yapılan hatalar

BinarySearchTree<Integer> t = new BinarySearchTree<>();
for (int x : new int[]{33, 18, 47, 9, 25, 40, 52, 18}) t.insert(x);
System.out.println(t.findMin() + " " + t.findMax() + " " + t.size());

BinarySearchTree<Integer> u = new BinarySearchTree<>();
for (int x : new int[]{33, 18, 47, 9, 25, 40, 52, 21}) u.insert(x);
u.remove(18);
u.remove(47);
System.out.println(u.preorder());
System.out.println(u.height());

static int mystery(Node t) {
    if (t == null) return 0;
    int c = ((t.left == null) != (t.right == null)) ? 1 : 0;
    return c + mystery(t.left) + mystery(t.right);
}

static Node badInsert(Node t, int x) {
    if (t == null) return new Node(x);
    if (x < t.element) badInsert(t.left, x);
    else if (x > t.element) badInsert(t.right, x);
    return t;
}

static int size(Node t) {
    if (t == null) return 0;
    return 1 + size(t.left) + size(t.right);
}

static int countInRange(Node t, int lo, int hi) {
    if (t == null) return 0;
    if (t.element < lo) return countInRange(t.right, lo, hi);
    if (t.element > hi) return countInRange(t.left, lo, hi);
    return 1 + countInRange(t.left, lo, hi)
             + countInRange(t.right, lo, hi);
}

static boolean isBST(Node t) {
    return isBST(t, Long.MIN_VALUE, Long.MAX_VALUE);
}
static boolean isBST(Node t, long lo, long hi) {
    if (t == null) return true;
    if (t.element <= lo || t.element >= hi) return false;
    return isBST(t.left, lo, t.element)
        && isBST(t.right, t.element, hi);
}

static int count, answer;
static int kthSmallest(Node t, int k) {
    count = 0; answer = -1;
    kth(t, k);
    return answer;
}
static void kth(Node t, int k) {
    if (t == null || count >= k) return;
    kth(t.left, k);
    if (++count == k) { answer = t.element; return; }
    kth(t.right, k);
}

static Integer floor(Node t, int x) {
    Integer best = null;
    while (t != null) {
        if (t.element == x) return x;
        if (t.element < x) { best = t.element; t = t.right; }
        else t = t.left;
    }
    return best;
}

static Node lca(Node t, int a, int b) {
    while (t != null) {
        if (a < t.element && b < t.element) t = t.left;
        else if (a > t.element && b > t.element) t = t.right;
        else return t;
    }
    return null;
}