* upper_bound는 이분 탐색을 이용해 O(logN)에 주어진 값을 처음으로 초과하는 인덱스를 구하는 함수입니다.
이분 탐색을 이용한 upper_bound 함수는 여기의 1)에서와 같이 일반적으로 정렬된 배열에 사용하지만, 이 문제에서는 양쪽 서브트리의 경계가 되는 두 인덱스 사이를 기준으로 root 값보다 작은 값들은 모두 왼쪽에 위치하고 root 값보다 큰 값들은 모두 오른쪽에 위치합니다. 따라서 root 값을 기준으로 upper_bound를 사용하면 O(logN)의 시간복잡도로 두 서브트리의 경계를 찾을 수 있습니다.
구현 방법으로는 preorder의 순회 결과에 대해 각 (서브)트리의 범위를 [left, right)로 놓고, 구간 [left + 1, right)에 preorder[left] (=root 노드)를 기준으로 upper_bound 함수를 실행하면 오른쪽 서브트리의 첫 인덱스를 구할 수 있습니다.
iterator를 이용한 구현을 여기에서 보실 수 있습니다. 골드1로서는 이런 글이라도 쓰면 기분이 좋습니다.
molla12 2년 전 8
C++ 이외의 언어에서도 이분 탐색을 이용해 실행 시간을 줄일 수 있습니다.
왼쪽과 오른쪽 서브트리를 구분할 때
upper_bound를 사용하면 됩니다.*
upper_bound는 이분 탐색을 이용해 O(logN)에 주어진 값을 처음으로 초과하는 인덱스를 구하는 함수입니다.이분 탐색을 이용한
upper_bound함수는 여기의1)에서와 같이 일반적으로 정렬된 배열에 사용하지만, 이 문제에서는 양쪽 서브트리의 경계가 되는 두 인덱스 사이를 기준으로 root 값보다 작은 값들은 모두 왼쪽에 위치하고 root 값보다 큰 값들은 모두 오른쪽에 위치합니다. 따라서 root 값을 기준으로upper_bound를 사용하면 O(logN)의 시간복잡도로 두 서브트리의 경계를 찾을 수 있습니다.구현 방법으로는 preorder의 순회 결과에 대해 각 (서브)트리의 범위를 [left, right)로 놓고, 구간 [left + 1, right)에 preorder[left] (=root 노드)를 기준으로 upper_bound 함수를 실행하면 오른쪽 서브트리의 첫 인덱스를 구할 수 있습니다.
iterator를 이용한 구현을 여기에서 보실 수 있습니다. 골드1로서는 이런 글이라도 쓰면 기분이 좋습니다.