Bilgisayar bilimlerinde bir AVL ağacı (İsmini icat eden Adelson-Velsky ve Landis'den alır) kendi kendini dengeleyen bir İkili arama ağacıdır. Bu tip Veri yapılarının icat edilmiş ilk örneğidir. Bir AVL ağacında, iki çocuk alt ağacın uzunluk farklı en fazla bir olabilir; Eğer herhangi bir anda fark birden fazlaysa, dengeleme yapılarak bu özellik korunur. Arama, ekleme ve silme işlemlerinin hepsi hem ortalama hem de en kötü durumlarda O(log n) zaman sürer, burada harfi operasyon öncesindeki düğüm(node) adetidir. Ekleme ve çıkarma işlemleri ağacın bir veya daha fazla ağaç rotasyonları ile dengelenmesini gerektirebilir.
AVL ağacı ismini iki Sovyet mucitlerinden alır, ve algoritmayı 1962'deki makaleleri "An algorithm for the organization of information".'de yayımladılar.
AVL ağaçı ve Kırmızı-siyah ağaç aynı operasyonları destekledikleri ve ikisinde de basit operasyonlar için zamanı sürdüğü için sıklıkla kıyaslanırlar. Arama işleminin fazla olduğu uygulamalar için AVL ağaçları daha katı şekilde dengelendiği için Kırmızı-siyah ağaçtan daha hızlıdır. Kırmızı siyah ağaçlara benzer şekilde AVL ağaçları uzunluğa göre dengelenmiştir.
Tanım
Dengeleme Faktörü (Balance factor)
Bir bir düğümün(node) Dengeleme Faktörü X iki çocuk alt ağaçlarının uzunluk farkı olarak tanımlanır.
- :459
Bir ikili ağaçın AVL ağacı olarak tanımlanması için 'ın
- bütün düğmleri için geçerli olması gerekir.
Bir düğüm X için eğer ise o düğüm sol taraf ağırlıklı(left-heavy), ise sağ taraf ağırlıklı(right-heavy) ve ise dengeli denir.
Özellikleri
Denge faktörlerini güncel tutmak için daha önceki denge faktörünü ve uzunluktaki değişimi bilmek yeterlidir, yani mutlak uzunluğu bilmek gerekli değildir. AVL denge bilgisini alışıldık şekilde saklamak için, her düğüm başına iki bit yeterlidir. Ancak, sonraki araştırmalarda bir bitin de yeterli olduğu görülmüştür.
adet düğüme sahip bir AVL ağacının uzunluğu (En fazla katman sayısı olarak sayılmaktadır), aralığındadır:460.
Burada altın oran ve Bunun sebebi uzunluğundaki bir AVL ağacı en az düğüm içermektedir. Burada , değeri başlangıç değerleri olan Fibonacci dizisi.
Kaynakça
- ^ (1983). "Balanced Trees". Algorithms. Addison-Wesley. s. 199. ISBN .
- ^ Adelson-Velsky, Georgy; Landis, Evgenii (1962). "An algorithm for the organization of information". Proceedings of the USSR Academy of Sciences (Rusça). 146: 263-266. English translation 8 Mart 2021 tarihinde Wayback Machine sitesinde . by Myron J. Ricci in Soviet Mathematics - Doklady, 3.1259-1263, 1962.
- ^ Pfaff, Ben (June 2004). (PDF). . 15 Eylül 2004 tarihinde kaynağından (PDF) arşivlendi.
- ^ a b Knuth, Donald E. (2000). Sorting and searching (2. ed., 6. printing, newly updated and rev. bas.). Boston [u.a.]: Addison-Wesley. ISBN .
- ^ Rajinikanth. . btechsmartclass.com. 27 Ekim 2018 tarihinde kaynağından arşivlendi. Erişim tarihi: 9 Mart 2018.
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Bilgisayar bilimlerinde bir AVL agaci Ismini icat eden Adelson Velsky ve Landis den alir kendi kendini dengeleyen bir Ikili arama agacidir Bu tip Veri yapilarinin icat edilmis ilk ornegidir Bir AVL agacinda iki cocuk alt agacin uzunluk farkli en fazla bir olabilir Eger herhangi bir anda fark birden fazlaysa dengeleme yapilarak bu ozellik korunur Arama ekleme ve silme islemlerinin hepsi hem ortalama hem de en kotu durumlarda O log n zaman surer burada n displaystyle n harfi operasyon oncesindeki dugum node adetidir Ekleme ve cikarma islemleri agacin bir veya daha fazla agac rotasyonlari ile dengelenmesini gerektirebilir Birkac elemanin AVL agacina eklenmesini gosteren animasyon sol sag sag sol ve sol sag rotasyonlari gostermektedir Gorsel 1 Dengeleme faktorleriyle bir AVL agaci yesil AVL agaci ismini iki Sovyet mucitlerinden alir ve algoritmayi 1962 deki makaleleri An algorithm for the organization of information de yayimladilar AVL agaci ve Kirmizi siyah agac ayni operasyonlari destekledikleri ve ikisinde de basit operasyonlar icin O log n displaystyle displaystyle text O log n zamani surdugu icin siklikla kiyaslanirlar Arama isleminin fazla oldugu uygulamalar icin AVL agaclari daha kati sekilde dengelendigi icin Kirmizi siyah agactan daha hizlidir Kirmizi siyah agaclara benzer sekilde AVL agaclari uzunluga gore dengelenmistir TanimDengeleme Faktoru Balance factor Bir bir dugumun node Dengeleme Faktoru X iki cocuk alt agaclarinin uzunluk farki olarak tanimlanir BF X Uzunluk SagAltAgac X Uzunluk SolAltAgac X displaystyle text BF X text Uzunluk text SagAltAgac X text Uzunluk text SolAltAgac X 459 Bir ikili agacin AVL agaci olarak tanimlanmasi icin in BF X 1 0 1 displaystyle text BF X in 1 0 1 butun dugmleri icin gecerli olmasi gerekir Bir dugum X icin eger BF X lt 0 displaystyle text BF X lt 0 ise o dugum sol taraf agirlikli left heavy BF X gt 0 displaystyle text BF X gt 0 ise sag taraf agirlikli right heavy ve BF X 0 displaystyle text BF X 0 ise dengeli denir Ozellikleri Denge faktorlerini guncel tutmak icin daha onceki denge faktorunu ve uzunluktaki degisimi bilmek yeterlidir yani mutlak uzunlugu bilmek gerekli degildir AVL denge bilgisini alisildik sekilde saklamak icin her dugum basina iki bit yeterlidir Ancak sonraki arastirmalarda bir bitin de yeterli oldugu gorulmustur n displaystyle n adet dugume sahip bir AVL agacinin uzunlugu h displaystyle h En fazla katman sayisi olarak sayilmaktadir log2 n 1 h lt logf n 2 b displaystyle log 2 n 1 leq h lt log varphi n 2 b araligindadir 460 Burada f 1 52 1 618 displaystyle varphi tfrac 1 sqrt 5 2 approx 1 618 altin oran ve b log2 52log2 f 2 0 3277 displaystyle b frac log 2 5 2 log 2 varphi 2 approx 0 3277 Bunun sebebi h displaystyle h uzunlugundaki bir AVL agaci en az Fh 2 1 displaystyle F h 2 1 dugum icermektedir Burada Fn n N displaystyle F n n in mathbb N degeri baslangic degerleri F1 F2 1 displaystyle F 1 F 2 1 olan Fibonacci dizisi Kaynakca 1983 Balanced Trees Algorithms Addison Wesley s 199 ISBN 0 201 06672 6 Adelson Velsky Georgy Landis Evgenii 1962 An algorithm for the organization of information Proceedings of the USSR Academy of Sciences Rusca 146 263 266 English translation 8 Mart 2021 tarihinde Wayback Machine sitesinde by Myron J Ricci in Soviet Mathematics Doklady 3 1259 1263 1962 Pfaff Ben June 2004 PDF 15 Eylul 2004 tarihinde kaynagindan PDF arsivlendi a b Knuth Donald E 2000 Sorting and searching 2 ed 6 printing newly updated and rev bas Boston u a Addison Wesley ISBN 0 201 89685 0 Rajinikanth btechsmartclass com 27 Ekim 2018 tarihinde kaynagindan arsivlendi Erisim tarihi 9 Mart 2018