노드와 브랜치를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
노드 : 트리에서 데이터를 구성하고 있는 각 요소 (데이터 및 브랜치 정보)
루트 노드 : 트리의 최상위에 있는 노드
부모 노드 : 어떤 노드의 윗 레벨 노드
자식 노드 : 어떤 노드의 아랫 레벨 노드
리프 노드 : 자식 노드가 없는 노드
깊이 : 트리에서 노드가 가질 수 있는 최대 레벨
자식 노드가 최대 두개인 노드로만 구성된 트리
이진 트리에 추가 조건이 붙은 것이다.
자신의 왼쪽 자식 노드에는 자신 보다 작은 값이
자신의 오른쪽 자식 노드에는 자신 보다 큰 값이 오는 규칙을 만족하는 이진 트리
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
}
장점
데이터를 탐색 할 때 배열에서 이진 탐색을 하는 것과 같이 속도가 빠르다.