4Legs_Archives

효율적인 이진탐색 트리 (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..