(a,b)-나무

컴퓨터 과학에서 (a,b) 트리는 균형 잡힌 검색 트리의 일종이다.

(a,b)-나무는 모든 잎이 같은 깊이에 있고, 뿌리를 제외한 모든 내부 노드는 a와 b 자식 사이에 있으며, 여기서 a와 b는 2 ≤ a ≤ (b+1)/2와 같은 정수다.그 뿌리는, 만약 잎이 아니라면, 2살에서 2살 사이의 아이들을 가지고 있다.

정의

a, b는 2 ≤ a ≤ (b+1)/2와 같은 양의 정수가 되게 한다.다음 경우 뿌리 나무 T는 (a,b)-나무다.

• 뿌리를 제외한 모든 내부 노드에는 적어도 a와 b자녀가 있다.
• 뿌리에는 기껏해야 b자식이 있다.
• 뿌리부터 잎까지 가는 길은 모두 길이가 같다.

내부 노드 표현

a (a,b)-트리 T의 모든 내부 노드 v는 다음과 같은 표현을 가지고 있다.

• $\rho {\displaystyle {}_{}}$ ${\displaystyle v_{}}$ ${\$을(를) 노드 v의 하위 노드 수로 설정하십시오$$.
• $S{\displaystyle {}_{}}$ ${\displaystyle v_{}}$[ ${\displaystyle 1}$… ${\displaystyle {}_{}}$ ${\displaystyle v_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle S_{v}[1\dots \rho _{v}]$를 하위 노드에 대한 포인터가 되게$$ 하라.
• $H{\displaystyle {}_{}}$ ${\displaystyle v_{}}$[ ${\displaystyle 1}$… ${\displaystyle {\rho }_{}}$ v${\displaystyle {}_{}}$- ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle H_{v}[1\dots \rho _{v}-1]$이(가$)$ $S{\displaystyle {}_{}}$ ${\displaystyle v_{}}$[ ${\displaystyle i}$ ${\displaystyle ]}$ ${\displaystyle H_{v$$}[$$i]$가 가리키는 하위 트리에서 가장 큰 키와$$ 같은 키의 배열일$$ 수 있도록 한다$.$

참고 항목

• B-트리
• 2-3나무
• 2-4 트리

참조

• 이 문서에는 NIST 문서의 공용 도메인 자료가 포함되어 있다.Black, Paul E. "(a,b)-tree". Dictionary of Algorithms and Data Structures.