[일반] 세그먼트트리 구현 질문

[익명(14.36)]

양놈사이트들 보다가 interval tree 라는걸 발견해서

구현해봤는데 시작 노드를 어떻게 잡아야 할지 모르겠더라구

내가 중간 값을 시작 노드로 지정해놨는데

만약 [1,10] , [2,8], [4,6] 이면 모든 노드를 방문해야되는데 쿼리는 왼쪽 혹은 오른쪽 트리로만 선택해서 내려가니까

발견을 못하던데 어뜨케 해야되지??

[시아닌(kimjg1119)]

뭔소리여 쿼리는 둘다내려가는데

[익명(14.36)]

// If left child of root is present and max of left child is // greater than or equal to given interval, then i may // overlap with an interval is left subtree if (root->left != NULL && root->left->max >= i.low) return overlapSearch(root->left, i); // Else interval can only overlap with right subtree return overlapSearch(root->right, i);

[익명(14.36)]

얘는 이렇게 되있던디

[0xrgb(0xrgb)]

둘다 겹치면 둘다 내려가는게 맞음

[익명(14.36)]

https://www.geeksforgeeks.org/interval-tree/

[0xrgb(0xrgb)]

그리고 이건 세그먼트 트리가 아님

[0xrgb(0xrgb)]

레인지트리라고도 부르는 건데 BBST까지 구현하려면 짜증나서 버린물건임

[하루룽(ailedear)]

헉 저게모야 clrs에 있던 이상한 트리가 저거인가