[CS] 자료구조 04 : 트리(Tree)

트리(Tree)

계층적인 구조를 나타내는 비선형 자료 구조

트리의 구조

노드 : 트리에서 데이터를 구성하는 각 요소을 노드라고 한다.

루트 노드: 트리의 가장 상위에 있는 노드를 루트(root) 노드이다.

부모 노드: 어떤 노드에 연결된 상위 노드를 해당 노드의 부모 노드라고 한다.

자식 노드: 어떤 노드의 하위에 연결된 노드들을 해당 노드의 자식 노드라고 한다.

리프 노드: 자식 노드가 없는 노드, 리프 노드는 트리의 가장 하위에 위치해 있다.

간선(edge) : 노드를 연결하는 선

Level : 노드의 깊이

Depth : 트리에서 노드가 가질 수 있는 최대 Level

이러한 트리에는 이진 트리(Binary Tree), 이진 탐색 트리(Binary Search Tree), 힙(Heap), AVL 트리, B-트리 등 다양한 종류의 트리가 존재하는데...

이번 포스팅에서는 이진 탐색 트리를 구현해보겠다.

이진 트리(Binary Tree)

각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조

이진 탐색 트리(Binary Search Tree)

이진 탐색트리는 이진 트리에서 다음과 같은 조건이 붙은 트리이다.

• 각 노드의 왼쪽 서브 트리에 있는 모든 노드들의 값은 해당 노드의 값보다 작습니다.
• 각 노드의 오른쪽 서브 트리에 있는 모든 노드들의 값은 해당 노드의 값보다 큽니다.

Swift Code

Node Class

class Node<T> {
    var data: T
    var left: Node?
    var right: Node?
    
    init(data: T) {
        self.data = data
    }
}

BinarySearchTree Class

class BinarySearchTree<T: Comparable> {
    var root: Node<T>?

Insert

    func insert(data: T) {
        root = insertRecursive(root, data)
    }
    
    private func insertRecursive(_ node: Node<T>?, _ data: T) -> Node<T> {
        guard let node = node else {
            return Node(data: data)
        }

        // 현재 노드가 내 데이터보다 크면 왼쪽으로, 작으면 오른쪽으로 가면서 내 위치를 찾는다.
        if data < node.data {
            node.left = insertRecursive(node.left, data)
        } else {
            node.right = insertRecursive(node.right, data)
        }
        return node
    }
}

Search

    func search(_ data: T) -> Bool {
        return searchRecursive(root, data)
    }
    
    private func searchRecursive(_ node: Node<T>?, _ data: T) -> Bool {
        guard let node = node else {
            return false
        }
        
        if node.data == data {
            return true
        } else if data < node.data {
            return searchRecursive(node.left, data)
        } else {
            return searchRecursive(node.right, data)
        }
    }

let bst = BinarySearchTree<Int>()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(1)
bst.insert(4)
bst.insert(6)
bst.insert(9)

print(bst.search(4)) //true
print(bst.search(2)) //false

 ┌──9
┌──7
│ └──6
5
│ ┌──4
└──3
 └──1
 
 시각적으로 확인해보았다.
 이건 https://babbab2.tistory.com/90 여기 참고함

이진탐색 트리 GIF 자료 출처
https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)