Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Kırmızı-siyah ağaç bilgisayar biliminde bir çeşit veri yapısıdır. Orijinali ilk olarak 1972 yılında yapıyı "simetrik ikili " olarak adlandıran tarafından bulunmuştur. Bugünkü ismini 1978 yılında ve 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 türüdür.
Özellikleri
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:
- Her düğüm ya kırmızıdır ya da siyah.
- 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.)
- Bütün yapraklar siyahtır.
- Kırmızı düğümlerin her iki çocuğu da siyahtır.
- Bir düğümden atalarına doğru giden tüm 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
- Bilgisayar Kavramları : Kırmızı Siyah Ağaçları 4 Nisan 2012 tarihinde Wayback Machine sitesinde .
- Mathworld: Red-Black Tree 30 Nisan 2008 tarihinde Wayback Machine sitesinde .
- San Diego State University: CS 660: Red-Black tree notes 9 Mayıs 2008 tarihinde Wayback Machine sitesinde ., by Roger Whitney
- , , , and . , Second Edition. MIT Press and McGraw-Hill, 2001. . Chapter 13: Red-Black Trees, pp. 273–301.
- Pfaff, Ben (Haziran 2004). "Performance Analysis of BSTs in System Software" (PDF). . 10 Ekim 2012 tarihinde kaynağından (PDF).
- Okasaki, Chris. . 7 Mart 2012 tarihinde kaynağından (PS) arşivlendi.
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
Kirmizi siyah agac bilgisayar biliminde bir cesit veri yapisidir Orijinali ilk olarak 1972 yilinda yapiyi simetrik ikili olarak adlandiran tarafindan bulunmustur Bugunku ismini 1978 yilinda ve tarafindan yayimlanan bir makaleyle almistir Karmasik ancak calisma suresi en kotu durumda bile iyi ve pratikte verimlidir O log n n agactaki eleman sayisini gosterir zamanda arama ekleme ve cikarma islemleri yapabilir Teknik TerimlerBir kirmizi siyah agac bilgisayar biliminde karsilastirilabilir veri parcalarini sayilar gibi organize etmek icin kullanilabilen ozel bir turudur OzellikleriKirmizi siyah agac ornegi Kirmizi siyah agaclar her dugumun degeri kirmizi veya siyah olabilen bir renk niteligine sahip oldugu Ikili arama agacidir Ikili arama agaclarinin sahip olduklari gereksinimlerin yaninda su asagidaki ek ozelliklere de sahiptirler Her dugum ya kirmizidir ya da siyah Kok dugum siyahtir Bu kural bazi tanimlarda kullanilirken bazilarinda kullanilmaz Kok dugum her zaman kirmizidan siyaha degistirilebilecegi ancak tersi gecerli olmadigi icin analizlerde cok az etkisi bulunur Butun yapraklar siyahtir Kirmizi dugumlerin her iki cocugu da siyahtir Bir dugumden atalarina dogru giden tum ayni sayida siyah dugum icerir Bu kisitlar kirmizi siyah agaclarin onemli bir ozelligini zorlar kokten herhangi bir yaprak dugume giden en uzun yol herhangi baska bir yapraga giden en kisa yolun iki katidan fazla olamaz Bunun sonucu olarak agac kabaca dengeli olur Ekleme silme ve degerleri bulma operasyonlarinin en kotu durum zamanlari agacin boyuyla orantili oldugundan boya getirilen bu teorik ust sinir kirmizi siyah agaclarin en kotu durumda bile verimli islemler yapmalarini saglar Bu durum ikili arama agaclarinda gecerli degildir Yukarida sayilan ozelliklerin kirmizi siyah agaclara bu onemli ozelligi kazandirmasinin nedenini gormek icin 4 ozellikten dolayi herhangi bir yolda iki ardisik kirmizi dugum olamayacagini gormek yeterlidir En kisa yol sadece siyah dugumlerden olusan bir yoldur ve en uzun muhtemel yol da kirmizi ve siyah dugumlerin sirasiyla geldigi yoldur 5 ozellikten dolayi tum uzun kokten yapraklara kadar olan yollar ayni sayida siyah dugum icerdiginden herhangi bir yolun bir baska yoldan iki katindan daha uzun olamayacagi aciktir KaynakcaBilgisayar Kavramlari Kirmizi Siyah Agaclari 4 Nisan 2012 tarihinde Wayback Machine sitesinde Mathworld Red Black Tree 30 Nisan 2008 tarihinde Wayback Machine sitesinde San Diego State University CS 660 Red Black tree notes 9 Mayis 2008 tarihinde Wayback Machine sitesinde by Roger Whitney and Second Edition MIT Press and McGraw Hill 2001 ISBN 0 262 03293 7 Chapter 13 Red Black Trees pp 273 301 Pfaff Ben Haziran 2004 Performance Analysis of BSTs in System Software PDF 10 Ekim 2012 tarihinde kaynagindan PDF Okasaki Chris 7 Mart 2012 tarihinde kaynagindan PS arsivlendi