힙이란
힙이란
완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어졌고, 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 입니다.
힙의 삽입, 삭제
힙의 삽입
1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입합니다.
2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킵니다.힙의 삭제
1. 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제됩니다.
-> 최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것 입니다.
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져옵니다.
3. 힙을 재구성합니다.
힙이 할수있는 것을 균형 이진 트리가 할수 있지않나?
힙에서 할 수 있는걸 균형 이진 트리에서 할 수 있는 것이 맞고, 자가 균형 트리라는 가정하에 시간복잡도가 O(lg N)O(lgN)으로 동일한 것도 맞습니다. 그러나 힙은 균형 이진 트리보다 수행 속도도 빠르고, 구현도 쉽고, 공간도 적게 차지하기에 최소 혹은 최댓값의 확인/삭제만 필요할 떄에는 힙을 쓰는 것이 더 좋습니다.
힙은 삽입, 최솟(혹은 최댓)값 삭제가 O(lg N), 최솟(혹은 최댓)값 확인이 O(1)입니다.
즉, 최소 최대값 확인은 힙이 더 유리합니다.
이진 탐색 트리
이진 탐색 트리
이진탐색트리는 왼쪽 서브트리는 자기자신보다 모두 작고, 오른쪽 서브트리는 자기자신보다 모두 큰 특성을 유지하는 트리입니다.
이진탐색트리(Binary Search Tree)는 이진탐색(Binary Search)과 연결리스트(LinkedList)를 결합한 자료구조입니다. 이진탐색트리는 이진탐색의 효율적인 탐색능력과, 연결리스트의 장점을 모두 따와 노드의 탐색과, 삽입, 삭제연산에 대해 평균적으로 O(logN)의 시간복잡도를 보입니다. 이진탐색트리는 다음 네 가지 특성을 가집니다.
- 모든 노드의 키는 유일한 값을 가진다.(중복된 노드 X)
- 왼쪽 서브트리의 키들은 루트노드의 키보다 작다.
- 오른쪽 서브트리의 키들은 루트노드의 키보다 크다.
- 노드의 각 서브트리는 이진탐색트리이다.
이진 탐색 트리 삽입, 탐색, 삭제
이진탐색트리의 탐색은 간단합니다. 찾고자 하는 값을 현재 노드와 비교해가며 자식노드로 내려가 원하는 값이 있는지 확인합니다. 다음은 이진탐색트리의 탐색과정입니다.
1. 현재 노드의 값과 찾고자 하는 값이 일치하면 현재 노드를 반환합니다.
2. 현재 노드의 값보다 찾고자 하는 값이 크면 오른쪽 자식노드로 이동합니다.
3. 현재 노드의 값보다 찾고자 하는 값이 작으면 왼쪽 자식노드로 이동합니다.
4. 1 ~ 3 을 반복합니다.
이진탐색트리의 삽입은 탐색과 유사합니다. 다음은 이진탐색트리의 삽입과정입니다.
1. 현재 노드가 null 이면 현재 위치에 노드를 삽입합니다.
2. 현재 노드의 값이 삽입할 값과 일치하면 삽입하지 않고 false를 반환합니다.
3. 현재 노드의 값보다 삽입할 값이 크면 오른쪽 자식노드로 이동합니다.
4. 현재 노드의 값보다 삽입할 값이 작으면 왼쪽 자식노드로 이동합니다.
5. 1 ~ 4 를 반복합니다.
이진탐색트리의 삭제는 탐색과 삽입연산보다 까다롭습니다. 삭제할 노드의 자식노드가 없다면 노드를 지우기만 하면 되지만, 자식노드가 있을 경우, 부모노드와 자식노드를 연결해줘야 하기 때문입니다. 이 때 이진탐색트리의 성질을 유지한 채로 연결을 해줘야 합니다.
삭제할 노드를 대체할 노드는 삭제할 노드의 왼쪽 노드 중 가장 큰 노드, 혹은 삭제할 노드의 오른쪽 노드 중 가장 작은 노드를 선택합니다. 왼쪽 서브트리 중 가장 큰 노드는 모든 왼쪽 노드 중 가장 크며, 삭제할 노드의 오른쪽 서브트리의 모든 노드보다는 작기 때문에 삭제할 노드를 대체할 수 있기 때문입니다. 오른쪽 서브트리 중 가장 작은 노드도 이와 동일합니다.
다음은 이진탐색트리의 삭제과정입니다.
1. 삭제할 값을 가진 노드를 찾습니다.
2. 삭제할 노드가 존재하지 않으면 false를 반환합니다.
3. 삭제할 노드가 단말노드라면 삭제하고 true를 반환합니다.
4. 한쪽 서브트리만 존재할 경우, 삭제할 노드의 자식노드와 부모노드를 연결하고 true를 반환합니다.
5. 양쪽 서브트리가 모두 존재한다면, 삭제할 노드를 대체할 노드를 찾아 서브트리와 부모노드를 연결합니다.
자가 균형 트리
자가 균형 트리
삽입/삭제 시 자동으로 depth (루트로 부터 내려갈 수 있는 최대 레벨)를 최소로 유지하는 노드 기반 이진 탐색 트리 ( depth가 최소인 것은 Complete binary tree인 경우 ) 입니다.
AVL
AVL 트리란 한 쪽으로 값이 치우치는 이진 탐색 트리(Binary Search Tree, BST)의 한계점을 보완하기 위해 만들어진 균형 잡힌 이진 트리입니다. AVL은 항상 좌/우로 데이터를 균형잡힌 상태로 유지하기 위해 추가적인 연산을 진행합니다.
Red Black Tree
레드블랙 트리는 모든 노드를 빨간색 또는 검은색으로 색칠합니다. 그리고 연결된 노드들은 색이 중복되지 않도록 관리됩니다.
해시
해시
키값이 배열의 인덱스 값으로 사용하기에는 적당하지 않고, 키값의 범위가 매우 넓어서 매우 큰 배열이 필요한 문제를 해결하기 위해 해시를 사용합니다. 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할을 수행합니다.
충돌회피 방법
만약 서로 다른 두 개의 키가, 해쉬 함수를 통과하였는데, 그 결과가 같다면 이를 충돌이라고 합니다.
충돌이 많이 일어난다면, O(1)으로 값을 탐색할 수 있는 장점이 없어집니다. 해시 충돌을 최소하 하기 위해서 테이블의 크기를 소수로 사용해서 만들어야 합니다.
만약 충돌이 난다면, 해결하는 방법이 크게 2가지가 있는데, 개방 주소법과 분리 연결법이 있습니다.개방 주소법
- 배열만을 사용하며, 저장 인덱스가 겹칠 경우 해당 인덱스의 옆 인덱스에 저장하는 방식입니다.
- 옆에 인덱스와 데이터 충돌이 일어나면 다시 옆 인덱스에 저장합니다.
- 충돌 데이터가 많이 발생하면 성능에 심각한 문제가 발생합니다.
분리 연결법
- Hash Table 에 연결 리스트에서 사용하는 Node 객체를 저장합니다.
- Hash Table의 셀마다 연결 리스트를 하나씩 저장하고 충돌이 발생하는 데이터는 연결 리스트의 다음 노드에 추가합니다.
- 데이터를 검색할 때는 Hash Table의 인덱스를 찾은 후 셀에 연결된 리스트를 순차적으로 탐색하며 찾으려는 Hash Code 와 저장된 Node의 Hash Code를 비교하는 것입니다.
