AVL ağacı - Turkipedia

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.^[1] 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 $n$ 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, Georgy Adelson-Velsky ve Evgenii Landis algoritmayı 1962'deki makaleleri "An algorithm for the organization of information".^[2]'de yayımladılar.

AVL ağaçı ve Kırmızı-siyah ağaç aynı operasyonları destekledikleri ve ikisinde de basit operasyonlar için ${\displaystyle {\text{O}}(\log n)}$ 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.^[3] 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 İkili ağaçda bir düğümün(node) Dengeleme Faktörü X iki çocuk alt ağaçlarının uzunluk farkı olarak tanımlanır.

{\text{BF}}(X):={\text{Uzunluk}}({\text{SağAltAğaç}}(X))-{\text{Uzunluk}}({\text{SolAltAğaç}}(X))

^[4]^:459

Bir ikili ağaçın AVL ağacı olarak tanımlanması için değişmez(Invariant)'ın

{\text{BF}}(X)\in {\{-1,0,1\}}

^[5] bütün düğmleri için geçerli olması gerekir.

Bir düğüm X için eğer ${\text{BF}}(X)<0$ ise o düğüm sol taraf ağırlıklı(left-heavy), ${\text{BF}}(X)>0$ ise sağ taraf ağırlıklı(right-heavy) ve ${\text{BF}}(X)=0$ 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.

$n$ adet düğüme sahip bir AVL ağacının uzunluğu $h$ (En fazla katman sayısı olarak sayılmaktadır), $\log _{2}(n+1)\leq h<\log _{\varphi }(n+2)+b$ aralığındadır^[4]^:460.
Burada $\varphi :={\tfrac {1+{\sqrt {5}}}{2}}\approx 1.618$ altın oran ve $b:={\frac {\log _{2}5}{2\log _{2}\varphi }}-2\approx \;-0.3277.$ Bunun sebebi $h$ uzunluğundaki bir AVL ağacı en az $F_{h+2}-1$ düğüm içermektedir. Burada $\{F_{n}\}_{n\in \mathbb {N} }$ , değeri başlangıç değerleri $F_{1}=F_{2}=1$ olan Fibonacci dizisi.

Kaynakça

