İçeriğe atla

Kırmızı-siyah ağaç

Kırmızı-siyah ağaç bilgisayar biliminde bir çeşit kendini-dengeleyen ikili arama ağacı veri yapısıdır. Orijinali ilk olarak 1972 yılında yapıyı "simetrik ikili B-ağaçları" olarak adlandıran Rudolf Bayer tarafından bulunmuştur. Bugünkü ismini 1978 yılında Leo J. Guibas ve Robert Sedgewick tarafından yayımlanan bir makaleyle almıştır. Karmaşık ancak çalışma süresi en kötü durumda bile iyi ve pratikte verimlidir: O(log n) (n ağaçtaki eleman sayısını gösterir) zamanda arama, ekleme ve çıkarma işlemleri yapabilir.

Teknik Terimler

Bir kırmızı-siyah ağaç, bilgisayar biliminde karşılaştırılabilir veri parçalarını (sayılar gibi) organize etmek için kullanılabilen özel bir ikili ağaç türüdür.

Özellikleri

İkili ağaç şekli. Siyah kök düğüm iki kırmızı çocuğa ve dört siyah toruna sahiptir. Torunların çocuk düğümleri ya siyah "boş" göstergelerdir ya da siyah "boş" göstergelere sahip kırmızı düğümlerdir.
Kırmızı-siyah ağaç örneği

Kırmızı-siyah ağaçlar, her düğümün, değeri kırmızı veya siyah olabilen bir renk niteliğine sahip olduğu İkili arama ağacıdır. İkili arama ağaçlarının sahip oldukları gereksinimlerin yanında, şu aşağıdaki ek özelliklere de sahiptirler:

  1. Her düğüm ya kırmızıdır ya da siyah.
  2. Kök düğüm siyahtır. (Bu kural bazı tanımlarda kullanılırken bazılarında kullanılmaz. Kök düğüm her zaman kırmızıdan siyaha değiştirilebileceği, ancak tersi geçerli olmadığı için analizlerde çok az etkisi bulunur.)
  3. Bütün yapraklar siyahtır.
  4. Kırmızı düğümlerin her iki çocuğu da siyahtır.
  5. Bir düğümden atalarına doğru giden tüm basit yollar aynı sayıda siyah düğüm içerir.

Bu kısıtlar kırmızı-siyah ağaçların önemli bir özelliğini zorlar: kökten herhangi bir yaprak düğüme giden en uzun yol, herhangi başka bir yaprağa giden en kısa yolun iki katıdan fazla olamaz. Bunun sonucu olarak ağaç kabaca dengeli olur. Ekleme, silme ve değerleri bulma operasyonlarının en-kötü durum zamanları ağacın boyuyla orantılı olduğundan, boya getirilen bu teorik üst sınır, kırmızı-siyah ağaçların en kötü durumda bile verimli işlemler yapmalarını sağlar. Bu durum ikili arama ağaçlarında geçerli değildir.

Yukarıda sayılan özelliklerin kırmızı-siyah ağaçlara bu önemli özelliği kazandırmasının nedenini görmek için, 4. özellikten dolayı herhangi bir yolda iki ardışık kırmızı düğüm olamayacağını görmek yeterlidir. En kısa yol, sadece siyah düğümlerden oluşan bir yoldur ve en uzun muhtemel yol da kırmızı ve siyah düğümlerin sırasıyla geldiği yoldur. 5. özellikten dolayı tüm uzun (kökten, yapraklara kadar olan) yollar aynı sayıda siyah düğüm içerdiğinden, herhangi bir yolun, bir başka yoldan iki katından daha uzun olamayacağı açıktır.

Kaynakça

İlgili Araştırma Makaleleri

<span class="mw-page-title-main">Ağaç</span> meyve verebilen, gövdesi odun veya kereste olmaya elverişli bulunan ve uzun yıllar yaşayabilen bitki

Ağaç, botanikte çoğu türünde dalları ve yaprakları destekleyen uzun bir sürgüne ya da gövdeye sahip çok yıllık bir bitkidir. Ağaç tanımı, bazı kullanımlarda sadece ikincil büyüme gösteren odunsu bitkileri, kereste olarak kullanılabilen bitkileri ya da belirli bir yüksekliğin üzerindeki bitkileri kapsayacak şekilde daha dar olabilir. Daha geniş tanımlarda ise uzun palmiyeler, eğrelti ağaçları, muz ağaçları ve bambular da birer ağaç olarak kabul edilir. Ağaçlar taksonomik bir grup değildir ancak güneş ışığı için rekabet etmek adına diğer bitkilerden daha fazla yükseğe çıkmanın bir yolu olarak birbirinden bağımsız şekilde evrimleşip gövde ve dalları olan çeşitli bitki türlerini içermektedir. Ağaçlar uzun ömürlü olma eğilimindedir ve bazıları birkaç bin yıl yaşar. Ağaçlar 370 milyon yıldır dünya üzerindeki varlığını sürdürmektedir. Dünyada yaklaşık üç trilyon olgunluğa erişmiş ağacın olduğu tahmin edilmektedir.

