노드와 브랜치를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조

용어

노드 : 트리에서 데이터를 구성하고 있는 각 요소 (데이터 및 브랜치 정보)

루트 노드 : 트리의 최상위에 있는 노드

부모 노드 : 어떤 노드의 윗 레벨 노드

자식 노드 : 어떤 노드의 아랫 레벨 노드

리프 노드 : 자식 노드가 없는 노드

깊이 : 트리에서 노드가 가질 수 있는 최대 레벨

이진 트리

자식 노드가 최대 두개인 노드로만 구성된 트리

이진 탐색 트리

이진 트리에 추가 조건이 붙은 것이다.

자신의 왼쪽 자식 노드에는 자신 보다 작은 값이

자신의 오른쪽 자식 노드에는 자신 보다 큰 값이 오는 규칙을 만족하는 이진 트리

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

}

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

func insert (_ data: T) {
		guard let root = self.root else {
				return self.root = Node.init(data : data)
		}
		var currentNode = root
		while true {
				if currentNode.data > data {
						guard let nextNode = currentNode.left else {
								return currentNode.left = Node.init(data: data)
						}
						currentNode = nextNode
				}else {
						guard let nextNode = currentNode.right else{
								return currentNode.right = Node.init(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
}

이진 탐색 트리 사용 용도 및 장점 / 단점

장점

데이터를 탐색 할 때 배열에서 이진 탐색을 하는 것과 같이 속도가 빠르다.