이진탐색트리 구현

이진탐색

• 탐색에 소요되는 시간 복잡도는 O(log n)
• 자료의 입력과 삭제가 불가능

연결리스트

• 탐색에 소요되는 시간 복잡도는 O(n)
• 자료 입력과 삭제의 시간 복잡도는 O(1)

이진탐색트리

• 각 노드의 왼쪽 노드는 해당 노드보다 적은 값이 존재한다.
• 각 노드의 오른쪽 노드는 해당 노드보다 높은 값이 존재한다.
• 중복된 노드는 허용되지 않는다.
• 중위순회 방식 (왼쪽 서브트리 -> 노드 -> 오른쪽 서브트리)

class Node {

let value: Int
var leftChild: Node?
var rightChild: Node?

init(value: Int, leftChild: Node?, rightChild: Node?) {

    self.value = value
    self.leftChild = leftChild
    self.rightChild = rightChild
 }

}

// Left Branch

let oneNode = Node(value: 1, leftChild: nil, rightChild: nil)
let fiveNode = Node(value: 5, leftChild: oneNode, rightChild: nil)

// Right Branch

let elevenNode = Node(value: 11, leftChild: nil, rightChild: nil)
let twentyNode = Node(value: 20, leftChild: nil, rightChild: nil)
let fourteenNode = Node(value: 14, leftChild: elevenNode, rightChild: twentyNode)

// TOP

let tenRootNode = Node(value: 10, leftChild: fiveNode, rightChild: fourteenNode)

func search(node: Node?, searchValue: Int) -> Bool {

   if node == nil {

	return false
   }

   if node?.value == searchValue {

	return true
   }

   // improve
   else if searchValue < node?.value ?? 0 {

	return search(node: node?.leftChild, searchValue: searchValue)
   }
   else {

	return search(node: node?.rightChild, searchValue: searchValue)
   }
   
   // basic
   else {
   
   	return search(node: node?.leftChild, searchValue: searchValue) ||
               search(node: node?.rightChild, searchValue: searchValue)
   }

}

search(node: tenRootNode, searchValue: 20)
// improve version: 2 times
// basic version: 5 times

compared to arr
let arr = [1, 5, 10, 11, 14 ,20]
let index = arr.firstIndex(where: { $0 == 20 }) // 7 times