Ağaç döndürme - Tree rotation

Genel ağaç rotasyonları.

Olarak ayrık matematik , ağaç dönme bir bir işlemdir ikili ağaç elemanları düzenine karışmadan yapısını değiştirir. Bir ağaç döndürme, ağaçtaki bir düğümü yukarı ve bir düğümü aşağı hareket ettirir. Ağacın şeklini değiştirmek ve özellikle daha küçük alt ağaçları aşağı ve daha büyük alt ağaçları yukarı hareket ettirerek yüksekliğini azaltmak için kullanılır, bu da birçok ağaç işleminin performansının artmasını sağlar.

Dönme yönünün tanımına ilişkin farklı açıklamalarda tutarsızlık vardır . Bazıları dönüş yönünün bir düğümün dönüş sırasında hareket ettiği yönü yansıttığını söylerken (ebeveyninin konumuna dönen bir sol çocuk bir sağa dönüştür), diğerleri ise dönüş yönünün hangi alt ağacın döndüğünü (bir sol alt ağaç ebeveyninin konumu, öncekinin tersi olan bir sola dönüştür). Bu makale, dönen düğümün yönlü hareketi yaklaşımını ele almaktadır.

illüstrasyon

Ağaç döndürme.svg
Gerçekleşen ağaç rotasyonlarının animasyonu.

Bitişik resimde gösterildiği gibi sağa döndürme işlemi , kök olarak Q ile gerçekleştirilir ve bu nedenle, Q üzerinde veya Q'da köklenmiş bir sağa döndürmedir . Bu işlem ağacın saat yönünde dönmesine neden olur. Ters işlem, saat yönünün tersine bir hareketle sonuçlanan sola dönüştür (yukarıda gösterilen sola dönüş, P'ye dayanmaktadır ). Bir rotasyonun nasıl çalıştığını anlamanın anahtarı, kısıtlamalarını anlamaktır. Özellikle, ağacın yapraklarının sırası (örneğin soldan sağa okunduğunda) değişemez (bunu düşünmenin başka bir yolu, yaprakların bir sıralı geçişte ziyaret edilme sırasının, yapraktan sonra aynı olması gerektiğidir). daha önce olduğu gibi çalışma). Diğer bir kısıtlama, ikili arama ağacının ana özelliğidir, yani sağ çocuk ebeveynden büyük ve sol çocuk ebeveynden küçüktür . O Bildirimi doğru çocuk bir alt ağacı (Q köklü ağaç için şemada örneğin düğüm B) kökünden bir sol çocuğun kendisini "sağ çocuğu olur, kökün sol çocuk haline gelebilir new" kökünü, bu kısıtlamalardan herhangi birini ihlal etmeden döndürülmüş alt ağaçta. Şemada da görebileceğiniz gibi, yaprakların sırası değişmez. Ters işlem de sırayı korur ve ikinci tür döndürmedir.

Bunun bir ikili arama ağacı olduğunu varsayarsak , yukarıda belirtildiği gibi, öğeler birbiriyle karşılaştırılabilecek değişkenler olarak yorumlanmalıdır. Soldaki alfabetik karakterler bu değişkenler için yer tutucu olarak kullanılır. Sağdaki animasyonda, büyük alfabetik karakterler değişken yer tutucular olarak kullanılırken, küçük Yunan harfleri tüm değişkenler için yer tutuculardır. Daireler bireysel düğümleri ve üçgenler alt ağaçları temsil eder. Her alt ağaç boş olabilir, tek bir düğümden oluşabilir veya herhangi bir sayıda düğümden oluşabilir.

Detaylı illüstrasyon

Rotasyonların nasıl yapıldığının resimli açıklaması.

Bir alt ağaç döndürüldüğünde, döndürüldüğü alt ağaç tarafı yüksekliğini bir düğüm artırırken diğer alt ağaç yüksekliğini azaltır. Bu, bir ağacı yeniden dengelemek için ağaç rotasyonlarını faydalı hale getirir.

Dönecek alt ağaçların üst düğümü için Root , yeni üst düğüm olacak düğüm için Pivot , dönüş tarafı için RS ve dönüşün karşı tarafı için OS terminolojisini düşünün . Yukarıdaki diyagramdaki Q kökü için RS , C ve OS P'dir. Bu terimleri kullanarak, döndürme için sözde kod: 

Pivot = Root.OS
Root.OS = Pivot.RS
Pivot.RS = Root
Root = Pivot

Bu sabit zamanlı bir işlemdir.

Programcı ayrıca, döndürmeden sonra kökün ebeveyninin pivotu gösterdiğinden emin olmalıdır. Ayrıca programcı, bu işlemin tüm ağaç için yeni bir kök ile sonuçlanabileceğini unutmamalı ve işaretçileri buna göre güncellemeye özen göstermelidir.

