이항 트리(Binomial Tree)란?
이항 트리는 순서화된(orderd) 트리 자료구조입니다. B0는 단 하나의 노드로 구성되며, Bk로 표현되는 이항 트리는 두 개의 이항 트리 Bk-1이 서로 연결된 형태입니다. 이때 한 이항 트리의 루트(root)는 다른 이항 트리 루트의 가장 왼쪽 자식 노드가 됩니다.
이항 트리는 주로 자산이나 주식의 기본적·기술적 분석에 활용됩니다. 이항 트리의 각 노드는 자산의 내재가치(intrinsic value)를 나타내며, 투자자나 시장 참여자가 최적의 투자 시점과 가치를 판단하는 데 유용한 도구가 됩니다.
이항 힙(Binomial Heap)이란?
이항 힙은 여러 개의 이항 트리를 결합하여 만든 자료구조입니다.
이항 힙 H가 만족해야 하는 성질은 다음과 같습니다.
H에 속한 모든 이항 트리는 힙 순서(heap-ordered)를 따릅니다. 즉, 각 노드의 키 값은 부모 노드의 키 값보다 크거나 같습니다.
H 안에는 특정 차수(degree)를 가진 루트를 가지는 이항 트리가 최대 하나만 존재합니다.
이항 힙 예시
이항 힙 노드의 메모리 표현
이항 힙의 각 노드는 메모리상에서 총 5개의 필드로 표현됩니다.
부모 포인터(Parent Pointer) : 부모 노드의 주소를 저장하여, 이항 힙 구조 안의 다른 노드들과의 연결 관계를 유지합니다.
키(Key) : 해당 노드가 담고 있는 데이터 또는 키 값을 저장합니다.
차수(Degree) : 이항 힙 노드의 차수 또는 레벨을 나타냅니다.
왼쪽 자식 포인터(Left Child Pointer) : 바로 아래 왼쪽 자식 노드의 주소를 저장하여, 자식 노드가 존재할 경우 이를 연결합니다.
형제 포인터(Sibling Pointer) : 바로 옆에 있는 형제(sibling) 노드의 주소를 저장합니다.
1. 단일 노드의 메모리 표현
2. 부모-자식 노드의 메모리 표현
3. 형제 노드의 메모리 표현
