Chapter 12. 균형 잡힌 이진 탐색 트리 : AVL 트리의 구현
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. AVL 트리의 경우는 이론적인 이해만으로도 의미가 있기 때문에 시간이 부족하거나 더 이상의 코드 분석이 부담스럽다면 AVL트리의 이론적인 이해에 만족하고 다음 Chapter로 넘어가도 좋다고 합니다. 하지만 저는 AVL 트리를 구현하는 것까지 마무리해 보고자 합니다. AVL 트리도 이진 탐색 트리이므로, 앞서 구현했던 이진 탐색 트리의 파일들을 확장하여 AVL 트리를 구현하고자 합니다. 그리고 다음의 두 파일을 추가하여, 리밸런싱을 진행하는데 필요한 도구들을 선언하고 정의하겠습니다. AVLRebalance.h 리밸런싱 관련 함수들의..
Chapter 12. 균형 잡힌 이진 탐색 트리: AVL 트리의 이해
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 이진 탐색 트리의 탐색 연산은 다음과 같은 시간 복잡도를 가집니다. 위의 빅-오는 자료구조에서 가장 이상적인 형태입니다. 그런데 이런 이진 탐색 트리는 다음과 같이 균형이 맞지 않을수록 다음과 같은 시간 복잡도를 보입니다. 위의 트리는 1부터 8까지의 숫자를 순서대로 입력했을 경우의 이진 탐색 트리입니다. 분명 트리이지만 그 형태는 차라리 연결 리스트와 같습니다. 똑같은 데이터를 입력하지만 5부터 시작해서 순서대로 입력할 경우 트리는 다음과 같은 구조를 가지게 됩니다. 똑같은 데이터를 똑같은 순서로 입력했고, 오로지 첫 시작 데이터..
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 이진 탐색 트리의 삭제 과정이 복잡하게 느껴지는 이유는 고려해야 할 예외상황이 많고, 따라서 일관적인 삭제 과정을 구현하지 못한다는 데에 있을지도 모릅니다. 그래서 이진 탐색 트리의 삭제 과정은 어떤 과정들을 거쳐야 하는지 정리해놓고 구현하는 것이 편합니다. 앞서 이진 탐색 트리의 삭제 과정을 열심히 설명했었는데 이진 탐색 트리의 삭제 과정은 크게 세 가지의 경우에 따라 달라짐을 알 수 있었습니다. 삭제 노드에 서브 트리가 없는 경우 삭제 노드에 서브 트리가 하나 이상 있는 경우 삭제 노드가 루트 노드인 경우 이진 탐색 트리의 삭제..
Chapter 11. 이진 탐색 트리
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 이진 트리의 구조를 보면, 트리는 탐색에 효율적이라는 사실을 쉽게 알 수 있습니다. 이진 트리에 저장된 데이터의 수가 10억 개 수준에 이른다 해도 트리의 높이는 30을 넘지 않기 때문입니다. 예를 들어서 연결 리스트에 10억 개의 데이터가 저장되어 있다고 가정해 보겠습니다. 그리고 찾고자 하는 데이터가 이 리스트의 정중앙에 위치한다는 정보를 얻었다고 가정해 보겠습니다. 이는 분명 유용한 정보입니다. 하지만 이러한 정보를 가지고 있음에도 불구하고 데이터에 이르기 위해서는 약 5억 개의 노드를 지나야 합니다. 반면 이진 트리의 경우에..
Chapter 11. 탐색의 이해와 보간 탐색
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 우리는 이전에 '순차 탐색'과 '이진 탐색'에 대해 배웠습니다. 따라서 이번에 탐색에 대해 배운다고 하면 순차 탐색이나 이진 탐색 이외의 다른 탐색 알고리즘들을 배울 것이라고 생각하기 쉽습니다. 하지만 이번에 배울 탐색에 대한 내용은 사실 '트리'에 대한 뒷 이야기에 더 가깝습니다. 탐색은 굳이 따지자면 알고리즘보다는 자료구조에 더 가까운 주제입니다. 왜냐하면 효율적인 탐색을 위해서는 효율적인 탐색을 가능하게 하는 효율적인 저장 방법에 대해 필수적으로 고민해야 하기 때문입니다. 그런데 효율적인 탐색이 가능한 가장 대표적인 저장 방법..
Chapter 10. 복잡하지만 효율적인 정렬 알고리즘
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 앞서 단순한 정렬 알고리즘으로 버블 정렬, 선택 정렬, 삽입 정렬에 대해 알아보았습니다. 세 정렬 방법 모두 성능이 좋지 못한 정렬 알고리즘이라는 것을 알 수 있었습니다. 물론 데이터의 수가 적은 경우에는 간단하게 사용할 수 있는 좋은 알고리즘이지만 데이터의 수가 많아지면 이보다 더 효율적인 알고리즘이 필요하게 됩니다. 이번에 소개하는 알고리즘이 바로 그러한 알고리즘들입니다. 우리는 이전에 '힙'에 대해 배웠습니다. 바로 이 힙을 이용한 정렬 방법이 '힙 정렬'입니다. 힙에 대해서는 앞서 설명했기 때문에 다음의 예제만 보아도 쉽게 ..