^ Sedgewick, Robert (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 (Rusça). 146: 263-266. English translation 8 Mart 2021 tarihinde Wayback Machine sitesinde arşivlendi. by Myron J. Ricci in Soviet Mathematics - Doklady, 3.1259-1263, 1962.
^ Pfaff, Ben (June 2004). "Performance Analysis of BSTs in System Software" (PDF). Stanford University. 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 0-201-89685-0.
^ Rajinikanth. "AVL Tree : Data Structures". btechsmartclass.com. 27 Ekim 2018 tarihinde kaynağından arşivlendi. Erişim tarihi: 9 Mart 2018.

İlgili Araştırma Makaleleri

Laplasyen $\text{[math]}$ , skaler bir $\text{[math]}$ alanının gradyanı alınarak elde edilen vektörün diverjansıdır. Fizikteki birçok diferansiyel denklem laplasyen içerir.

RSA, güvenliği tam sayıları çarpanlarına ayırmanın algoritmik zorluğuna dayanan bir tür açık anahtarlı şifreleme yöntemidir. 1978’de Ron Rivest, Adi Shamir ve Leonard Adleman tarafından bulunmuştur. Bir RSA kullanıcısı iki büyük asal sayının çarpımını üretir ve seçtiği diğer bir değerle birlikte ortak anahtar olarak ilan eder. Seçilen asal çarpanları ise saklar. Ortak anahtarı kullanan biri herhangi bir mesajı şifreleyebilir, ancak şu anki yöntemlerle eğer ortak anahtar yeterince büyükse sadece asal çarpanları bilen kişi bu mesajı çözebilir. RSA şifrelemeyi kırmanın çarpanlara ayırma problemini kırmak kadar zor olup olmadığı hala kesinleşmemiş bir problemdir.

<span class="mw-page-title-main">Totient</span>

Totient sayılar teorisinde, bir tam sayının o sayıdan daha küçük ve o sayı ile aralarında asal olan sayma sayı sayısını belirten fonksiyondur. Genellikle Euler Totient ya da Euler'in Totienti olarak adlandırılan Totient, İsviçreli matematikçi Leonhard Euler tarafından yaratılmıştır. Totient fonksiyonu, Yunan harflerinden $\text{[math]}$ ile simgelendiği için Fi fonksiyonu olarak da anılabilir.

<span class="mw-page-title-main">Küresel koordinat sistemi</span>

Küresel koordinat sistemi, üç boyutlu uzayda nokta belirtmenin bir yoludur.

Normal dağılım, aynı zamanda Gauss dağılımı veya Gauss tipi dağılım olarak isimlendirilen, birçok alanda pratik uygulaması olan, çok önemli bir sürekli olasılık dağılım ailesidir.

Matematikte karmaşık sayı, bir gerçel bir de sanal kısımdan oluşan bir nesnedir. a ve b sayıları gerçek olursa karmaşık sayılar şu biçimde gösterilirler:

\text{[math]}

Elektriksel güç, elektrik enerjisinde elektrik devresi tarafından taşınan güç olarak tanımlanır. Gücün SI birimi watt'tır. Elektrikli cihazların birim zamanda harcadığı enerji miktarı olarak da bilinir. 1 saniyede 1 joule enerji harcayan elektrikli alet 1 watt gücündedir.

Merkezi limit teoremi büyük bir sayıda olan bağımsız ve aynı dağılım gösteren rassal değişkenlerin aritmetik ortalamasının, yaklaşık olarak normal dağılım göstereceğini ifade eden bir teoremdir. Matematiksel bir ifadeyle, bir merkezi limit teoremi olasılık kuramı içinde bulunan bir zayıf yakınsama sonucu setidir. Bunların hepsi, birçok bağımsız aynı dağılım gösteren rassal değişkenlerin herhangi bir toplam değerinin limitte belirli bir "çekim gücü gösteren dağılıma" göre dağılım gösterme eğiliminde olduğu gerçeğini önerir.

Olasılık kuramı ve istatistik bilim kollarında, zeta dağılımı bir ayrık olasılık dağılımıdır. Eğer X s parametresi ile zeta dağılımı gösteren bir bir rassal değişken ise, Xin k tam sayısı değerini almasının olasılığı şu olasılık kütle fonksiyonu ile belirtilir:

\text{[math]}

Olasılık kuramı içinde herhangi bir rassal değişken için karakteristik fonksiyon, bu değişkenin olasılık dağılımını tüm olarak tanımlar. Herhangi bir rassal değişken X için, gerçel doğru üzerinde, bu fonksiyonu tanımlayan formül şöyle yazılır:

\text{[math]}

Matematikte Laplace denklemi, özellikleri ilk defa Pierre-Simon Laplace tarafından çalışılmış bir kısmi diferansiyel denklemdir. Laplace denkleminin çözümleri, elektromanyetizma, astronomi ve akışkanlar dinamiği gibi birçok bilim alanında önemlidir çünkü çözümler bilhassa elektrik ve yerçekim potansiyeli ile akışkan potansiyelinin davranışını açıklar. Laplace denkleminin çözümlerinin genel teorisi aynı zamanda potansiyel teorisi olarak da bilinmektedir.

Hiperişlem, matematik'te aritmetik işlemlerin sonsuz dizisidir. Ardılın birli işlemi, ardından toplama, çarpma ve üs almanın iki işlemiyle devam eden ve ardından ikili işlemlerin ötesine geçerek serilerle ilerleyen bir işlemdir. Üstelden sonraki işlemler için bu dizinin n. elemanı Reuben Goodstein tarafından adlandırıldı. n Yunan önekinden sonra -syon son eki kullanılarak elde edilir ve Knuth yukarı ok gösterimindeki n-2 okları kullanılarak yazılabilir. Her hiperişlem, önceki terimlerin yinelemesi olarak tanımlanır. Ackermann işlevi, Knuth yukarı ok gösterimini kullanarak şöyle yinelenebilir:

\text{[math]}

Matematikte, küresel harmonikler Laplace denkleminin çözüm kümesinin açısal kısmıdır. Küresel koordinatların bir sistemi içinde küre yüzeyinde tanımlanır, Fourier serisi ise çember üzerinde tanımlanır. Laplace'ın küresel harmonikleri $\text{[math]}$ Pierre Simon de Laplace tarafından ilk 1782 yılında tanıtılan bir ortogonal sistemin küresel harmonik formlarının özel bir kümesidir. Küresel harmoniklerden birkaçının kökleri sağda gösterimlenmiştir. Küresel harmonikler pek çok yerde teorik önem taşımaktadır ve özellikle atomik yörünge elektron konfigürasyonları, yerçekimi alanları, geoitleri ve gezegen ve yıldızların manyetik alanlarının temsili ve kozmik mikrodalga arka plan radyasyonu karakterizasyonu hesaplanmasında kullanılan pratik uygulamaları vardır. Küresel harmonikler 3D Bilgisayar grafiklerinde, dolaylı aydınlatma ve 3D şekillerin tanınması gibi konularda geniş bir yelpazede özel bir rol oynamaktadır.

Matematikte, uzunluğu 1 olan ve uzayda bir norma sahip olan vektöre birim vektör denir. Birim vektör genellikle ‘û‘ gibi şapkalı ve küçük harflerle ifade edilir. Normalize vektör veya versor olmayan bir sıfır vektörü u ile eş yönlü olan birim vektörü u

\text{[math]}

Geometrik optik veya ışın optiği, ışık yayılmasını ışınlarla açıklar. Geometrik optikte ışın bir soyutlama ya da enstrumandır; ışığın belirli şartlarda yayıldığı yola yaklaşmada kullanışlıdır.

Çarpım fonksiyonu, sayılar teorisinde bir f(n) aritmetik fonksiyonudur. Bu fonksiyon, tanım kümesindeki her x ve y çifti için çarpma işlemini koruyan fonksiyondur.

\text{[math]}

Temel grup, Henri Poincaré'in 1895'te yayınladığı "Analysis Situs" adlı makalesinde tanımlanmıştır. Kavram, Bernhard Riemann, Poincaré ve Felix Klein'ın çalışmalarıyla Riemann yüzeyleri teorisinden ortaya çıkmıştır. Karmaşık değerli fonksiyonların monodromik özelliklerini açıkladığı gibi kapalı yüzeylerin tam bir topolojik sınıflandırılmasını sağlar.

Hacim integrali çok değişkenli kalkülüsteki çokkatlı integralin 3 boyutlu durumudur. Hacim integrali fizikte önemli bir yere sahiptir. Özellikle yoğunlukların hesabı için kullanılır.

Geometride, Theodorus Sarmalı, uç uca yerleştirilmiş dik üçgenlerden oluşan bir spiraldir. Adını, Cyreneli Theodorus'tan almıştır.

Matematikte, özellikle kategori teorisi ve homotopi teorisinde bir grupoid için grup kavramı birden fazla eşdeğer yolla açıklanabilir. Bir grupoid şu iki şekilde genelleştirilir:

İkili işlemin yerini alan bir kısmi fonksiyon ilişkisindeki grup;
Her morfizmanın ters çevrilebilir olduğu kategorideki grup.

Bu sayfa, bu Vikipedi makalesine dayanmaktadır.
Metin, CC BY-SA 4.0 lisansı altında mevcuttur; ek koşullar uygulanabilir.
Görseller, videolar ve sesler kendi lisansları altında mevcuttur.