잘 까먹는 자료구조들

Balanced Tree

왼쪽과 오른쪽의 자식 수가 같거나 하나의 차이만 나는 것

 

Binary Search Tree

이진탐색을 할 때 사용되는 트리로 부모 노드의 오른쪽에는 부모노드보다 큰 수, 왼쪽에는 작은 수가 들어간다.

 

Heap

최대힙, 최소힙이 있는데 모두 Root가 각각 최대이거나 최소이다. 즉, 가장 마지막으로 Numbering되는 자식이 최소이거나 최대이다.

삽입 연산 시에는 트리의 가장 마지막 자식 다음에 넣고 부모 노드와 하나씩 비교 / 스왑해가면서 자기 자리를 찾는다.

삭제 연산 시에는 루트값을 삭제하고 가장 마지막 자식을 루트에 넣은 후 하나씩 비교하면서 트리를 정립한다.

 

이때 힙과 BST의 차이는 힙은 맨 위가 max 혹은 min이라는 것 외에 정렬이 되어있지 않지만 BST의 경우는 정렬되어있으며 root가 항상 중간 값이다. (이 때, 주의할 것은 평균값이 아니고 중간값이라는 것)