Gidhub BE Developer

m-원 탐색 트리

2018-06-13
goodGid

m-원 탐색 트리

  • 이원 탐색 트리보다 분기율을 높이면 : m개 서브트리

  • 장점
    트리의 높이가 감소 (특정 노드의 탐색시간 감소)

  • 단점
    삽입,삭제 시 트리의 균형 유지 위해 복잡한 연산 필요


m-원 탐색 트리의 성질



m-원 탐색 트리의 분석

  • m-원 탐색 트리 탐색시간 : 탐색 경로 길이(높이)에 비례

    • 각 레벨에서는 한 개의 노드만 탐색

    • 분기율(m)을 최대로 하면 트리의 높이가 낮아짐

  • Point가 m개
    Key는 m-1개


Back : B-트리

Comments

Content