이진탐색트리에서
연분홍
2024.12.07
데이터값이 정수로 이루어진 이진탐색트리가 있다고 가정하고.
특정 정수를 키보드로부터 입력받아서
그 정수보다 크거나 작은 값들을 출력하려고할때.
이진탐색트리를 전위순회를 하든, 후위순회를 하든, 중위순회를 하든, 트리의 모든 노드를 들린다음 입력받은 값과 비교해서 참일경우 출력하는 방법이 정석적인 방법인가요?
아니면 좀더 나은 방법이나 정석적인 방법이 있나요?
-
총알탄 2024-12-07
정렬일 경우를 기준으로...
중위순회로 큰값은 upper bound까지 왼쪽자식먼저, 작은 값은 lower bound까지 오른쪽자식먼저 탐색해나가면 원하는 값들만 구할 수 있습니다... -
LimeTree 2024-12-07
..............4
....3...................7
.1.....2.............5....9 -
찬슬 2024-12-07
이진트리로 하는 이유가 검색을빠르게 하기위해서 이기때문에..
보통 이진트리가 같는 값들은 루트를 기준으로 작은값은 왼쪽 큰값은 오른쪽에 위치하게됩니다.
같은값도 갖지게 합니다.
그렇게 레벨이 증가할때도 똑같이 부모노드보다 작은값은 왼쪽 큰값은 오른쪽으로 하게되면...
검색시 루트보다 큰가 작은가 같은가 비교하고
작은가 큰가 비교하고....... 이런식으로 비교해서 같으면 출력하고 아님 못찾은거고...
이런식이기때문에 모든 노드를 거칠 필요가없습니다.