Vize tekrarı: sıralama, ağaçlar, BST, AVL, heap

Vize haftası. Bu sayfa yeni konu anlatmaz; ilk sekiz haftayı tek yerde toplar. Önce özet tabloya bak, sonra her konunun “sınavda nasıl çözülür” kalıbını oku, en son soruları kâğıt kalemle çöz. Her sorunun cevabını kendi izini çıkarmadan açma.

Vizede karşına çıkacak soru tipleri neredeyse sabittir:

1. Big-O: bir yapı ya da algoritma için en iyi, ortalama, en kötü süre.
2. İz sürme: “şu sırayla ekle, ağacı/diziyi çiz”.
3. Metot yazma: özyinelemeli (recursive) ağaç metotları: yükseklik, yaprak sayısı, toplam, arama.

Büyük tablo

Sıralama: hatırlanacaklar

Alt sınır. Sadece karşılaştırma yapan bir algoritma bir karar ağacıdır. $n!$ farklı sıralamanın her biri ayrı bir yaprakta bitmelidir. Yüksekliği h olan ikili ağaçta en fazla $2^h$ yaprak olduğundan:

$h \ge \lceil \log_2 n! \rceil = \Omega(n \log n)$

n   n!      en az karşılaştırma
3   6       3
4   24      5
5   120     7
6   720     10
8   40320   16

Counting ve radix bu sınırı neden geçer? Çünkü karşılaştırma yapmazlar. Değerin kendisini dizi indeksi olarak kullanırlar. Bunun bedeli: değerler küçük tam sayılar (ya da sabit uzunlukta anahtarlar) olmalı.

LSD radix izi. Her geçişte bir basamağa göre kararlı (stable) dağıt, kovaları sırayla topla:

başlangıç  512  34 208  71 645  93 160
birler     160  71 512  93  34 645 208
onlar      208 512  34 645 160  71  93
yüzler      34  71  93 160 208 512 645

TUZAK · radix’te kararlılık. Onlar geçişinde 208 ve 512 farklı kovalara gider, ama aynı kovaya düşen sayılar bir önceki geçişin sırasını korumalı. Kararlılığı bozarsan önceki geçişin işi kaybolur.

Ağaçlar ve gezinme

Şu ağacı ezberden çözebilmelisin:

        A
       / \
      B   C
     / \   \
    D   E   F
       /
      G

preorder   A B D E G C F    (kök, sol, sağ)
inorder    D B G E A C F    (sol, kök, sağ)
postorder  D G E B F C A    (sol, sağ, kök)
level      A B C D E F G    (kuyruk ile)
yükseklik  3, yaprak sayısı 3 (D, G, F)

Preorder + inorder’dan ağaç kurma. Preorder’ın ilk elemanı köktür. Inorder’da kökü bul: solundakiler sol alt ağaç, sağındakiler sağ alt ağaç. Preorder’da sıradaki eleman, sol alt ağacın köküdür. Özyinelemeli devam et.

pre: 5 9 1 3 7 2 8     in: 1 9 7 3 5 2 8

kök 5: in -> [1 9 7 3] 5 [2 8]
sol kök 9: in -> [1] 9 [7 3]
  9'un sağı kök 3: in -> [7] 3
sağ kök 2: in -> 2 [8]

          5
        /   \
       9     2
      / \     \
     1   3     8
        /
       7
post: 1 7 3 9 8 2 5

Sadece preorder + postorder ise ağaç tek değildir (tek çocuklu düğümün çocuğu solda mı sağda mı bilinmez). Inorder şarttır.

BST: ekleme ve silme

45, 20, 60, 10, 30, 50, 70, 25, 35 ekle:

           45
         /    \
       20      60
      /  \    /  \
    10    30 50   70
         /  \
        25   35

Silmenin üç durumu: yaprak ise doğrudan sil. Tek çocuk varsa çocuğu ebeveyne bağla. İki çocuk varsa değerini inorder successor (sağ alt ağacın en solu) ile değiştir, sonra successor’ı sağ alt ağaçtan sil (o en fazla bir çocukludur).

20’yi sil: successor 25.

           45
         /    \
       25      60
      /  \    /  \
    10    30 50   70
            \
             35

Preorder: 45 25 10 30 35 60 50 70. Sonra 45’i silersen successor 50 olur: 50 25 10 30 35 60 70.

AVL: rotasyon seçimi

Ekleme yolunda aşağıdan yukarı çıkarken BF’si +2 ya da -2 olan ilk düğüm rotasyon noktasıdır. Durumu oradan bakarak, eklemenin hangi torunda yapıldığına göre seç:

40, 20, 60, 10, 30 ekledikten sonra 25 ekle:

önce (25 eklendi)          sonra (LR at 40)
       40                        30
      /  \                     /    \
    20    60                 20      40
   /  \                     /  \       \
  10   30                  10   25      60
      /
    25

40’ın BF’si 2 - 0 = 2, ekleme sol çocuğun (20) sağına gitti: LR. Ortanca değer (30) yukarı çıkar.

Heap: buildHeap ve heapsort

buildHeap dizinin son iç düğümünden (n/2) köke doğru her düğümü aşağı süzer. Çoğu düğüm alt katlarda ve az süzülür; toplam iş $O(n)$.

[9, 4, 7, 1, 8, 2, 6]   n=7, i=3..1
i=3  7 <-> 2           [9, 4, 2, 1, 8, 7, 6]
i=2  4 <-> 1           [9, 1, 2, 4, 8, 7, 6]
i=1  9 -> 1 -> 4       [1, 4, 2, 9, 8, 7, 6]

Heapsort artan sıra için max-heap kurar (0-indeksli: çocuklar 2i+1, 2i+2). Sonra her adımda kökü (en büyük) dizinin aktif bölümünün sonuna koyar ve heap’i bir küçültür.

[3, 8, 5, 1, 9, 6]
buildHeap   [9, 8, 6, 1, 3, 5]
adım 1      [8, 5, 6, 1, 3 | 9]
adım 2      [6, 5, 3, 1 | 8, 9]
adım 3      [5, 1, 3 | 6, 8, 9]
adım 4      [3, 1 | 5, 6, 8, 9]
adım 5      [1 | 3, 5, 6, 8, 9]

Öncelik kuyruğu ve java.util.PriorityQueue için bu haftanın diğer sayfasına bak.

Sık yapılan hatalar

        A
       / \
      B   C
     / \   \
    D   E   F
       /
      G

static int height(Node t) {
    if (t == null) return -1;
    return 1 + Math.max(height(t.left), height(t.right));
}