Dengeli Ağaç
- İngilizcesi
- Balanced Tree
- Okunuşu
- belınst tri
Kısaca
Dengeli ağaç, her değişiklikten sonra dengelenerek yüksekliğini log n civarında tutan ağaçtır; arama, ekleme ve silme en kötü durumda bile O(log n) kalır.
Dengeli ağaç (balanced tree) nedir?
Dengeli ağaç, hiçbir dalın diğerlerinden çok daha derine inmesine izin verilmeyen ve yüksekliği n düğüm sayısı olmak üzere log n ile orantılı kalan bir ağaçtır. Yükseklik önemlidir, çünkü arama, ekleme ve silmenin hepsi kökten aşağıya tek bir yol boyunca ilerler: bir milyon düğümlü dengeli bir ağaç yalnızca yaklaşık 20 seviye yüksekliğindedir, dolayısıyla bir işlem yaklaşık 20 adım sürer. Kendi kendini dengeleyen ağaçlar, verinin hangi sırayla geldiğinden bağımsız olarak bu biçimi otomatik olarak korur.
En bilinen kendi kendini dengeleyen ikili arama ağaçları AVL ağaçları ve kırmızı-siyah ağaçlardır. AVL ağacı, her düğümün iki alt ağacının yüksekliklerinin en fazla bir farklı olmasını gerektirir; kırmızı-siyah ağaç ise her düğümü kırmızı ya da siyaha boyar ve kökten en uzun yolu en kısa yolun en fazla iki katı tutan kuralları izler. Bir ekleme ya da silmeden sonra ikisi de ihlalleri rotasyonlarla, yani sıralı düzeni koruyarak birkaç ebeveyn-çocuk bağını değiştiren küçük yerel yeniden düzenlemelerle onarır. AVL ağaçları daha sıkı dengelidir ve aramada biraz daha hızlıdır; kırmızı-siyah ağaçlar ise güncellemelerde daha az rotasyon gerektirir ve birçok standart kütüphanenin onları kullanmasının nedeni budur.
Her yöneticinin benzer sayıda çalışanı olduğu, böylece herhangi bir çalışanın CEO'nun yalnızca birkaç seviye altında olduğu iyi yönetilen bir şirketi düşünün; dengesiz ağaç ise herkesin tam olarak bir başka kişiye bağlı olduğu ve en yeni işe alınanın yüzlerce seviye aşağıda kaldığı bir şirkettir. Dengeli ağaçlar, genellikle kırmızı-siyah ağaç olan Java'nın TreeMap ve C++'ın std::map yapıları gibi standart kütüphanelerdeki sıralı map ve sıralı koleksiyonlara güç verir; ayrıca işletim sistemi çekirdeklerinde, örneğin CPU zamanlayıcılarda görülür. Diskte saklanan veriler için veritabanları, tüm yapraklarını aynı derinlikte tutarak dengeli kalan B-ağaçlarını kullanır.
Dengeli ağaç sıklıkla sade bir ikili arama ağacı ve tam ağaçla karıştırılır. Sade bir BST aynı sıralama kuralını izler ama asla yeniden dengelenmez; sıralı veri eklemek onu O(n) işlemli uzun bir zincire dönüştürür, dengelemenin çözdüğü sorun tam olarak budur. Heap'lerin kullandığı biçim olan tam ikili ağaç ise her seviyeyi soldan sağa doldurur; her zaman dengelidir, ancak dengeli bir ağacın tam olması gerekmez.
Önemli noktalar
- Dengeli ağaç yüksekliğini log n ile orantılı tutar.
- Arama, ekleme ve silme, veri sıralı gelse bile O(log n) olarak garanti edilir.
- AVL ağaçları ve kırmızı-siyah ağaçlar kendilerini rotasyonlarla yeniden dengeler.
- Java'nın
TreeMapve C++'ınstd::mapgibi sıralı map'ler arka planda dengeli ağaçlardır. - Dengesiz bir ikili arama ağacı O(n) işlemli bir zincire dönüşebilir.
Örnek
class Node:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
def rotate_left(x):
# x's right child y becomes the new root of this subtree
y = x.right
x.right = y.left # y's left subtree moves under x, keeping the order intact
y.left = x
return y
# Inserting 1, 2, 3 in sorted order builds a chain: 1 -> 2 -> 3 (height 3)
root = Node(1, right=Node(2, right=Node(3)))
root = rotate_left(root) # the kind of repair AVL and red-black trees make
print(root.value, root.left.value, root.right.value) # 2 1 3 (height 2)Sık sorulan sorular
Bir ağacı dengeli yapan nedir?
Ağacın yüksekliği log n ile orantılı kaldığında dengelidir; bu genellikle her düğüm için sol ve sağ alt ağaçların benzer yüksekliklerde olması demektir. Her dengeli ağaç türü bunu kesin olarak tanımlar; örneğin AVL ağacı en fazla bir yükseklik farkına izin verir.
AVL ağacı ile kırmızı-siyah ağaç arasındaki fark nedir?
İkisi de O(log n) işlemli, kendi kendini dengeleyen ikili arama ağaçlarıdır. AVL ağaçları daha sıkı dengelidir, bu yüzden aramalar biraz daha hızlıdır; kırmızı-siyah ağaçlar biraz daha fazla dengesizliğe izin verir ve veri değiştiğinde daha az rotasyon gerektirir; bu da çok sayıda ekleme ve silme içeren iş yüklerine uygundur.
Neden hash tablosu yerine dengeli ağaç kullanılır?
Hash tablosu tam anahtarla aramada ortalamada O(1) ile daha hızlıdır ama hiçbir sırayı korumaz. Dengeli ağaç anahtarları sıralı tutar; bu yüzden aralık sorgularını, bir sonraki daha büyük anahtarı bulmayı ve öğeleri sıralı listelemeyi verimli biçimde yapabilir.
İlgili sayfalar
- İkili Arama AğacıVeri Yapıları, s. 22İkili arama ağacı, her düğümün sol alt ağacında küçük, sağ alt ağacında büyük değerler bulunan ve hızlı sıralı aramaya olanak tanıyan bir ikili ağaçtır.
- AğaçVeri Yapıları, s. 2Ağaç, kenarlarla bağlı düğümlerden oluşan hiyerarşik bir veri yapısıdır; en üstte tek bir kök düğüm ve altında dallanan çocuk düğümler bulunur.
- B-TreeVeri Yapıları, s. 3B-tree, düğümleri çok sayıda sıralı anahtar ve çocuk tutan, kendini dengeleyen arama ağacıdır; sığ kaldığından aramalar çok az disk ya da sayfa okuması ister.
- HeapVeri Yapıları, s. 19Heap, en küçük ya da en büyük öğeyi kökünde tutan ağaç tabanlı bir veri yapısıdır; bu öğeyi O(1)'de okuyabilir ve O(log n)'de çıkarabilirsiniz.
- Hash TablosuVeri Yapıları, s. 18Hash tablosu, anahtar-değer çiftlerini saklayan ve hash fonksiyonuyla herhangi bir anahtarın değerini ortalamada sabit sürede bulan bir veri yapısıdır.
- Big O gösterimiProgramlamanın Temelleri, s. 4Big O gösterimi, girdi büyüdükçe bir algoritmanın çalışma süresinin ya da bellek kullanımının nasıl arttığını, kesin hız yerine büyüme oranıyla anlatır.
Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin