공부하는 스누피

이진 탐색 트리가 편향 트리이면 최악의 경우 O(h)의 시간복잡도를 가진다. 항상 O(logh)의 시간복잡도를 유지하려면 트리의 균형을 맞추어야 한다. AVL 트리는 균형 잡힌 트리 중 하나이다. AVL 트리에서는 균형의 정도를 표현하기 위해 균형 인수를 사용한다. 균형 인수는 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이이다. 균형을 잡기 위해 트리를 재조정할 때, 균형 인수의 절댓값이 크면 클수록 트리의 균형이 무너진 상태이다. 균형 인수의 절대값이 1 이하여야 균형 잡힌 트리라고 할 수 있다. 트리의 균형을 잡는 방법은 Rebalancing, Refactoring 등으로 부른다. 재조정이 필요한 상태는 크게 4가지이다. 1) Left Left 상태 루트 노드의 균형 인수가 +2인 경우. 왼쪽 서브..

해시는 키(key)와 값(value)이 한 쌍을 이루는 자료구조입니다. 원리가 간단하기 때문에 복잡한 알고리즘 없이도 탐색이 가능하다는 장점이 있고, 자료구조에서 중요하게 다루는 부분은 아니라 정확한 의미를 모르고 지나가기 쉽습니다. 사전은 해시와 원리가 비슷해 예시로 많이 쓰이고 있습니다. 사전은 단어와 뜻으로 이루어져 있습니다. 사용자는 단어의 뜻을 알기 위해 단어가 어디에 위치했는지 찾아봅니다. 각 단어의 뜻은 단어 바로 옆에 적혀 있기 때문이죠. 여기서 단어는 뜻을 찾기 위한 '주소'라고 보면 되겠습니다. 같은 단어가 여러개 있다면, 거기에다 흩어져 있다면 뜻을 찾기 힘들어 사전의 의미가 없어집니다. 물론 실제 사전은 알파벳순으로 정렬되어 중복된 단어가 있어도 크게 불편하지 않지만, 해시는 그렇지..