<span class="mw-page-title-main">Çilek</span> Meyve

Çilek (Fragaria), gülgiller (Rosaceae) familyası içinde yer alan bir bitki cinsi ve bu cins içinde yer alan türlerin meyvelerinin ortak adıdır.

<span class="mw-page-title-main">Kokar ağaç</span>

Kokar ağaç,Çin Cennet Ağacı, Simaroubaceae familyasından Mayıs-Haziran ayları arasında yeşilimsi sarı renkli çiçekler açan, kötü kokulu bir ağaç türü. Vatanı Uzakdoğu'dur. Buradan Avrupa ve Anadolu'ya yayılmıştır. Zararlı yabani bir ot, istilacı bir tür olarak kabul edilir. Ağaç hızla büyür ve 25 yılda 15 metre (50 ft) yüksekliğe ulaşabilir. Tür nadiren 50 yıldan fazla yaşarken, bazı örnekler 100 yaşını aşar. Ağaç, ipek üretiminde kullanılan bir güve olan ailanthus ipek güvesi için bir konak bitki olarak hem Çin'de hem de yurtdışında yaygın olarak yetiştirilmiştir. Menzilinin uzağında, uzun zaman önce dikilmiş bir sokak ağacı olarak bulunduğu şehirlerin bozulmuş bölgelerinde en yaygın şekilde büyür.

<span class="mw-page-title-main">Zeytin</span> Zeytin familyasından bir bitki türü

"Avrupa zeytini" anlamında Olea europaea botanik adlı zeytin, zeytingiller Oleaceae familyasından meyvesi yenen ve geleneksel olarak Akdeniz iklimine özgü bir ağaç türüdür. Tür, tüm Akdeniz ülkelerinin yanı sıra Güney Amerika, Güney Afrika, Çin, Avustralya, Yeni Zelanda, Meksika ve Amerika Birleşik Devletleri'nde yetiştirilir. Olea europaea, Olea cinsi için tip türüdür.

<span class="mw-page-title-main">Mabet ağacı</span> bitki türü

Ginkgo biloba (Çince ve Japonca 銀杏), günümüzde varlığını sürdüren hiçbir yakın türü veya benzeri bulunmayan, tamamıyla kendine özgü bir ağaçtır. Botanikçilerce, bitkiler (Plantea) alemi içindeki ayrı bir bölümde (Ginkgophyta) değerlendirilir. Bu bölümün içinde tek bir sınıf (Ginkgoopsida), sınıfın içinde tek bir takım (Ginkgoales), takımın içinde tek bir familya (Ginkgoaceae), familyanın içinde de tek bir cins olarak Ginkgo ve bu cinste de tek tür olarak Ginkgo biloba bulunmaktadır. Geçmişte Spermatophyta veya Pinophyta bölümlerine yerleştirilmişse de bugün yukarıda belirtilen tanımların daha uygun olduğu sonucuna varılmıştır. Bilinen yaşayan fosil türlerinin en iyi örneklerinden biridir. Ginkgo biloba, açık tohumlular (gymnospermae) olarak anılan, başka bir deyişle tohumları bir meyve tarafından koruma altında olmayan bir ağaç türüdür.

Veri yapısı, bilgisayar ortamında verilerin etkin olarak saklanması ve işlenmesi için kullanılan yapı.

Biyolojide filogenetik çeşitli organizma grupları arasındaki evrimsel ilişkinin araştırmasıdır. Bu ilişkiler filogeni olarak adlandırılır. Filogenetik terimi Yunanca kökenlidir, "kabile, ırk" anlamına gelen file veya filon (φυλή/φῦλον) ve doğumla ilişkili anlamındaki genetikos (γενετικός) terimlerinden türetilmiştir. Organizmaların sınıflandırması ve adlandırması olan taksonomi, filogenetikten büyük miktarda etkilenmiştir ama yöntemsel ve mantıksal olarak farklıdır. Bu iki saha, "kladizm" veya "kladistik" olarak bilinen filogenetik sistematik bilim dalında örtüşürler. Filogenetik sistematikte taksonları birbirinden ayırt etmek için sadece filogenetik ağaçlar kullanılır. Evrimsel hayat ağacının araştırılması için filogenetik analiz yöntemleri vazgeçilmez hâle gelmiştir.

Yağcıbedir halıları, özellikle Balıkesir'in Sındırgı ve Bigadiç köylerinde, Yörükler tarafından dokunan ve önemli kültürel değere sahip motifleri olan bir halı türüdür.

<span class="mw-page-title-main">İkili arama ağacı</span>

İkili arama ağacı, verileri organize etmek için kullanılan bir çeşit ikili ağaçtır. İkili ağaçtan temel farkı, verilerin sıralanmış bir şekilde tutulmasıdır, bu sayede ikili arama algoritmasının kullanılmasına imkân verir.

