tree

이진탐색트리(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)의 시간복잡도를 가진다. root node보다 작은값을 left subtree 큰값을 right subtre..