İçeriğe atla

İkili arama ağacı

İ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.

9 elemanlı, yüksekliği 4 ve kökü 8 olan bir ikili arama ağacı

İkili arama ağaçlarında; her düğümün sağ çocuğu kendisinden büyük, sol çocuğu ise kendisinden küçüktür. Bu ağaçlarda çalışan arama algoritması önce kökten başlar, eğer aranan eleman kökten büyükse sağ çocuğa, kökten küçükse sol çocuğa ilerler. Böylece, eleman bulunana yapraklara kadar yinelemeli bir şekilde ilerleme sağlanır.

İşlemler

İkili arama ağacı üzerinde; arama, ekleme, silme işlemleri yapılabilir.

Arama

Kökten başlanarak arama işlemi yapılır. Eğer aranan eleman o anki düğümden büyükse sağa, küçükse sola ilerlenir. Bu algoritma bir döngü içinde ya da özyinelemeli şekilde uygulanabilir. Python kodu şu şekildedir:

def search_recursively(key, node):
    if node is None or node.key == key:
        return node
    if key < node.key:
        return search_recursively(key, node.left)
    # key > node.key
    return search_recursively(key, node.right)
def search_iteratively(key, node): 
    current_node = node
    while current_node is not None:
        if key == current_node.key:
            return current_node
        elif key < current_node.key:
            current_node = current_node.left
        else: # key > current_node.key:
            current_node = current_node.right
    return current_node

Ekleme

Eleman ekleme işlemi her zaman yapraklara ya da tek çocuğu olan düğümlere yapılır. Bunun için öncelikle eklenecek elemanın konumu bulunmalıdır, konum bulma işlemi arama kısmında olduğu gibi büyükse sağa, küçükse sola ilerle şeklinde yapılır. Bu algoritma da bir döngü içinde ya da özyinelemeli şekilde uygulanabilir. C++ kodu şu şekildedir:

