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

Bir Yorum Bırakın