m-ary 나무

컴퓨터 과학에서 m-ary 트리는 일반적으로 다음과 같은 방식으로 계층적으로 표현되는 노드의 모음으로 정의됩니다.

• 트리는 루트 노드에서 시작됩니다.
• 트리의 각 노드는 하위 노드에 대한 포인터 목록을 유지 관리합니다.
• 자식 노드의 수가 m보다 작거나 같습니다.

m-ary 트리의 일반적인 표현은 자식을 저장하기 위해 m 참조(또는 포인터)의 배열을 구현합니다(m은 자식 수의 상한선입니다).

m-way 검색 트리

ㅏ. 비어 있거나

비. b(1<=b

• k가 T0의 키이면 k <=k1
• k가 Ta의 키이면(0
• k가 Tb의 키이면 k> kb 및
• 모든 Ta는 비어 있지 않은 m-way 검색 트리이거나 모든 Ta는 비어 있습니다.

m-ary 나무의 이미지

n 노드와 관련된 완전한 m-ary 트리의 높이는 천장(log_m n).

차수가 m인 B-트리는 m-way 트리입니다.

ㅏ. 모든 잎은 같은 수준에 있어야 하며

비. 루트와 잎을 제외한 모든 노드는 최소 m/2 자식과 최대 m 자식을 가집니다. 루트에는 최소 2명의 하위 항목과 최대 m개의 하위 항목이 있습니다.