Algorithm/알고리즘 개념1 [JAVA] 세그먼트 트리 (Segment Tree) 세그먼트 트리 - 연속된 구간 또는 특정 구간 내 데이터에 대한 연산을 빠르게 구할 수 있는 트리- 리프노드에는 배열의 수 자체 저장 리프노드가 아닌 노드에는 왼쪽 자식노드와 오른쪽 자식노드의 합 저장- 리프노드를 제외한 다른 모드 노드는 항상 2개의 자식을 가진다- 어떤 노드의 인덱스가 n일때, 왼쪽 자식노드는 2n이고 오른쪽 자식노드는 2n+1 이다- Full Binary Tree 이다 (N이 2의 제곱근일 경우 Perfect Binary Tree)- 리프노드가 N개인 Full Binary Tree에는 리프노드가 아닌 노드가 N-1개 있으므로 필요한 노드 개수는 2N - 1개 이다 ✅ 참고사항 : 트리 개념- 이진트리 (Binary Tree) : 각 노드가 최대 2개의 자식 노드를 가지는 트리- .. 2024. 10. 21. 이전 1 다음
