Vikipedi
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 olusturulmus 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 önerilmistir.[1] 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[2] 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 sirayla eklenmis bir ağaçta rastgele secilen bir elemana uzaklik O(log n)'dir. Kok dugumden secilen herhangi bir baska elemana gidilirken su an bulundugumuz elemanin altinda n elaman oldugunu varsayalim. Su anki elamanin bizim aradigimiz elaman olma olasiligi n elaman rastgele bicimde dagildigindan 1/n'dir.Sol alt agac p-1 eleman barindirdigindan ayni mantikla gitmek istegimiz elemanin orada olma olasiligi p-1/n'dir. Ayni sekilde sag alt agac n-p dugum barindirdigindan olasilik n-p/n'dir. Bir adimda gelinecek alt agac buyuklugunun beklenen degeri (p-1)·(p-1)/n + (n-p)·(n-p)/n + (1·1/n) olarak ortaya cikar. P'nin butun degerleri 1 ile n arasinda esit olasilikla dagildigindan her adimda ziyaret edilecek agac buyuklugude ayni sekilde dagilir. Yukaridaki ifadenin 1'den n'e kadar degerlerinin n ile bolumu: (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) seklinde ortaya cikar.[ http://www.cs.cornell.edu/Courses/cs312/2003sp/lectures/lec26.html] treap lecture Bu ifadeninde gosterdigi gibi, O(log 3/2n) adimda istenilen noktaya ulasilmasi beklenir. Bu sebepten ekleme, silme ya da arama islemlerinin O(log n) zamanda yapilabilir.
=