[알고리즘] 패스트캠퍼스 챌린지 10일차

트리(Tree) 구조

• 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
• 실제로 어디에 많이 사용되나?
  • 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨
• 알아둘 용어들
  • Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
  • Root Node: 트리 맨 위에 있는 노드
  • Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
  • Parent Node: 어떤 노드의 다음 레벨에 연결된 노드
  • Child Node: 어떤 노드의 상위 레벨에 연결된 노드
  • Leaf Node (Terminal Node): Child Node가 하나도 없는 노드
  • Sibling (Brother Node): 동일한 Parent Node를 가진 노드
  • Depth: 트리에서 Node가 가질 수 있는 최대 Level

이진트리 구조 / 용어 의미 확인해보기

 

이진트리(Binary Tree)와 이진 탐색 트리(Binary Search Tree)

• 이진 트리: 노드의 최대 Branch가 2인 트리
• 이진 탐색 트리 (Binary Search Tree, BST): 이진 트리에 다음과 같은 추가적인 조건이 있는 트리
  • 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음
  • 데이터 검색(탐색) 할 때에 주로 사용
  • 장점: 탐색 속도를 개선 가능
  • 단점: 

=> 이진 트리와 이진 탐색 트리를 동일하다고 하기도 하지만, 차이가 있으니 알아둬야 한다고 하셨다.
이진트리와 이진 탐색 트리의 차이점, 이진 탐색 트리의 장점인 탐색 속도 개선에 관해서 설명만 보면 잘 이해가 되지 않는데
아래 참고자료의 gif 보면 잘 알 수 있다.
특히 탐색 속도 개선 관련해서 예시로 숫자 탐색 시 정렬된 배열에서 탐색하는 것과 비교하는 자료가 도움이 많이 됨...!ㅎㅎ
이런 시각적인 자료를 함게 곁들여서 설명해주시니까 너무 좋당

[참고자료] https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node

5 Gifs to Understand Binary Search Trees

 

그럼 이제 트리구조를.. 코드로 구현...

이진트리를 잘 보면, 하나의 노드는 그 데이터와 왼쪽 또는 오른쪽으로 나아가는 주소값을 가지고 있다고 볼 수 있다.

링크드리스트.. 더블 링크드 리스트..?!

1. 새로 넣을 값(value)와 현재 노드의 값(value)를 비교한다.
2. 새로운 값 < 현재 노드의 값 => 왼쪽으로, 새로운 값 >= 현재 노드의 값 => 오른쪽으로
3. 현재 노드의 왼쪽 또는 오른쪽에 값이 없으면 새로운 값으로 해당 위치에 노드를 만들고 종료
4. 현재 노드의 온쪽 또는 오른쪽에 값이 있으면 비교할 노드를 그 위치의 노드로 변경

class Node<T: Comparable> {
    var value: T?
    var left: Node?
    var right: Node?
    
    init(_ value: T, left: Node? = nil, right: Node? = nil) {
        self.value = value
        self.left = left
        self.right = right
    }
}

class BinarySearchTree<T: Comparable> {
    // root node of Tree
    var head: Node<T>?
    // current Node
    var node: Node<T>?


    init(_ head: Node<T>? = nil) {
        self.head = head
    }

    // insert value to tree
    func insert(value: T) {
        // first node == head(root node)
        guard self.head != nil else {
            return
        }
        self.node = self.head
        while true {
            if value < self.node!.value! {
                // go left
                if self.node?.left != nil {
                    // need to compare with left's node
                    self.node = self.node?.left
                } else {
                    // current node's left is empty >> Make New Node with value
                    self.node?.left = Node(value)
                    break
                }
            } else {
                // go right
                if self.node?.right != nil {
                    // need to compare with right's node
                    self.node = self.node?.right
                } else {
                    // current node's right is empty >> Make New Node with value
                    self.node?.right = Node(value)
                    break
                }
            }
        }
    }
}

// test 
let head = Node(1) 
// make tree with root node 
let tree = BinarySearchTree(head) 
// insert value to the tree tree.
tree.insert(value: 2)

오..!
새로운값 insert 까지 성공!!!!



오늘부터 트리 구조에 대해 공부했다.
어려워서 트리 언제끝나나 강의 목차 보는데 트리 1 부터 8까지..
오늘 수요일이니까.. 이번주 내내 트리 보고 보고 보고 보면.. 되나...? 휴우

일단 오늘 들은 내용은 지난주에 했던 Double Linked List와 비슷해서 걱정했던 것 만큼 어렵지는 않았던 것 같다.
방법만 이해하고 나니, Swift로 잘 짰다!

그럼 이제 insert 했으니까 데이터 출력하기.. 이건 내일해야겠다..ㅎㅎ

강의 인증샷. 트리 어렵다..!

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.