황민혁 트러블슈팅 모음집

주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 앞서 소개한 AVL 트리는 탐색과 관련하여 매우 만족스러운 성능을 보였습니다. 하지만 탐색 키의 비교 과정을 거치면서 찾는 대사에 가까워지는 방식이기 때문에, 원하는 바를 '단번에' 찾아내는 방식이라고 말하기는 어렵습니다. 때문에 상황에 따라서는 이러한 AVL 트리의 성능에 만족하지 못할 수도 있습니다. 그리고 이러한 상황에서 도입을 검토할 수 있는 자료구조가 바로 '테이블'입니다. 테이블도 자료구조인데 찾고자 하는 데이터를 '단번에' 찾을 수 있다니 믿기 어려우실 겁니다. 물론 테이블이라고 해서 정말로 찾고자 하는 데이터를 단번에..

주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. AVL 트리의 경우는 이론적인 이해만으로도 의미가 있기 때문에 시간이 부족하거나 더 이상의 코드 분석이 부담스럽다면 AVL트리의 이론적인 이해에 만족하고 다음 Chapter로 넘어가도 좋다고 합니다. 하지만 저는 AVL 트리를 구현하는 것까지 마무리해 보고자 합니다. AVL 트리도 이진 탐색 트리이므로, 앞서 구현했던 이진 탐색 트리의 파일들을 확장하여 AVL 트리를 구현하고자 합니다. 그리고 다음의 두 파일을 추가하여, 리밸런싱을 진행하는데 필요한 도구들을 선언하고 정의하겠습니다. AVLRebalance.h 리밸런싱 관련 함수들의..

주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 이진 탐색 트리의 탐색 연산은 다음과 같은 시간 복잡도를 가집니다. 위의 빅-오는 자료구조에서 가장 이상적인 형태입니다. 그런데 이런 이진 탐색 트리는 다음과 같이 균형이 맞지 않을수록 다음과 같은 시간 복잡도를 보입니다. 위의 트리는 1부터 8까지의 숫자를 순서대로 입력했을 경우의 이진 탐색 트리입니다. 분명 트리이지만 그 형태는 차라리 연결 리스트와 같습니다. 똑같은 데이터를 입력하지만 5부터 시작해서 순서대로 입력할 경우 트리는 다음과 같은 구조를 가지게 됩니다. 똑같은 데이터를 똑같은 순서로 입력했고, 오로지 첫 시작 데이터..

주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 이진 탐색 트리의 삭제 과정이 복잡하게 느껴지는 이유는 고려해야 할 예외상황이 많고, 따라서 일관적인 삭제 과정을 구현하지 못한다는 데에 있을지도 모릅니다. 그래서 이진 탐색 트리의 삭제 과정은 어떤 과정들을 거쳐야 하는지 정리해놓고 구현하는 것이 편합니다. 앞서 이진 탐색 트리의 삭제 과정을 열심히 설명했었는데 이진 탐색 트리의 삭제 과정은 크게 세 가지의 경우에 따라 달라짐을 알 수 있었습니다. 삭제 노드에 서브 트리가 없는 경우 삭제 노드에 서브 트리가 하나 이상 있는 경우 삭제 노드가 루트 노드인 경우 이진 탐색 트리의 삭제..