이진 검색 트리는 한 쪽으로 쏠린 형태가 되면 비효율적인 연산이 나타나게 된다. 레드 블랙 트리와 AVL트리 같이 복잡한 트리 구조를 설계하면 항상 일정한 균형성을 보장한 이진 검색 트리를 만들 수 있다. 그러나 이는 실제로 설계하기 매우 어려우므로 가장 간단한 구조로 균형성을 보장하는 이진 검색 트리가 트립이다.
C++의 표준 라이브러리에는 map, set 클래스가 있는데, 이 클래스들은 레드 블랙 트리로 만들어진 구조기 때문에 균형성이 있고 쉽게 사용할 수 있다. 그러나 이 클래스들은 특정 위치의 원소를 찾거나 특정 값보다 작은 값을 가진 원소의 수를 세는 것과 같은 연산을 제공하지 않는다. 알고리즘 문제 해결 과정에서 이러한 연산이 필요할 때가 있는데, 트립은 이러한 연산을 제공하기 때문에 유용하다.
typedef int KeyType;
struct Node {
KeyType key;
int priority, size;
Node* left, *right;
Node(const KeyType& _key) : key(_key), priority(rand()), size(1), left(NULL), right(NULL){}
void setLeft(Node* newLeft) { left = newLeft; calcSize(); }
void setRight(Node* newRight) { right = newRight; calcSize(); }
void calcSize() {
size = 1;
if (left) size += left->size;
if (right) size += right->size;
}
};
기본적인 이진 검색 트리의 노드 원소 이외에도 트립의 노드는 priority, size값을 갖는데, 이는 균형잡힌 구조를 만들어 주고 특정 원소의 위치를 찾는데 사용된다.
priority의 경우 랜덤하게 생성되는데 priority를 기준으로 노드의 위치가 결정된다. 부모 노드는 반드시 자식 노드에 비해 높은 priority를 가지고 있어야 한다. 따라서 랜덤으로 부여되는 priority 때문에 균형잡힌 구조가 만들어질 가능성이 훨씬 높아진다.
struct의 생성자로 주어진 key값, 랜덤으로 부여된 priority, 자기 자신을 루트로 하는 size 1이 설정된 모습을 볼 수 있다.
image.png 힙이란 이진 검색 트리와 비슷한 형태의 구조를 가지고 있지만 트리보다 더 느슨한 대소 관계 조건을 가지고 있고 더 엄격한 모양 조건을 가지고 있는 구조를 말한다. 이진 검색 트리는 루트보다 작은 노드는 왼쪽 자식, 큰 노드는 오른쪽 자식의 규칙을 가지고 있는데, 힙은 부모 노드보다 자식 노드가 작기만 하면 된다. 이렇게 느슨한 ...
image.png 문제 파악 삽입 정렬 과정에 관한 정보를 바탕으로 정렬되기 전 수열을 찾는 문제이다. 삽입 과정 정보를 인데스로 사용하여 원래 수열의 위치를 하나씩 파악할 수 있으므로 삽입 과정을 vector로, 인덱스를 이용해 찾고자 하는 수 를 찾는 컨테이너를 트립으로 두면 문제를 NlogN의 시간 복잡도로 해결할 수 있다. 숫자를 하나씩 ...
트립이란 이진 검색 트리는 한 쪽으로 쏠린 형태가 되면 비효율적인 연산이 나타나게 된다. 레드 블랙 트리와 AVL트리 같이 복잡한 트리 구조를 설계하면 항상 일정한 균형성을 보장한 이진 검색 트리를 만들 수 있다. 그러나 이는 실제로 설계하기 매우 어려우므로 가장 간단한 구조로 균형성을 보장하는 이진 검색 트리가 트립이다. C++의 표준 라이브러리에는 ...
map 클래스 map클래스는 이진 검색 트리 기반의 자료 구조이다. 일반적인 이진 검색 트리는 한 방향으로 쏠린 형태로 만들어져 효율성이 떨어질 수 있는데 map은 레드 트리 구조로 되어 있어서 항상 일정한 효율성을 보장한다. 레드 트리 구조는 직접 구현하기 매우 복잡해서 C++의 표준 라이브러리 중 하나인 map클래스를 사용하는 것이 좋다. se...
image.png 문제 접근 값을 계산하는 과정에서 값을 검색하고 비교하는 과정이 필요하므로 이진 검색 트리를 활용하는 것이 좋겠다는 생각이 들었다. 이를 위해 C++의 표준 라이브러리 중 이진 검색 트리 기능을 하는 set을 사용하려고 했다. 문제에 대한 값이 들어오면 그 값보다 큰 값을 가진 인덱스들에 대해 라면의 값을 확인하려고 했다. se...