[BOJ] 백준 [2957] 이진탐색트리 JAVA

[BOJ] 백준 [2957] 이진탐색트리 JAVA

https://www.acmicpc.net/problem/2957

이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다. 만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다

2957번: 이진 탐색 트리

평범한 이진트리 만드는 문제이다.

하지만 시간제한과 메모리에 비해 주어지는 N을 보니 곱해 통과하지 않을듯 하다 .. 결국 시간초과

왜 ..? 보통 노드의 수를 N이라고하면 탐색하는데 걸리는시간은 O(logN)이다.

하지만 만약 연속된 수만 나와서 편향된 트리가 만들어진다면 .. ? => O(N)

편향된 트리가 되지 않게하기 위한 균형잡힌 트리가 있다. => Red-black 트리.

이 트리는 삽입하려는 노드의 삼촌노드( 부모의 부모의 자식) 를 보고 편향되지 않게 균형을 맞춰주기때문.

그런데 우리가 흔히 쓰는 컬렉션도 위와같은 균형트리구조를 쓰는 컬렉션이있다.

TreeSet 이나 HashMap같이 ..

이중 TreeSet의 컬렉션을 이용해서 간단하게 해보자.

TreeSet 의 내부메소드 중에 lower , higher 가 있는데 , 이 메서드는 파라미터로 특정 값을 기준 으로 받고

이 기준에서 봤을때 제일 가까운(자식or부모) 값을 return 해준다. 이게 무슨 말이냐면

key를 기준으로 해서 제일 가까운 수를 반환 해준다는 것. 가령 1~10 까지 트리에 저장되있다고 가정하고

key가 5인 이진트리의 왼쪽자식은 4, 오른쪽자식은 7 이라고 했을 때

lower(5) 로 던져주면 4를 , higher(5)를 던져주면 7을 리턴해준다는 뜻.

from http://katastrophe.tistory.com/81 by ccl(A) rewrite - 2021-11-11 16:00:56