이분탐색 트리에 대해서
-
이분탐색 트리의 경우, 편향트리가 만들어 질 수 있다.
-
생각해보면, 데이터를 정렬한 상태에서 mid 에 있는 값부터 넣게 되면,
이분탐색의 성능을 그대로 발휘 할 수 있다. -
하지만, 조건이 있따.
1.데이터가 정적이어야 함.
2. 정렬한 상태에서 해야 한다.
왜 정적이어야 하냐면?
-
1 2 3 4 5 6 ,을 위의 방식대로 넣었다고 하자.
-> 그러면 이분탐색 트리이지만, 데이터가 7,8,9,10 이런식으로 높은 값이 들어오면, 오른쪽으로 편향된 트리가 만들어진다. -
이때는 어쩔수 없이 avl 트리, 등 트리를 회전시켜야만 함.
int* 의 참조 타입.
정답 코드
https://school.programmers.co.kr/learn/courses/30/lessons/42892
🔥🔥🔥