균형 이진 탐색 트리

모르는 단어

proportional 비례하는

justified 이치에 맞는

constant factor

lower bound

amortized analysis 최악의 경우를 (시간)평균내서 분석하는 것.

http://en.wikipedia.org/wiki/Amortized

exploit 활용하다 판촉하다.

균형 이진 탐색 트리

http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

In computer science, a self-balancing binary search tree or height-balanced binary search tree is a binary search tree (BST) that attempts to keep its height, or the number of levels of nodes beneath the root, as small as possible at all times, automatically. 

컴퓨터 과학에서 (자가) 균형 이진 탐색 트리나 (높이) 균형 이진 탐색 트리는 자동적으로 항상 가능한한 작게 루트 밑의 노드의 레벨의 수나 높이를 유지하도록 시도하는 이진 탐색 트리이다.

It is one of the most efficient ways of implementing ordered lists and can be used for other data structures such as associative arrays and sets.

정렬된 리스트를 구현하는 데 효율적인 방법이고 associative arrays와 associative set 같은 다른 자료 구조에도 사용될 수 있다.

Most operations on a binary search tree take time directly proportional to the height of the tree, so it is desirable to keep the height small. 

이진 탐색의 대부분의 연산은 트리의 높이에 직접 비례하여 시간이 걸리기 때문에 트리의 높이를 작게 유지하는 것이 요구된다.

Ordinary binary search trees have the primary disadvantage that they can attain very large heights in rather ordinary situations, such as when the keys are inserted in sorted order. 

일반 이진 검색 트리는 키들이 정렬된 순서로 추가될 때처럼 일반적인 상황에서 매우 큰 높이에 도달할 수 있는 큰 단점을 가진다.

The result is a data structure similar to a linked list, making all operations on the tree expensive. 

그 결과는 트리 비용에서 대부분의 연산을 링크드 리스트와 비슷한 데이터 구조처럼 된다.

If we know all the data ahead of time, we can keep the height small on average by adding values in a random order, resulting in a random binary search tree, but we don't always have this luxury, particularly in online algorithms.

우리가 미리 모든 데이터를 안다면 임의의 순서로 값이 추가됨으로서 평균적으로 작은 높이를 유지할 수 있지만 특히 온라인 알고리즘에서는 이렇게 미리 알 수는 없다.

Self-balancing binary trees solve this problem by performing transformations on the tree (such as tree rotations) at key times, in order to reduce the height. 

(자가) 균형 이진 트리는 높이를 줄이기 위해 key time에 (트리 순회같은) 트리의 변형함으로서 이 문제를 해결한다.

Although a certain overhead is involved, it is justified in the long run by ensuring fast execution of later operations.

오버헤드가 있더라도 나중 연산의 빠른 실행을 보장함으로서는 오랜 시간이 지나서 볼 때에는 이치에 맞는다.

The height must always be at most the ceiling of log2n, since there are at most 2k nodes on the kth level; a complete or full binary tree has exactly this many levels. 

k번째 단계에서 최대 2k의 노드가 있어야하기 때문에 높이는 최대 log2n이어야 한다. 완전 혹은 full 이진 트리는 정확히 이만큼의 단계를 가진다.

Balanced BSTs are not always so precisely balanced, since it can be expensive to keep a tree at minimum height at all times; instead, most algorithms keep the height within a constant factor of this lower bound.

항상 최소의 높이를 가진 트리를 유지하는 것이 비용이 많이 들기 때문에 균형 이진 탐색 트리는 항상 아주 정밀하게 균형 잡혀있지는 않다. 

대신, 대부분의 알고리즘은 이보다 작은 값의 상수 요소 안에서 높이가 유지된다.(?)

Times for various operations in terms of number of nodes in the tree n:

다음은 n개의 node를 가진 트리에서 다양한 연산의 회수를 보여준다.

이러한 구현에 대해 이 회수는 가장 안좋은 경우이다.

구현

다음은 트리의 다음 형태로 구현되는 유명한 자료 구조들이다.

응용프로그램

Self-balancing binary search trees can be used in a natural way to construct and maintain ordered lists, such as priority queues.

(자가) 균형 이진 탐색 트리는 우선순위 큐 같은 순서화된 리스트를 유지하고 생성하는 자연스러운 방법이 될 수 있다.

They can also be used for associative arrays; key-value pairs are simply inserted with an ordering based on the key alone. 

associative arrays에도 사용될 수 있다. 키-값 쌍은 키로만 정렬함으로서 간단히 추가될 수 있다.

In this capacity, self-balancing BSTs have a number of advantages and disadvantages over their main competitor, hash tables. 

이러한 능력은 균형 이진 탐색 트리가 해시 테이블과 비교(경쟁)하여 장점과 단점을 가진다.

Lookup is somewhat complicated in the case where the same key can be used multiple times.

탐색은 같은 키가 여러번 사용되는 곳에서는 다소 복잡하다.

Many algorithms can exploit self-balancing BSTs to achieve good worst-case bounds with very little effort. 

많은 알고리즘은 매우 적은 노력으로 최악의 경우의 값에서 좋은 결과를 달성하기 위해 균형 이진 탐색 트리를 활용할 수 있다.

For example, if binary tree sort is done with a BST, we have a very simple-to-describe yet asymptotically optimal O(n log n) sorting algorithm (although such an algorithm has practical disadvantages due to bad cache behavior). 

예를 들어 이진 트리 정렬은 이진 검색 트리에 의해 해 놓았다면 우리는 

Similarly, many algorithms in computational geometry exploit variations on self-balancing BSTs to solve problems such as the line segment intersection problem and the point location problem efficiently.

비슷하게 

Self-balancing BSTs are a flexible data structure, in that it's easy to extend them to efficiently record additional information or perform new operations.

For example, one can record the number of nodes in each subtree having a certain property, allowing one to count the number of nodes in a certain key range with that property in O(log n) time. These extensions can be used, for example, to optimize database queries or other list-processing algorithms.