Treap

Treap ya da tree heap (ağaç öbeği), arama, ekleme, silme gibi temel işlemler için log(n) zamanı garanti eden dinamik bir ikili arama ağacıdır. İkili arama ağacına sıralı şekilde ekleme yapılırsa binary arama ağacı bağlantılı listeye dönüşür ve arama ancak O(n) zamanda yapılabilir. Bu durumu ortadan kaldırmak için treap her düğümde binary arama ağacında kullanılan asıl değere ek olarak bir de rastgele oluşturulmuş bir anahtar tutar. Treap veri yapısı hem asıl değere göre veri ağacının kurallarına uyularak hem de rastgele anahtar ata düğümden küçük olacak şekilde kurulur.

Treap ilk defa Cecilia R. Aragon ve Raimund Seidel tarafından 1989 yılında önerilmiştir. Treap adı İngilizce ağaç anlamına gelen "tree" ve öbek anlamına gelen "heap" sözcüklerinin birleştirilmesinden oluşmuştur. Treap oluşturulurken ağaç yapısını bozmayacak şekilde işlemler icra edilir ardından treap'in heap yapısını bozmamak adına gerekli düzeltmeler sağa veya sola döndürme (right or left rotate) işlemleri ile yapılır.

Treap değerlerin rastgele anahtarlara göre sıralı olarak eklenmesi şeklinde de düzeltme işlemleri yapılmadan oluşturulabilir.

Bütün değerleri rastgele bir sırayla eklenmiş bir ağaçta rastgele seçilen bir elemana uzaklık O(log n)'dir. Kök düğümden seçilen herhangi bir başka elemana gidilirken şu an bulunduğumuz elemanın altında n elaman olduğunu varsayalım. Su anki elemanın bizim aradığımız elaman olma olasılığı n elaman rastgele biçimde dağıldığından 1/n'dir. Sol alt ağaç p-1 eleman barındırdığından aynı mantıkla gitmek istediğimiz elemanın orada olma olasılığı p-1/n'dir. Ayni şekilde sağ alt ağaç n-p düğüm barındırdığından olasılık n-p/n'dir. Bir adımda gelinecek alt ağaç büyüklüğünün beklenen değeri (p-1)·(p-1)/n + (n-p)·(n-p)/n + (1·1/n) olarak ortaya çıkar. P'nin bütün değerleri 1 ile n arasında eşit olasılıkla dağıldığından her adımda ziyaret edilecek ağaç büyüklüğü de aynı şekilde dağılır. Yukarıdaki ifadenin 1'den n'e kadar değerlerinin n ile bölümü: (1/n)∑ (p-1)2/n + (n-p)2/n + 1 = (1/n)((2/3)n2 - n + 4/3) = (2/3)n + O(1/n) şeklinde ortaya çıkar. Bu ifadeninde gosterdigi gibi, O(log 3/2n) adımda istenilen noktaya ulaşılması beklenir. Bu sebepten ekleme, silme ya da arama işlemlerinin O(log n) zamanda yapılabilir.

Operasyonlar ve işlemler

Arama

Arama işlemi ikili arama ağacındaki gibi anahtar değerleri göz ardı edilerek yapılır.

Ekleme

Bir x değerini ağaca eklemek için rastgele olacak şekilde bir p anahtar değeri üretilir. Ağaca ikili arama yapıldıktan sonra uygun düğümde yeni bir yaprak düğüm oluşturulur. Bu noktadan sonra p değeri düğümün atasından küçük olana kadar sağa ya da sola döndürme işlemi düğüm üzerinde uygulanır. Böylece hem ağaç yapısı hem de heap özelliği korunmuş olur.

Silme

Bir x değerini ağaçtan silmek için önce ikili arama yapılarak düğümün yeri tespit edilir. Eğer düğüm bir yaprak düğümse silinir. Eğer değilse tek çocuğu varsa aralarında döndürme işlemi uygulanarak düğüm yaprak düğüm haline getirilir. Eğer birden fazla çocuk varsa p değerine göre uygun olan çocuk seçilerek döndürme işlemi uygulanır. Bu işlemler düğüm yaprak düğüm oluncaya kadar devam eder.

Treap'in bölünmesi

Bir Treap istenilen bir noktadan iki ayrı treap'e bölünmek istendiğinde iki farklı durum ortaya çıkar. Bölünmenin istendiği değer treap'te mevcut değilse o değer en yüksek anahtar değeriyle treap'e eklenerek değerin kök düğüm olması sağlanır. Ardından düğümün sol çocuğu ve sağ çocuğu iki ayrı treap olarak kök düğümden bağlantıları koparılır. Değer Treap'in içinde ise değerin bulunmasına müteakip değer uygun döndürme işlemleriyle kök düğüm yapılır. Kök düğümün sol ya da sağ çocuğunun kök ile bağlantısı koparılarak ayrı bir treap olarak kullanılabilir. Bu işlem basitçe bir ekleme işlemi yapmakla ayni zamanda yani O(log n) zamanda tamamlanır.

Bölünen Treap'lerin birleşmesi

İki treap birleştirilirken on sart olarak bir treap'teki en büyük değerin öbür treap'teki en küçük değerden küçük olduğu kabul edilir. İlk treap'teki en büyük elemandan büyük diğer treap'teki en küçük elemandan küçük olacak şekilde bir x değeri ağaca en küçük anahtar değeriyle eklenir (sol çocuk ve sağ çocuk treap kök düğümleri olacak şekilde). Ekleme işleminden sonra bu düğüm yaprak düğüm olacağından kolayca silinir ve elimizde birleşmiş bir treap kalır. Bu işlemde bölünme işlemi gibi ekleme işlemi kadar yani O(log n) zamanda tamamlanır.

Eleman sayısı

İkili arama ağaçlarında kullanılan lokal bir değişkeni ekleme başarılı olduğunda arttırmak ve silme işlemi başarılı olduğunda azaltmak bölünme ve birleşme işlemleri sonrası treap için hatalı sonuç verir. Bu yaklaşımın yerine her düğümde sağ ve sol çocuk sayıları tutulmalı ve bu sayılar döndürme işlemleri sonunda güncellenmelidir. Bu yöntemle hatasız bir biçimde treap'in eleman sayısı bölünme ve birleşme işlemleri sonucu O(1) zamanda öğrenilebilir.

Kaynakça

Yararlı kaynaklar

• c# treap implementasyonu http://www.codeproject.com/Articles/8184/Treaps-in-C 29 Haziran 2013 tarihinde Wayback Machine sitesinde arşivlendi.
• java treap implementasyonu http://users.cis.fiu.edu/~weiss/dsaajava/code/DataStructures/Treap.java 6 Aralık 2012 tarihinde Wayback Machine sitesinde arşivlendi.
• c++ treap implementasyonu https://web.archive.org/web/20120203153554/http://www.cplusplus.happycodings.com/Data-Structures-and-Algorithm-Analysis-in-C++/code105.html
• python treap implementasyonu http://stromberg.dnsalias.org/~dstromberg/treap/ 5 Mayıs 2013 tarihinde Wayback Machine sitesinde arşivlendi.
• treap applet http://people.ksp.sk/~kuko/bak/index.html4 Mart 2015 tarihinde Wayback Machine sitesinde arşivlendi.
• treap dersi (İngilizce) http://www.youtube.com/watch?v=G5vUC5epTwc 29 Ocak 2021 tarihinde Wayback Machine sitesinde arşivlendi.