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.  Aragon, Cecilia R.; Seidel, Raimund (1989), "Randomized Search Trees", Proc. 30th Symp. Foundations of Computer Science (FOCS 1989), Washington, D.C.: IEEE Computer Society Press, pp. 540–545, doi:10.1109/SFCS.1989.63531, ISBN 0-8186-1982-1  Seidel, Raimund; Aragon, Cecilia R. (1996), "Randomized Search Trees", Algorithmica 16 (4/5): 464–497, doi:10.1007/s004539900061 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.[ http://www.cs.cornell.edu/Courses/cs312/2003sp/lectures/lec26.html ] treap lecture
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 
java treap implementasyonu http://users.cis.fiu.edu/~weiss/dsaajava/code/DataStructures/Treap.java 
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/ 
treap applet http://people.ksp.sk/~kuko/bak/index.html
treap dersi (İngilizce) http://www.youtube.com/watch?v=G5vUC5epTwc 

Kategori:Bilgisayar verisi
Kategori:Veri yönetimi
Kategori:Programlama
Kategori:Rastlantısallık