<span class="mw-page-title-main">Avrupa kayını</span> Kayıngiller familyasından bir bitki türü

Avrupa kayını, kayıngiller (Fagaceae) familyası üyelerinden belirli mevsimlerde yaprak döken bir kayın türü.

<span class="mw-page-title-main">Gövde (botanik)</span> damarlı bir bitkinin yapısal ekseni

Gövde, bir vasküler bitkinin iki ana yapısal ekseninden biridir, diğeri ise kök'tür. Yaprakları, çiçekleri ve meyveleri destekler, ksilem ve floemde kökler ve sürgünler arasında su ve çözünmüş maddeleri taşır, besin maddelerini depolar ve yeni canlı doku üretir. Gövde normalde düğümlere ve ara düğümlere ayrılır:

Arama algoritmaları, bilgisayar biliminde seçili özelliklere göre istenilen bilgileri bulan algoritmalardır. Listeler, metinler ve şekiller üzerinde çalışırlar.

Treap ya da tree heap, 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.

<span class="mw-page-title-main">Merkle ağacı</span>

Kriptografi ve bilgisayar bilimlerinde, Hash ağacı ya da Merkle ağacında her yaprak düğümü veri blokunun özet değerini, her yaprak olmayan düğüm ise kendi alt düğümlerinin kriptografik özet değerlerini içerir. Merkle ağacı büyük veri yapılarının verimli ve güvenli bir şekilde doğrulanmasını sağlar. Merkle ağaçları, özet listeleri ve özet zincirlerinin genelleştirilmiş halidir. Aynı isimdeki Merkle İmza Algoritması, Merkle özet değeri ağacını kullanmaktadır.

Merkle imzası, anahtarlama ağaçları ve sayısal imza şemalarını birleştiren bir veri doğrulama yapısıdır. Özet değeri tabanlı kriptografidir ve Merkle ağacı da denen özet değeri ağacını kullanmaktadır. Verileri Lampart imza algoritması gibi tek kullanımlık şekilde imzalar. Ralph Merkle tarafından 1970 sonu itibarıyla geliştirilmiştir ve RSA, Dijital İmza Algoritması gibi geleneksel dijital imzalara alternatif olmuştur.

<span class="mw-page-title-main">AVL ağacı</span>

Bilgisayar bilimlerinde bir AVL ağacı 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.

Karar ağacı, bir kurum veya kuruluş tarafından tercihlerin, risklerin, kazançların ve hedeflerin anlaşılmasına yardımcı olan bir teknik türüdür. Aynı zamanda birçok önemli yatırım sahalarında uygulanabilen, birbiriyle bağlantılı şans olaylarıyla ilgili olarak çıkan çeşitli karar noktalarını incelemek için kullanılan bir karar destek aracıdır. Yalnızca koşullu kontrol ifadeleri içeren bir algoritmayı görüntülemenin bir yoludur.

Anaç, bitkinin bir parçasıdır, genellikle yeni yer üstü büyümesinin üretilebildiği bir yeraltı kısmıdır. Başka bir bitkinin tomurcuğunun aşılandığı, iyi gelişmiş bir kök sistemine sahip bir gövde olarak da tanımlanabilir. Bir köksap veya yeraltı sapına atıfta bulunabilir. Aşılamada, bir bitkiye, bazen sadece bir kütüğe, halihazırda kurulmuş, sağlıklı bir kök sistemine sahip olan, üzerine başka bir bitkiden bir kesme veya tomurcuk aşılanmış anlamına gelir. Üzüm asmaları ve diğer meyveler gibi bazı durumlarda, anaçlar için çelikler kullanılabilir, kökler onları dikmeden önce fidanlık koşullarında kurulur. Anaç üzerine aşılanan bitki kısmına genellikle kalem denir. Scion o özelliklere sahip bitkidir yayıcısı fotosentetik aktivite ve meyve veya dekoratif özellikleri dahil, yerden arzuluyor. Anaç, toprakla etkileşimi, köklerin ve gövdenin yeni bitkinin desteklenmesini sağlaması, gerekli toprak suyu ve minerallerini alması, ilgili zararlı ve hastalıklara karşı direnç göstermesi için seçilir. Birkaç hafta sonra iki parçanın dokuları birlikte büyüyecek ve sonunda tek bir bitki oluşturacaktır. Ürün her zaman genetik olarak farklı iki bitkinin bileşenlerini içermesine rağmen, birkaç yıl sonra aşı yerini tespit etmek zor olabilir.

<i>Cercis canadensis</i>

Cercis canadensis, Fabaceae familyasından gösterişli çiçeklere sahip bir çalı türü.

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

Hackenbush, matematikçi John Horton Conway tarafından icat edilen iki oyunculu bir oyundur. Birbirlerine ve bir "zemin" çizgisine uç noktaları ile bağlı renkli çubukların herhangi bir konfigürasyonunda oynanabilir.