sıra değişmezliği

Ağaç döndürme, ikili ağacın sıra dışı geçişini değişmez kılar . Bu, ağacın herhangi bir bölümünde bir döndürme gerçekleştirildiğinde öğelerin sırasının etkilenmediği anlamına gelir. Yukarıda gösterilen ağaçların sıralı geçişleri şunlardır: 

Left tree: ((A, P, B), Q, C)        Right tree: (A, P, (B, Q, C))

Birini diğerinden hesaplamak çok basittir. Aşağıda, bu hesaplamayı gerçekleştiren örnek Python kodu verilmiştir: 

def right_rotation(treenode):
    """Rotate the specified tree to the right."""
    left, Q, C = treenode
    A, P, B = left
    return (A, P, (B, Q, C))

Buna bakmanın başka bir yolu şudur:

Q düğümünün sağa dönüşü: 

Let P be Q's left child.
Set Q's left child to be P's right child.
[Set P's right-child's parent to Q]
Set P's right child to be Q.
[Set Q's parent to P]

P düğümünün sola dönüşü: 

Let Q be P's right child.
Set P's right child to be Q's left child.
[Set Q's left-child's parent to P]
Set Q's left child to be P.
[Set P's parent to Q]

Diğer tüm bağlantılar olduğu gibi bırakılır.

Ayrıca sol ve sağ dönüşlerin kombinasyonları olan çift ​​dönüşler de vardır. X'te bir çift ​​sola dönüş, X'in sağ alt öğesinde bir sağa dönüş ve ardından X'te bir sola dönüş olarak tanımlanabilir; benzer şekilde, X'te bir çift ​​sağa dönüş, X'in sol alt öğesinde bir sola dönüş ve ardından X'te bir sağa dönüş olarak tanımlanabilir.

Ağaç rotasyonlar ağaç bir dizi kullanılır veri yapıları gibi AVL ağaçları , kırmızı-siyah ağaçlar , WAVL ağaçları , yayvan ağaçlar ve treaps . Yerel dönüşümler oldukları için yalnızca sabit zamana ihtiyaç duyarlar : yalnızca 5 düğüm üzerinde çalışırlar ve ağacın geri kalanını incelemeleri gerekmez.

Yeniden dengeleme için rotasyonlar

Bir AVL ağacında rotasyonların nasıl yeniden dengelemeye neden olduğunun resimli açıklaması.

Bir ağaç, rotasyonlar kullanılarak yeniden dengelenebilir. Bir dönüşten sonra, dönüşün olduğu taraf yüksekliğini 1 artırırken, dönüşün karşısındaki taraf benzer şekilde yüksekliğini azaltır. Bu nedenle, sol alt ve sağ alt öğeleri arasında yükseklik farkı 1'den fazla olan düğümlere stratejik olarak rotasyonlar uygulanabilir. Kendi kendini dengeleyen ikili arama ağaçları bu işlemi otomatik olarak uygular. Bu yeniden dengeleme tekniğini kullanan bir ağaç türü AVL ağacıdır .

Dönme mesafesi

Ana madde: Dönme mesafesi
Bilgisayar biliminde çözülmemiş problem :

İki ikili ağaç arasındaki dönüş mesafesi polinom zamanında hesaplanabilir mi?

(bilgisayar biliminde daha çözülmemiş problemler)

Dönme mesafesi düğümleri aynı sayıda herhangi iki ikili ağaç arasında diğer içine bir dönüştürmek için gerekli dönüş minimum sayısıdır. Bu mesafe ile, n- düğümlü ikili ağaçlar kümesi bir metrik uzay haline gelir : mesafe simetriktir, iki farklı ağaç verildiğinde pozitiftir ve üçgen eşitsizliğini sağlar .

Bir olan açık problem bir var olup olmadığını polinom zaman algoritması dönme mesafenin hesaplanması için. Yine de Fordham'ın algoritması doğrusal zamanda bir mesafe hesaplar, ancak yalnızca 2 tür döndürmeye izin verir: (ab)c = a(bc) ve a((bc)d) = a(b(cd))). Fordham'ın algoritması, düğümlerin 7 türde sınıflandırılmasına dayanır ve bir tür düğümü diğerine dönüştürmek için gereken dönüş sayısını bulmak için bir arama tablosu kullanılır.

Daniel Sleator , Robert Tarjan ve William Thurston , herhangi iki n- düğümlü ağaç ( n ≥ 11 için) arasındaki dönme mesafesinin en fazla 2 n  − 6 olduğunu ve n yeterli olduğunda bazı ağaç çiftlerinin bu kadar uzakta olduğunu gösterdiler. büyük. Lionel Pournin, aslında bu tür çiftlerin n ≥ 11 olduğunda var olduğunu gösterdi .

Ayrıca bakınız

Referanslar

Dış bağlantılar