Tree
계층적 관계(Hierarchical Relationship)을 표현하는 자료구조다.
비선형 자료구조에 해당한다.
Tree에 쓰이는 용어
- 루트(root): 가장 상위 노드
- 부모(parent): 연결된 상위 노드
- 자식: 연결된 하위 노드
- 자손(descendant): 그 노드에서 생겨난 모든 노드
- 조상(ancestor) 그 노드를 생겨나게 한 모든 노드
- 레벨(level): 트리에서 같은 줄을 의미
- 프로퍼티(property): 균형잡힌 정도
- 하위 트리의 노드 개수가 같으면 그 트리는 균형(balanced) 트리다.
- 하위 트리의 노드 개수가 다르면 그 트리는 불균형(imbalanced) 트리다.
Binary Search Tree(이진 탐색 트리)
루트 노드에서 두개의 서브 트리로 나누어지고, 나누어진 서브 트리도 두개로 나누어진다.
공집합도 이진 트리에 포함해 노드가 하나, 또는 0개여도 이진 트리의 정의를 만족하도록 한다.
- 왼쪽 자손은 그 노드보다 작은 값만 포함한다.
- 오른쪽 자손은 그 노드보다 큰 값만 포함한다.
- 위의 두 조건을 만족하지 않는 경우 이진 트리나 이진 탐색 트리는 아니다.
이진 탐색 트리의 시간복잡도
탐색: 한번 검색할 때마다 검색 대상이 절반씩 감소한다. O(logN)
삽입: 해당 값을 넣을 노드를 칮고, 자식 노드를 삽입한다. O(logN)
삭제: 해당 값을 넣을 노드를 찾고, 연결이 끊긴 자식 노드를 처리한다. O(logN)
- 삭제할 노드에 자식이 없으면 삭제한다.
- 삭제할 노드에 자식이 하나라면 삭제하고 자식을 삭제한 노드의 위치에 넣는다.
- 삭제할 노드에 자식이 둘이라면 자식노드 중 삭제된 노드보다 큰 값 중 최솟값을 후속자 노드로 대체한다. 삭제된 값의 오른쪽 자식의 왼쪽 자식을 따라 계속 내려간 값에 해당된다.
- 후속자 노드에 오른쪽 자식만 있는 경우 후속자 노드를 삭제된 노드 자리에 넣은 후 오른족 자식은 후속자 노드의 원래 부모의 왼쪽 자식으로 넣는다.
*이진 탐색 트리에서는 N개의 노드가 있을 때 레벨은 logN개가 있다.
정렬된 배열의 시간복잡도
탐색: 한번 검색할 때마다 검색 대상이 절만씩 감소한다. O(logN)
삽입: 해당 값을 넣을 위치를 찾고, 삽입하고, 데이터를 하나씩 옮긴다. O(N)
삭제: 해당 값을 넣을 위치를 찾고, 삭제하고, 데이터를 하나씩 옮긴다. O(N)
데이터를 많이 변경하는 애플리케이션이라면 정렬된 배열보다 이진 탐색 트리가 더 적절하다.
자료구조 순회(traversal)
트리의 모든 노드의 데이터에 접근하는 것
중위 순회(inorder traversal)에서 데이터가 얻어지는 순서는 다음과 같다.
이 경우 시간복잡도는 O(N)에 해당된다.
