# 이진 탐색 트리
[참고자료](https://www.youtube.com/watch?v=ESqeK-ACHkU)

- 3가지 연산: 삽입, 삭제, 탐색
- 모든 원소는 유일한 키 값을 갖는다.
- 왼쪽 서브트리의 모든 원소들은 루트의 키보다 작은 값을 갖는다.
- 오른쪽 서브트리의 모든 원소들은 루트의 키보다 큰 값을 갖는다.
- 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리이다.


- 탐색 연산의 Big-O는 O($\log_{2}{N}$)
- 노드를 하나 통과할 때마다 검색 대상이 2분의 1로 줄어들기 때문이다.

**중위 운행**
> 4 6 8 10 12 14 15 20
> 오름차순이네?
> 이것 역시 이진 탐색 트리의 특징이라 할 수 있다.

## 운행법
- 트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다.

- 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다.

- 이진트리의 운행법은 세 가지가 있따

- 전위(Preorder) 운행 : Root -> Left -> Right

- 중위(Inorder) 운행 : Left -> Root -> Right

- 후위(Postorder) 운행 : Left -> Right -> Root

### 탐색, 삽입

> 유일한 키를 가져야 하는 이진 탐색 트리에는 탐색이 성공했을 때는 삽입이 당연히 안된다.
>
> 탐색 실패 시에 실패한 위치에 노드를 삽입한다.

final class Node<T: Comparable> {
    var data: T
    var left: Node?
    var right: Node?

    init(data: T) {
        self.data = data
    }
}



final class BinarySearchTree<T: Comparable> {
    var root: Node<T>?
    
    func insert(_ data: T) {
        guard let root = self.root else {
            return self.root = Node(data: data)
        }

        var currentNode = root

        while true {
            if currentNode.data > data {
                guard let nextNode = currentNode.left else {
                    return currentNode.left = Node(data: data)
                }
                currentNode = nextNode
            } else {
                guard let nextNode = currentNode.right else {
                    return currentNode.right = Node(data: data)
                }
                currentNode = nextNode
            }
        }
    }
    
    func search(from data: T) -> Bool {
        if root == nil { return false }

        var currentNode = root
        while let node = currentNode {
            if node.data == data {
                return true
            }
            if node.data > data {
                currentNode = node.left
            } else {
                currentNode = node.right
            }
        }
        return false
    }
    
    func deleteBST(_ data: T) {
        var currentNode = root
        
        while let node = currentNode, node.data != data {
            
        }
    }
}