Node* insert(Node*& root, int key, int value) {
  if (!root) 
    root = new Node(key, value);
  else if (key < root->key)
    root->left = insert(root->left, key, value);
  else  // key >= root->key
    root->right = insert(root->right, key, value);
  return root;

Silme

İki çocuğu olan bir düğümün (D) silinmesi. D, E ile yer değiştirilip siliniyor.

Silme işlemi üç başlık altında incelenebilir. Eğer,

  • Silinecek düğümün çocuğu yoksa: basitçe düğüm silinir.
  • Silinecek düğümün tek çocuğu varsa: düğüm silinir ve tek çocuk silinen düğümün yerine taşınır.
  • Silinecek düğümün iki çocuğu varsa: silinecek düğüme D diyelim, D'yi silmeden önce D'den büyük en küçük eleman bulunur (inorder successor) buna da E diyelim. E ile D yer değiştirilir ve ardından D silinir.

Bir elemandan büyük en küçük eleman, o elemanın sağ alt ağacının en solundaki elemandır ve bunu bulmak için ekstra metot yazmak gerekir. Bu yüzden, silme algoritması ekleme ve arama algoritmalarına göre daha uzundur. Python kodu şu şekildedir:

def find_min(self):   # Gets minimum node in a subtree
    current_node = self
    while current_node.left_child:
        current_node = current_node.left_child
    return current_node

def replace_node_in_parent(self, new_value=None):
    if self.parent:
        if self == self.parent.left_child:
            self.parent.left_child = new_value
        else:
            self.parent.right_child = new_value
    if new_value:
        new_value.parent = self.parent

def binary_tree_delete(self, key):
    if key < self.key:
        self.left_child.binary_tree_delete(key)
    elif key > self.key:
        self.right_child.binary_tree_delete(key)
    else: # delete the key here
        if self.left_child and self.right_child: # if both children are present
            successor = self.right_child.find_min()
            self.key = successor.key
            successor.binary_tree_delete(successor.key)
        elif self.left_child:   # if the node has only a *left* child
            self.replace_node_in_parent(self.left_child)
        elif self.right_child:  # if the node has only a *right* child
            self.replace_node_in_parent(self.right_child)
        else: # this node has no children
            self.replace_node_in_parent(None)

Dengeli ikili arama ağaçları

Bir ağaçtaki tüm düğümlerin sağ alt ağaçları ve sol alt ağaçları arasındaki yükseklik farkı en fazla 1 ise, o ağaç dengeli olarak tanımlanır. Ağaçların dengeli olması onların yüksekliğini azaltarak ağaç üzerinde çalışan algoritmaların performansını arttırır. Örneğin boş bir ikili arama ağacına 1, 2, 3, 4, 5, 6, 7 elemanlarını sırayla eklediğimizi düşünelim. Bu durumda elemanlar hep sağ tarafa ekleneceği için ağaç esasen bir bağlı listeye dönüşür. Halbuki, aynı elemanlar, yüksekliği 3 olan bir ağaca da yerleştirilebilirlerdi. Bu durum, dengeli ikili arama ağaçlarının icadına yol açmıştır. AVL ağacı, 2-3-4 ağacı ve kırmızı-siyah ağaçlar dengeli ağaçlara örnektir.

İlgili Araştırma Makaleleri

<span class="mw-page-title-main">JavaScript</span> programlama dili

JavaScript, HTML ve CSS ile birlikte World Wide Web'in temel teknolojilerinden biri olan programlama dilidir. Web sitelerinin %97'sinden fazlası, web sayfası hareketleri için istemci tarafında JavaScript kullanırlar ve kullanılan kodlar genellikle üçüncü taraf kitaplıkları içerir. Tüm büyük web tarayıcılarında, kaynak kodunu kullanıcıların cihazlarında yürütebilmek için özel bir JavaScript motoru bulunur.

<span class="mw-page-title-main">Asal sayı</span> sadece iki pozitif tam sayı böleni olan doğal sayılardır

Bir asal sayı, yalnızca 1'den büyük olup kendisinden küçük iki doğal sayının çarpımı olarak ifade edilemeyen bir doğal sayıdır. 1'den büyük ve asal olmayan doğal sayılara bileşik sayı adı verilir. Örneğin, 5 bir asal sayıdır çünkü onu bir çarpım olarak ifade etmenin mümkün olan yolları, 1 × 5 veya 5 × 1, yalnızca 5 sayısını içermektedir. Ancak, 4 bir bileşik sayıdır çünkü bu, her iki sayının da 4'ten küçük olduğu bir çarpım şeklindedir. Asal sayılar, aritmetiğin temel teoreminden ötürü sayı teorisi alanında merkezi öneme sahiptir: 1'den büyük her doğal sayı, ya bir asal sayıdır ya da asal sayıların çarpımı olarak, sıralamalarından bağımsız bir şekilde, benzersiz olarak çarpanlarına ayrılabilir.

<span class="mw-page-title-main">Pi sayısı</span> dairenin çevresinin çapına oranını ifade eden irrasyonel matematik sabiti

Pi sayısı , bir dairenin çevresinin çapına bölümü ile elde edilen irrasyonel matematik sabitidir. İsmini, Yunanca περίμετρον (çevre) sözcüğünün ilk harfi olan π harfinden alır. Pi sayısı, Arşimet sabiti ve Ludolph sayısı olarak da bilinir. Aynı zamanda ismini yunancada pie anlamına gelen πίτα' dan alır.

<span class="mw-page-title-main">Mastürbasyon</span> cinsel organın uyarılması

Mastürbasyon, sürtünme yoluyla cinsel ilişki olarak, cinsel organın genellikle orgazm oluncaya kadar uyarılması eylemidir. Tek başına, kendi kendine veya başka biri tarafından el yoluyla ve parmaklama), ayak yoluyla ya da cinsel ilişkiye girmeden vücudun başka kısımlarıyla veya seks oyuncağıyla yapılabilir. Karşılıklı mastürbasyon, bir cinsel partnerle yapılan mastürbasyondur ve bir partnerin cinsel organlarının elle uyarılmasını içerebilir veya penetratif olmayan bir seks biçimi olarak kullanılabilir.

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

Radiohead, Oxfordshire'lı bir İngiliz alternatif rock grubudur. Grubun üyeleri, Thom Yorke, Jonny Greenwood, Ed O'Brien, Colin Greenwood ve Phil Selway 'dır. Radiohead, müzik otoriteleri tarafından en yaratıcı çağdaş rock grupları arasında gösterilir. Bunun en büyük nedenleri de birkaç katmandan oluşan şarkıları ve bir albümlerinden diğerine müzik tarzlarındaki radikal değişikliklerdir. Her ne kadar albümleri EMI gibi büyük ve ana akım bir yapımcı tarafından yayımlanıyorsa da, çoğunluk tarafından hem müzikal hem de politik bağımsızlıklarını korudukları düşünülmektedir. Radiohead albümleri, şimdiye kadar 27 milyondan fazla satış rakamına ulaştı.

<span class="mw-page-title-main">II. Elizabeth</span> Birleşik Krallık kraliçesi (1952–2022)

II. Elizabeth, Birleşik Krallık ve aralarında Kanada, Avustralya ve Yeni Zelanda'nın da olduğu İngiliz Milletler Topluluğu üyesi 14 ülkenin 1952-2022 yılları arasındaki kraliçesi. Aynı zamanda İngiliz Milletler Topluluğu başkanı ve İngiltere Kilisesi yüksek valisi olarak görev aldı. 70 yıl 214 günlük saltanatı ile Kraliçe Victoria'nın saltanatını geride bırakarak Birleşik Krallık'ın en uzun süre tahtta kalan hükümdarı, Fransa Kralı XIV. Louis'den sonra dünyanın en uzun süre tahtta kalan hükümdarı ve tarihte en uzun süre hüküm süren kadın hükümdar unvanlarını aldı.

