İçeriğe geç

Binary tree oluşturmak

Merhabalar bu yazımda Ağaç algoritmalarından önemli ve bilindik bir algoritma olan binary ağacını Swift dili ile nasıl modeller arama işlemi gerçekleştiririz bunun örneğini göreceğiz.

Kısaca bu ağaç yapısını özetlersem. Bir adet root düğüm bulunur ve sol tarafı küçük değerler, sağ tarafı ise büyük değerler alır ve bu formata göre ağaç şekillenir. Farklı bir düğüm ağaca girmişse bu format tekrar oluşturulmak zorundadır. Algoritmik olarak arama işleminde ise root değerden küçük değerler sol tarafa bakılır. Aranan değer root değerden büyükse sağ tarafa bakılarak recursive bir işlem gerçekleştirilerek bulunur. Çoğu arama algoritmasından daha hızlı ve iyi sonuçlar vermektedir.

Bildiğimiz gibi ağaç yapıları bilgisayar bilimlerinde ve modern uygulamalarda kullanılmakta ve önemli bir yere sahiptir. Çoğu bilindik uygulama ağaç yapısını kullanarak hızlı bir şekilde arama ve relation işlemleri gerçekleştirmektedir.

Aşağıda yazdığım kod örneğini inceleyebilir, kullanımı görebilirsiniz.

class BinaryTree {
    
    var leftChild:BinaryTree?
    var rightChild:BinaryTree?
    var value:Int
    
    init(value:Int, leftChild:BinaryTree?, rightChild:BinaryTree?) {
        self.value = value
        self.leftChild = leftChild
        self.rightChild = rightChild
    }

}

//      7
//     / \
//    3   15
//   /   /  \
//  1    11  21
//      / \
//      8  19

// LEFT Branch

let child_1 = BinaryTree(value: 1, leftChild: nil, rightChild: nil)
let child_3 = BinaryTree(value: 3, leftChild: child_1, rightChild: nil)

// RİGHT Branch
let child_8 = BinaryTree(value: 8, leftChild: nil, rightChild: nil)
let child_19 = BinaryTree(value: 19, leftChild: nil, rightChild: nil)
let child_11 = BinaryTree(value: 11, leftChild: child_8, rightChild: child_19)
let child_21 = BinaryTree(value: 21, leftChild: nil, rightChild: nil)
let child_15 = BinaryTree(value: 15, leftChild: child_11, rightChild: child_21)

let root = BinaryTree(value: 7, leftChild: child_3, rightChild: child_15)

extension BinaryTree {
    class func search(value:Int,node:BinaryTree?) -> Bool {
        
        if node == nil {
            return false
        }
        
        if node?.value == value {
            return true
        } else if value < (node?.value)! {
            return search(value: value, node: node?.leftChild)
        } else {
            return search(value: value, node: node?.rightChild)
        }
        
    }
}

BinaryTree.search(value: 8, node: root) // true
BinaryTree.search(value: 31, node: root) // false

Github link.

 

Tarih:Algorithm

Bu yazı yorumlara kapalı.

Copyright © 2020 Kenan Atmaca