Veri Yapıları – Ağaçlar


Ağaçlar/Trees, verilerin birbirlerine bağlanmasıyla oluşturulan, ağaç yapısına benzer bir yapıya sahip veri modelleridir.

Ağaç Yapısını İnceleyelim..

  • Bir ağacın her bir elemanına node/düğüm denir.
    • Veriler node’larda tutulur.
  • Düğümler birbirlerine edge/kenar/dal ile bağlanır.
    • Bu bağlantılar iki node arasındaki ilişkiyi gösterir

Trees1.png

  • Düğümler ağaca seviyeler oluşturacak şekilde yerleştirilirler, yani ağaçlar hiyerarşik bir yapıya sahiptir.
    • Bu hiyerarşik yapının en tepesindeki düğüm; root/kök,
    • En ucundaki, çocuğu olmayan düğümler; leaf/yaprak,
    • Çocuğu olan düğümler; parent/ebeveyn, çocuklar ise child/çocuk olarak adlandırılır.
    • Bir düğümün alt ağaçlarına subtree denir.

tree-structure

 

 

    • Aynı parent’a sahip düğümler birbirlerinin sibling/kardeş node’larıdır.
    • Bir düğümden köke kadar izlenen yoldaki diğer tüm düğümler, o düğümün ancestor/atalarıdır.
    • Bir düğümün çocuklarına bağlı olan tüm düğümler, o düğümün descendant/torunlarıdır.
  • Bir düğüme ulaşmak için üzerinden geçilen düğümler listesine path/yol/iz denir.
  • Düğümün depth/derinliği, o düğümden kök düğüme kadar olan yolun uzaklığıdır. (Kök düğümünün derinliği 1 kabul edilerek örnekleme yapılacaktır).
    • Bir ağacın derinliği kök düğümün en uçtaki yaprak düğüme olan uzaklığıyla ölçülür.
  • Düğümün height/yüksekliği, o düğümden kendisiyle ilişkili en uzak yaprak düğüme kadar giden yolun uzunluğudur.
  • Düğümün level/düzey/seviyesi, kök ve ilgili düğüm arasında bulunan düğümlerin sayısına eşittir. ( Bu yazı için kök düğümün düzeyi 1 kabul ederek örnekleme yapılacaktır)
  • Bir node’un degree/derecesi, çocuk sayısına eşittir.
  • Ağaçlar döngü/cycle içermezler.
  • Bir ağacın hiç düğümü yoksa, boş/empty tree olarak adlandırılır. 🙂

Ne Öğrendik ?

örnek ağaç.jpg

Şekildeki ağacı aşağıdaki tabloda inceleyelim;

  Root ( M ) E R
Derece/Çocuk Sayısı 2 1 0
Düzey 1 3 4
Derinlik 1 3 4
Ebeveyn/Parent K S
Kardeş L T
Ata M P, M
Çocuk K, P C
Path M M, K, E M, P, S, R

Binary Tree / İkili Ağaçlar 

Binary/İkili ağaç yapısında bir node’un en fazla iki çocuğu vardır. Bu çocuklar sağ ve sol olarak adlandırılır.

  • Full Binary Tree; Yapraklar hariç her bir node’un iki çocuğu olmak zorundadır ve dolayısıyla tüm yaprakları aynı derinliktedir.

fullbinary

  • Complete Binary Tree ; Her bir yeni derinliğe düğümler soldan sağa doğru eklenir ve bir derinlik tamamlanmadan bir sonraki derinliğe geçilmez.
    • Her node iki tane çocuğa sahip olmayabilir ve bazı yapraklar arasında derinlik farkı olabilir. Bu nedenle bir complete tree, full binary tree özelliği taşımayabilir.
    • Yapraklar arasındaki derinlik farkı en fazla 1’dir.

completebinary

Complete Binary Tree

not full and binary.png

Not full and complete tree

  • Balanced Binary Tree ; Her bir düğümün sol alt ağacının yüksekliği ile sağ alt ağacının yüksekliği arasında en çok 1 fark olmalıdır.
    • Complete Binary Tree’ler aynı zamanda Balanced Binary Tree’dir ancak tam tersi durum her zaman doğru değildir.

Ağaç Üzerinde Nasıl Dolaşırım ?

Ağaç üzerindeki gezinme/traversal işlemi tüm düğümlere uğrayarak gerçekleştirilir. Doğrusal veri modellerinden farklı bir yapıya sahip olan ağaçları dolaşmak için kullanılan bir kaç algoritma örneği verirsek;

  • Pre-order Traversal (root-left-right)
    • Kökü ziyaret et
    • Sol alt ağacı dolaş
    • Sağ alt ağacı dolaş
  • In-order Traversal (left-root-right)
    • Sol alt ağacı dolaş
    • Kökü ziyaret et
    • Sağ alt ağacı dolaş
  • Post-order Traversal (left-right-root)
    • Sol alt ağacı dolaş
    • Sağ alt ağacı dolaş
    • Kökü ziyaret et

336px-sorted_binary_tree_preorder-svg

 

 

 

Pre-order   : F, B, A, D, C, E, G, I, H

In-order     : A, B, C, D, E, F, G, H, I

Post-order : A, C, E, D, B, H, I, G, F

 

 

 

  • Level-order Traversal (Breadth-first)
    • Kökü ziyaret et
    • Soldan sağa ağacı dolaş

220px-sorted_binary_tree_breadth-first_traversal-svg

 

 

Level-order : F, B, G, A, D, I, C, E, H

 

 

Expression Tree / İfade Ağaçları 

  • Matematiksel işlemlerin ağaca aktarılmış halidir.
  • Yapraklar her zaman değişken ya da sabit değerler alır.
  • Parent node’lar işlem operatörlerini tutar.
  • In-order traversal normal işlem düzenini sağlarken (infix), Pre-order prefix, Post-order ise postfix sonuçlar verir.
  • En son yapılacak işlem root node’unda tutulur.

exp-tree-ex-11-svg

 

 

 

infix     : (a+b) *c + 7

prefix   : +*+abc7

postfix : ab+c*7+

 

Yararlandığım Kaynaklar :  

  1. Veri Yapıları Ders Notlarım 🙂
  2. ÇU Veriyapıları Ders Notları
  3. Tree Traversal
  4. Binary Expression Tree – Wikipedia
  5. KU Veri Yapıları Ders Notları

İLGİNİZİ ÇEKEBİLİR

UNITY – PlayerPrefs Kullanımı
November 28, 2016
Wireframe Nedir,Uygulama Alanları Nelerdir
November 16, 2016

6 Comments

Yavuzfk
Reply 19 Aralık 2019

Özet ve çok yararlı bir kaynak olmuş, teşekkürler.

    Setenay Ceren Ağdaş
    Reply 9 Ocak 2020

    Rica ederim

Enes Şahin
Reply 8 Ocak 2020

Çok yararlı bir not olmuş teşekkür ederim

    Setenay Ceren Ağdaş
    Reply 9 Ocak 2020

    Rica ederim

Esra
Reply 26 Mayıs 2020

Gerçekten çok işime yaradı, çok akıcı ve çok güzel anlatmışsınız.Teşekkür ederim.

    Setenay Ceren Ağdaş
    Reply 29 Mayıs 2020

    Rica ederim. Yorumunuz için teşekkürler :)

Bir Yorum Bırakın