AVL Tree 썸네일형 리스트형 Introduction to B-Tree 2 효율적인 트리(tree) 구조를 유지하는데 가장 큰 문제는, 최적의 트리 탐색 성능을 제공하기 위해서 트리는 정렬된 상태로, 균형 트리를 이루어야 한다는 것이다. 그러나 트리의 균형을 잡는 연산은 매우 비싸다. 이진 트리가 이상적인 상태를 유지한다고 하더라도, 이진 탐색은 디스크 상주 인덱싱에 비해서 그다지 빠르지 않다. 트리가 최적의 탐색 성능을 제공하기 위해서는, 트리는 균형을 이루어야 하는데, 이것은 가능한 한 루트에서 가장 끝에 위치한 각각의 노드까지 경로가 최대한 비슷해야 한다는 것을 의미한다. 즉, 트리가 최악의 성능을 보이는 경우는 일렬로 노드가 연속되어 붙어 있을 때이며, 이 경우 사실 트리라기보다는 리스트에 더 가깝다. 역사적으로 트리를 균형 상태로 유지하기 위해 AVL 트리나, 페이지화.. 더보기 이전 1 다음