4Legs_Archives

문제 링크 : www.acmicpc.net/problem/8916 8916번: 이진 검색 트리 각 테스트 케이스에 대해서, 입력으로 주어진 순열과 같은 트리를 만드는 순열의 개수를 9,999,991로 나눈 나머지를 출력한다. www.acmicpc.net 한 트리에서 왼쪽 자식은 모두 파란색, 오른쪽 자식은 모두 빨간색으로 칠해보자. 우선 이러한 형태의 BST(Binary Search Tree)를 구성하기 위해선 반드시 root가 처음 입력되어야 한다는 것은 자명하다. 이 때, root 노드를 제외한 나머지 노드들의 번호가 아예 존재하지 않는다고 가정할 때, 위와 같은 BST의 형태만을 만드는 것은 다음과 같다. 각 자식 노드들의 서브트리 관계와 상관없이 단지 입력만을 고려했을 때, 왼쪽 서브트리의 모든 ..

효율적인 이진탐색 트리 (Efficient BST) 다음 두 이진탐색 트리를 보자. 첫 번째 BST는 25를 검색하기 위해 6번의 비교가 필요하다. 하지만 두 번째 BST는 3번의 비교로도 검색할 수 있다. 모든 노드를 Search하는 데 비교 횟수를 비교하면, 우리는 두 번째로 제시된 BST가 Search 수행이 더 효율적이라 할 수 있다. BST가 효율적이기 위해선 가능한 트리의 높이가 최소가 되어야 한다. 그러기 위해선 각 서브트리들이 어느 한쪽으로 치우치지 않고, 균형을 잘 이루어야 할 것이다. 이것이 AVL 트리의 핵심이다. 트리의 균형 (Balance Factor) 우리는 AVL 트리를 사용하기 위해 각 노드마다 균형 인수(BF, Balance Factor)를 둔다. 균형 인수는 한 노드에 대..

이진 탐색 트리 (Binary Search Tree) 딕셔너리(Dictionary)는 페어(Pair)의 모음으로, 각 페어는 Key값과 관련된 다른 값들로 이루어져 있다. 일반적인 딕셔너리 구조는 실제로는 그렇지 않음에도 불구하고 중복된 키값이 없다 가정하지만, 이진 탐색 트리에서는 이러한 가정 없이 쉽게 중복 키값에 대해 확장할 수 있는 자료구조이다. 정의 이진 탐색 트리는 이진 트리의 한 종류로써, 다음 조건들을 만족하는 자료구조이다. ① 각 노드는 구분되는 하나의 키값을 갖는다. ② 왼쪽 서브트리의 모든 키값들은 root의 키값보다 작다. ③ 오른쪽 서브트리의 모든 키값들은 root의 키값보다 크다. ④ 왼쪽, 오른쪽 서브트리 각각 또한 이진 탐색 트리이다. 탐색 (Search) 삽입 (Insert..