이진탐색트리(Binary Search Tree: BST)

BST

 BST(Binary Search Tree) = 이진탐색트리는 정렬된 트리 구조이다. 

저장과 동시에 정렬을 하는 자료구조이다. 새로운 데이터를 저장할때 일정한 규칙에 따라 저장을 하게된다.

어느 node를 선택하든 해당 node의 left subtree에는 그 node의 값보다 작은 값들을 지닌 node들로만 이루어져 있고, node의 right subtree에는 그 node의 값보다 큰 값들을 지닌 node들로만 이루어져 있는 binary tree다.

검색, 저장, 삭제의 시간복잡도는 모두 O(lonN)의 시간복잡도를 가지고, worst case는 한쪽으로 치우친 tree가 됬을경우 O(N)의 시간복잡도를 가진다.

1. root node보다 작은값을 left subtree 큰값을 right subtree에 저장한다.
2. 각 subtree들도 위와 같은 조건으로 반복되어진다.

worst case

worst case는 일반적으로 tree가 한쪽으로 치우친 경우(좌측이나 우측으로만 연결)에 발생되고 O(N)의 시간이 걸리게 된다.

이러한 경우를 피하는 방식은 대표적으로 AVL tree와 red-black tree가 있다. 이 두 tree는 삽입과 삭제 연산이 이루어질 때 트리의 균형을 유지하기 위해 회전하는 것으로, 균형을 잡힌 트리를 제공한다.