<span class="mw-page-title-main">Birleştirmeli sıralama</span>

Birleşmeli Sıralama, bilgisayar bilimlerinde derecesinde karmaşıklığa sahip bir sıralama algoritmasıdır. Girdi olarak aldığı diziyi en küçük hale gelene kadar ikili gruplara böler ve karşılaştırma yöntemi kullanarak diziyi sıralar.

<span class="mw-page-title-main">Toplama</span> aritmetik işlem

Toplama işlemi dört ana aritmetik işlemden biridir. Diğer aritmetik işlemler çıkarma, çarpma ve bölmedir. İki doğal sayının toplaması sayı değerlerinin toplamını üretir. Yandaki resimdeki örnek, toplamda beş elma oluşturan üç elma ve iki elmanın toplamasını göstermektedir. Bu gözlem, matematik ifadesi ile "3 + 2 = 5" olarak ifade edilir

<span class="mw-page-title-main">Yığın sıralaması</span>

Yığın Sıralaması, bilgisayar bilimlerinde kullanılan karşılaştırmaya dayalı bir sıralama algoritmasıdır. Uygulamada pek çok bilgisayarda hızlı sıralama algoritmasından daha yavaş çalışsa da en kötü durumda O(n log n) çalışma süresi vardır. Yığın sıralaması diziyi yerinde sıralar ancak kararlı bir sıralama algoritması değildir.

İplik sıralaması bilgisayar bilimlerinde kullanılan bir sıralama algoritmasıdır. Sıralanacak olan dizinin, sıralanmış alt dizilerinin oluşturularak bu alt dizilerin birleştirilmesi yoluyla sonucun oluşturulması mantığına dayanır. Algoritmanın her bir aşamasında ana dizinin üzerinden geçilir ve bu diziden zaten sıralanmış olan bir dizi eleman çıkarılır. Çıkarılan bu eleman dizileri daha sonra birleştirilir.

Döngü açma, programın çalışmasını hızlandıran döngü dönüştürme yöntemlerinden biridir. Bu yöntem yazılan programın kod satır sayısını artırmaktadır. Döngülerdeki dönüşüm manuel olarak programcı tarafından yapılabileceği gibi kodlar derleyiciler tarafından da düzenlenebilmektedir.

<span class="mw-page-title-main">Murray Rothbard</span> Amerikalı ekonomist (1926 – 1995)

Murray Newton Rothbard, Avusturya Okulu'na mensup Amerikalı bir iktisatçı, iktisat tarihçisi, siyaset teorisyeni ve aktivisttir. Rothbard, 20. yüzyıl Amerikan liberteryen hareketinin, özellikle de sağ kanat kollarının merkezi bir figürüydü ve anarko-kapitalizmin kurucusu ve önde gelen teorisyenlerinden biriydi. Siyaset teorisi, tarih, ekonomi ve diğer konularda yirmiden fazla kitap yazdı.

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">Blok zinciri</span> sanal para aktarımlarının dağıtık olarak depolandığı veritabanı

Blok zinciri, blokzincir ya da özgün İngilizce tabiriyle blockchain, kriptografi kullanılarak bağlanan ve güvenli hale getirilen, bloklar adı verilen, sürekli büyüyen bir kayıt listesidir.

Hesaplamalı elektromanyetik, hesaplamalı elektrodinamik veya elektromanyetik modelleme elektromanyetik alan ile fiziksel nesnelerin ve çevrenin etkileşimini modelleme işlemidir.

<span class="mw-page-title-main">Bilgisayar bilimi tarihi</span>

Bilgisayar bilimi tarihi, modern dijital bilgisayarların ortaya çıkışından çok daha öncelere dayanmaktadır. Abaküs gibi sabit sayısal görevleri hesaplamak için kullanılan makineler, antik çağlardan beri çarpma ve bölme gibi hesaplamalara yardımcı olmuştur. Hesaplamalar yapmaya yaran algoritmalar, antik çağlardan beri, hatta gelişmiş bilgi işlem ekipmanlarının geliştirilmesinden önce bile var 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.

<span class="mw-page-title-main">Giorgia Meloni</span> İtalya başbakanı

Giorgia Meloni, Ekim 2022'den bu yana İtalya başbakanı olarak görev yapan ve bu pozisyonda bulunan ilk kadın olan İtalyan siyasetçidir. 2006'dan beri Temsilciler Meclisi üyesi olan Meloni, 2014'ten beri İtalya'nın Kardeşleri (FdI) siyasi partisine liderlik etmekte ve 2020'den beri Avrupa Muhafazakârlar ve Reformcular Partisi'nin başkanlığını yürütmektedir.

C++17, C++ programlama dili için yayınlanan ISO/IEC 14882 standardının bir versiyonudur. C++17, bir önceki C++ standardı olan C++14'ün yerine geçmiş, sonrasında C++20 ile yerdeğiştirmiştir.