그래프는 단방향, 양방향을 모두 가리킬 수 있지만, 트리는 부모 노드에서 자식 노드를 가리키는 단방향만 존재한다.
이진 트리
최대 2개의 자식을 갖는 형태의 트리이다.
이진 트리 vs 이진 탐색 트리
이진 트리: 최대 2개의 자식을 갖는 트리
이진 탐색 트리: 이진 트리에 추가적인 조건이 존재하는 트리
노드의 왼쪽 하위 트리에는 노드의 값보다 작은 값의 노드만 존재한다.
노드의 오른쪽 하위 트리에는 노드의 값보다 큰 노드만 존재한다.
이진 탐색 트리를 사용하는 이유
이진 탐색 트리의 시간 복잡도 → 트리의 높이가 h라고 한다면 → O(h)
데이터의 수로 표기하는게 정석이므로 그렇게 표기를 한다면 → 모든 노드가 빈 자리 없이 꽉꽉 채워져있는 포화 이진 트리일 경우 → 포화 이진 탐색 트리를 구성하고 있는 노드의 개수가 n개일 때, $ n = 2^h - 1 $ 이므로 h = log(n-1) O(h) = O(log(n-1)) = >O(logn)
배열 탐색의 시간복잡도 → O(n)
반면, 트리가 아래 그림처럼 한쪽으로 치우친 경우에는 $ h = n $ 이므로 O(n)의 시간복잡도를 갖는다.