--- title: '2-3 ve 2-3-4 Ağaçları' source: 'https://academia.sh/tr/kurslar/veri-yapilari/2-3-agaclari' course: 'Veri Yapıları' language: tr updated: '2026-08-17T18:07:59+00:00' license: 'CC BY-SA 4.0' --- # 2-3 ve 2-3-4 Ağaçları Düğüm başına çok anahtar, bölünerek yukarı büyüme, kusursuz derinlik dengesi ve kırmızı–siyah ağaçlarla eşlik. Önceki ders dengeyi dönmelerle onarıyordu: ağaç bozulur, sonra düzeltilir. Bu dersin yaklaşımı farklıdır — ağaç **hiçbir zaman bozulmaz**, çünkü büyüme biçimi dengeyi tanım gereği korur. Fikir, ikili kısıtından vazgeçmektir: bir düğüm birden çok anahtar taşıyabilir. ## İki Düğüm Türü **2-3 ağacında** iki tür düğüm bulunur: - **2-düğüm:** Bir anahtar, iki çocuk. Sol alt ağaç küçükleri, sağ alt ağaç büyükleri taşır — sıradan bir arama ağacı düğümü. - **3-düğüm:** İki anahtar, üç çocuk. Sol alt ağaç birinci anahtardan küçükleri, orta alt ağaç iki anahtar arasındakileri, sağ alt ağaç ikinci anahtardan büyükleri taşır. ``` [7 | 12] ← 3-düğüm: iki anahtar, üç çocuk / | \ [3] [10] [25 | 30] ``` Yapının belirleyici kuralı şudur: **tüm yapraklar aynı derinliktedir.** Bu, sonradan sağlanan bir özellik değil, ekleme yönteminin doğrudan sonucudur. ## Arama Arama, ikili ağaçtakine benzer; tek fark, düğüm içinde birden çok anahtarın karşılaştırılmasıdır. Anahtar düğümde bulunursa arama biter; bulunmazsa değerin hangi aralığa düştüğüne bakılarak ilgili çocuğa inilir. Düğüm içindeki karşılaştırma sayısı en fazla ikidir, yani sabittir. Maliyet yine yükseklikle orantılıdır. ## Ekleme: Aşağıdan Yukarı Büyüme Ekleme her zaman bir yaprağa yapılır. Üç durum vardır: **Yaprak 2-düğümse**, anahtar eklenir ve düğüm 3-düğüme dönüşür. Ağacın biçimi değişmez. **Yaprak 3-düğümse**, geçici olarak üç anahtarlı bir düğüm oluşur. Bu düğüm **bölünür**: ortadaki anahtar bir üst düğüme **terfi eder**, kalan iki anahtar iki ayrı 2-düğüm olur. **Terfi eden anahtar üst düğümü de taşırırsa**, aynı bölünme bir üst seviyede tekrarlanır. Bölünme köke kadar sürebilir; kök bölünürse yeni bir kök oluşur ve **ağacın yüksekliği bir artar.** Son madde, yapının denge güvencesinin kaynağıdır. Ağaç yapraklardan değil **kökten** büyür; tüm yapraklar aynı anda bir seviye aşağı iner, dolayısıyla derinlik farkı hiçbir zaman oluşmaz. ```python class Dugum23: """2-3 ağacı düğümü: bir veya iki anahtar; sıfır, iki veya üç çocuk.""" def __init__(self, anahtarlar: list[int], cocuklar: list | None = None) -> None: self.anahtarlar = anahtarlar self.cocuklar = cocuklar or [] def yaprak_mi(self) -> bool: return not self.cocuklar def _ekle(dugum: Dugum23, deger: int): """(düğüm, terfi) döndürür; terfi = (anahtar, sol, sağ) ya da None.""" if dugum.yaprak_mi(): anahtarlar = sorted(dugum.anahtarlar + [deger]) if len(anahtarlar) <= 2: return Dugum23(anahtarlar), None # 2-düğüm → 3-düğüm orta = anahtarlar[1] # taştı: ortayı terfi ettir return None, (orta, Dugum23([anahtarlar[0]]), Dugum23([anahtarlar[2]])) i = 0 while i < len(dugum.anahtarlar) and deger > dugum.anahtarlar[i]: i += 1 alt, terfi = _ekle(dugum.cocuklar[i], deger) if terfi is None: dugum.cocuklar[i] = alt return dugum, None anahtar, sol, sag = terfi # alttan bir anahtar geldi anahtarlar = dugum.anahtarlar[:i] + [anahtar] + dugum.anahtarlar[i:] cocuklar = dugum.cocuklar[:i] + [sol, sag] + dugum.cocuklar[i + 1:] if len(anahtarlar) <= 2: return Dugum23(anahtarlar, cocuklar), None orta = anahtarlar[1] # bu düğüm de taştı return None, (orta, Dugum23([anahtarlar[0]], cocuklar[:2]), Dugum23([anahtarlar[2]], cocuklar[2:])) def ekle(kok: Dugum23 | None, deger: int) -> Dugum23: if kok is None: return Dugum23([deger]) dugum, terfi = _ekle(kok, deger) if terfi is None: return dugum anahtar, sol, sag = terfi return Dugum23([anahtar], [sol, sag]) # kök bölündü: yükseklik arttı def seviyeler(kok: Dugum23) -> list[list[list[int]]]: """Ağacı seviye seviye, düğümlerin anahtar listeleriyle gösterir.""" sonuc, sira = [], [kok] while sira: sonuc.append([d.anahtarlar for d in sira]) yeni = [] for d in sira: yeni.extend(d.cocuklar) sira = yeni return sonuc kok = None for deger in (3, 7, 10, 12, 25, 30): # sıralı ekleme kok = ekle(kok, deger) print(deger, "->", seviyeler(kok)) # 3 -> [[[3]]] # 7 -> [[[3, 7]]] # 10 -> [[[7]], [[3], [10]]] # 12 -> [[[7]], [[3], [10, 12]]] # 25 -> [[[7, 12]], [[3], [10], [25]]] # 30 -> [[[7, 12]], [[3], [10], [25, 30]]] ``` Çıktı, büyümenin nasıl yürüdüğünü adım adım gösterir. Üçüncü eklemede kök taşar, bölünür ve ağaç iki seviyeye çıkar. Beşinci eklemede bir yaprak taşar; orta anahtar köke terfi eder ve kök 3-düğüme dönüşür. Dikkat çekici olan, girdinin **sıralı** olmasıdır. Aynı sıra, sade ikili arama ağacında yüksekliği beş olan bir zincir üretiyordu; burada yükseklik birdir. ## 2-3-4 Ağaçları Aynı fikir bir adım genişletilirse **2-3-4 ağacı** elde edilir: düğümler bir, iki veya üç anahtar taşıyabilir. Bölünme eşiği dört anahtara çıkar; kural aynıdır. Ek esneklik, bölünmelerin daha seyrek olmasını sağlar. Buna karşılık düğüm içi karşılaştırma sayısı artar ve düğüm yapısı büyür. ## Kırmızı–Siyah Ağaçlarla Eşlik 2-3-4 ağaçları ile önceki dersteki kırmızı–siyah ağaçlar arasında birebir bir karşılık vardır: bir 2-3-4 ağacı, düğümleri ikili yapıya açılarak kırmızı–siyah ağaca çevrilebilir. Karşılık şöyle kurulur: 2-düğüm siyah bir düğümdür; 3-düğüm, siyah bir düğüm ve ona bağlı bir kırmızı çocuktur; 4-düğüm ise siyah bir düğüm ve iki kırmızı çocuğudur. Kırmızı bağlar, "aslında aynı düğümün parçası" demektir. Bu eşlik, kırmızı–siyah kurallarının kaynağını açıklar. İki ardışık kırmızı düğümün yasaklanması, bir düğümün üçten fazla anahtar taşımamasıdır. Tüm yollarda siyah sayısının eşit olması, tüm yaprakların aynı derinlikte olmasıdır. Yani iki yapı aynı fikrin iki gösterimidir: biri düğüm başına çok anahtar tutar, diğeri aynı bilgiyi ikili ağaçta renklerle kodlar. İkili gösterim, düğüm yapısının sabit kalmasını sağladığı için gerçekleştirimde tercih edilir. ## Yükseklik Sınırı Tüm yapraklar aynı derinlikte olduğundan yükseklik doğrudan hesaplanır. Her düğüm en az iki, en fazla üç çocuk taşıdığına göre: $$ \log_3 n \leq h \leq \log_2 n $$ Her iki uçta da logaritmiktir; arama, ekleme ve silme $O(\log n)$'dir. Silme işlemi eklemenin aynadaki görüntüsüdür: düğüm anahtarsız kalırsa kardeşinden ödünç alır, kardeş de veremiyorsa iki düğüm birleştirilir ve eksilme bir üst seviyeye taşınır. Silmede dikkat edilecek nokta, eksilmenin de köke doğru yayılabilmesidir: birleşme zinciri köke ulaşırsa kök tek çocuğuyla değiştirilir ve ağacın yüksekliği bir azalır. Büyüme gibi küçülme de yalnızca kökten olur; denge bu nedenle hiç bozulmaz. ## Özet - 2-3 ağacında düğümler bir veya iki anahtar taşır; 2-düğümün iki, 3-düğümün üç çocuğu vardır. - Tüm yapraklar aynı derinliktedir ve bu, ekleme yönteminin doğrudan sonucudur. - Taşan düğüm bölünür, orta anahtar üst düğüme terfi eder; kök bölündüğünde yükseklik bir artar. - Ağaç yapraklardan değil kökten büyüdüğü için dengesizlik oluşmaz; sıralı girdi bile dejenere ağaç üretmez. - 2-3-4 ağacı aynı fikrin üç anahtara genişletilmiş hâlidir ve kırmızı–siyah ağaçla birebir eşlenir. - Yükseklik $\log_3 n$ ile $\log_2 n$ arasındadır; tüm işlemler logaritmiktir. ## Sonraki Adım Düğüm başına anahtar sayısı ikiden üçe çıkarıldığında ağaç sığlaştı. Sayı yüzlere çıkarılırsa ne olur? Bu soru, verinin bellekte değil diskte durduğu durumlarda kritik hâle gelir. Sonraki ders, blok tabanlı depolamaya göre tasarlanmış B-ağaçlarını ele alacak.