#6-2-3 The Art of Computer Programming - 정렬과 검색

이번 절은 균형 트리에 대한 내용이다.

아무래도 트리 삽입 알고리즘은 입력 자료가 무작위 할 경우는 좋은 검색 트리를 만들지만

데이터에 따라 한쪽으로 치우친 검색 트리가 만들어 질 수 있다.

 

그렇기에 AVL트리라고 부르는 균형트리를 구성해서 검색한다.

 

트리를 막 회전하고 빼고 재조정하고 다시 연결하는 등등의 작업들을 한다.

예전에 한번 수업때 들었던 트리긴 한데.. 생각보다 좀 복잡해서 이해를 못했다.

물논 지금 다시 책을 읽어봐도 이해가 잘 안 된다.

 

여하튼 개념은 트리가 한쪽으로 치우칠 거 같으면 그걸 다시 조정해서 어떤 데이터를 검색하든지

검색 시간이 크게 차이가 안 나도록 만드는 방법이다.

 

근데 이것도 지난 절에 얘기했던 것 같이

자주 데이터가 바뀌는 경우에는 데이터를 검색하는 시간보다 관리하는 시간이 더 들지 않을까..?

 

그런데도 실무에서 쓰이는 개념이라고 하면.. 관리 시간에 대한 문제는 해결된 걸까..

 

여러 가지 의문점을 남기며 이 절을 마친다.