C++ binary search tree (이진 탐색 트리) 구현, AVL tree 개념

* 본문은 <C++로 구현하는 자료구조와 알고리즘>(범한서적주식회사, 2013)을 공부하면서 작성한 글입니다. 향후 객체지향 및 자료구조 수업을 들으며 정확한 + 최신 내용 이해를 반영하여 보완해 나갈 것입니다.

 

1. 이진 탐색 트리

아래 코드의 BinaryTree는 저번에 구현한 LinkedBinaryTree를 말한다.

 

2. AVL tree

극단적인 경우 이진 탐색 트리가 한쪽으로만 n개의 노드가 일렬로 늘어선 형태가 된다. 그러면 실행 시간이 O(n)이 되어 O(log n) 실행시간을 달성했다고 보기 어렵다. 이런 한계를 극복하기 위해 나온 것이 AVL tree다.

개념은 이 링크를 통해 공부하면 좋다. -> https://ratsgo.github.io/data%20structure&algorithm/2017/10/27/avltree/

이것 이상의 공부는 후에 수업 진도를 보고 결정.