[TIL] 05/24 항해99 16일차 - 이진탐색트리, 문제풀이

 

들어가며

갑자기 잘 쓰던 들어가며에 뭘 써야할 지 헷갈리기 시작했다. 원래 아무말이나 적었던거 같은데...

 

오늘도 열심히 잠을 잤으니 그 업보를 지금의 나에게 지우기로 하고 오늘의 TIL은 이진 탐색트리의 개념과 문제 풀이를 정리해보고자 한다!

 

---

이진 탐색 트리

이진 탐색 트리(BST, Binary Search Tree)란 이진 탐색(Binary search)과 연결리스트(Linked list)의 아이디어를 결합한 자료구조의 일종이다.

 

커리큘럼상 뒤에 배우게 될 이진탐색의 경우 소요되는 시간 복잡도는 O(log n)으로 빠르지만 삽입, 삭제가 불가능하다. 반면 연결리스트의 경우 삽입, 삭제에 필요한 시간 복잡도는 O(1)로 효율적이지만 탐색하는 데에는 O(n)가 소요된다.

 

이진 탐색 트리는 이진 탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안되었다.

 

 

특징

이진 탐색 트리는 다음과 같은 속성을 가지고 있다.

• 이진 탐색 트리의 노드에 저장된 key는 유일하다.
• 부모의 key가 왼쪽 자식 노드의 키보다 크다.
• 부모의 key가 오른쪽 자식 노드의 키보다 작다.
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

 

 

+

궁금했던 부분! - 이진 탐색 트리는 꼭 정렬된 배열으로만 만들 수 있을까?

이 부분은 궁금한 부분을 스스로 찾고 정리한거라 정확한 정보가 아닐 수 있습니다. 틀린 부분이 있다면 지적해주시고 걸러서 보시길 바랍니다!!

 

배열을 이진 탐색 트리로 만들 때의 이야기이다. 당연하게도 존재하고 있는 이진 탐색 트리는 완전히 정렬되어있지 않아도 위의 부모-자식간의 정렬 기준을 충족한다면 상관없다!

 

이진 탐색 트리는 이진 탐색 + 연결 리스트의 장점을 가지고 고안해낸 자료구조라고 설명했었다. 이 부분에서 힌트를 얻어낼 수 있는데, 이진 탐색은 정렬된 배열에서 타겟을 찾는 알고리즘이다. 이진 검색의 로그 마법을 적용한 이진 탐색 트리도 정렬된 배열을 가지고 만들 수 있다. 라는게 <파이썬 알고리즘 인터뷰 425p>에서 기술한 내용이다.

 

정리하자면 배열을 이진 탐색 트리로 만들 때는 정렬된 배열을 사용하자!로 할 수 있겠다.

 

궁금증에 도움을 주신 호균님께 감사!!

 

 

 

자가 균형 이진 탐색 트리

이진 탐색 트리가 효율적이고 좋은 녀석이긴 하지만 항상 그 시간 복잡도가 O(log n)인 건 아니다. 만약 트리의 모양이 균형을 제대로 이루지 못하면 O(n)에 근접한 시간이 소요될 수 있다.

 

위 그림 처럼 균형이 깨진 트리는 루트부터 맨 끝까지 차례대로 모두 탐색해야하므로 O(n)의 시간 복잡도를 갖는다. 이 상황을 해결하기 위해 고안된 것이 ‘자가 균형 이진 탐색 트리'이다.

 

자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)는 삽입, 삭제 시 자동으로 높이를 작게 유지하는 노드 기반의 이진 탐색 트리이다.

 

 

자가 균형 이진 탐색 트리는 최악의 경우에도 이진 트리의 균형이 잘 맞도록 유지한다. 균형이 잘 맞는다는 말은 높이를 가능한 낮게 유지하는 것이 중요하다는 얘기이다.

 

 

위의 균형/불균형 트리 예시 그림을 보면 균형이 맞는 트리는 노드 수가 훨씬 많음에도 불균형 트리보다 루트의 높이가 작다. 이처럼 루트의 높이로 불균형과 균형을 구분할 수 있다.

 

자가 균형 이진 탐색 트리의 대표적인 형태로는 AVL 트리와 레드 - 블랙 트리 등이 존재하는데, 특히 레드 - 블랙 트리는 효율성이 높아 실무에서도, 면접에서도 자주 쓰인다고 하니 꼭 잊지 말고 돌아와서 정리하자!

 

 

문제풀이

[leetcode] 226. 이진 트리 반전 (Invert Binary Tree)

[leetcode] 226. 이진 트리 반전 (Invert Binary Tree)

 

[leetcode] 108. 정렬된 배열의 이진 탐색 트리 변환 (Convert Sorted Array to Binary Search Tree)

[leetcode] 108. 정렬된 배열의 이진 탐색 트리 변환 (Convert Sorted Array to Binary Search Tree)

나오는 개념 - 이진 검색

 

---

마치며

오늘의 한마디 by 지은님 - 삽질을 즐기자!