알고리즘 인덱스 트리, 세그먼트 트리

알고리즘

백엔드담당자 2021. 7. 30. 10:09

인덱스 트리 개념설명

세그먼트 트리 개념설명

인덱스 트리 vs 세그먼트 트리

인덱스 트리: 리프노드를 모두 채워서 만듦. 특정 인덱스(node)로 지정 탐색이 가능. 업데이트도 지정 업데이트 가능(리프노드부터 업데이트 가능)

세그먼트 트리: 필요한 리프노드만 채움. 불완전 트리라서 특정 인덱스(node)로 지정 탐색이 어려움. 업데이트도 지정 업데이트가 불가능(루트노드부터 업데이트 필요)

=> 문제에서 인덱스가 주어지는 경우 인덱스 트리를 사용하는 것이 용이

=> 구간 업데이트가 빈번한 경우 세그먼트 트리를 사용하는 것이 용이 (인덱스 트리는 시간초과 가능성)