Binary Tree

Binary Tree

이진트리는 각 노드가 최대 2개의 자식을 갖는 트리이다.

 

Binary Search Tree

이진 탐색 트리는 모든 노드 n에 대해 left subtree <= n < right subtree를 만족하는 이진트리이다.

Binary Search Tree

이러한 특성때문에 inorder traversal을 하면 오름차순으로 정렬된 수열을 얻을 수 있다. 위의 그림에서는 2, 4, 6, 8, 10, 20 순서대로 방문하게 된다.

 

전체 N개의 노드가 균형이 잡힌 BST에 저장되어 있다면, 특정 값을 찾는 데에 O(logN)이 걸린다.