switch

- 이진 탐색 트리 Binary Search Tree 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 이진트리이다. 각 노드의 자식이 2개 이하이며 탐색 효율이 높은 편이며 중복된 키를 허용하지 않는다. 삽입은 루트에서 시작해서 비교한다. 중간에 있는 노드를 삭제할 경우 해당 자식 노드를 삭제할 노드 위치로 옮기고, 자식이 두 개인 노드의 경우는 오른쪽 서브 트리 최솟값 또는 왼쪽 트리 최댓값 중 하나를 삭제 노드 위치로 옮긴다. - 시간 복잡도 삽입, 검색, 삭제가 모두 트리의 높이이다 트리가 균형상태인 경우 O(logN) 불균형 상태인경우 O(N) 만큼의 시간 복잡도를 갖는다. 트리가 편향되지 않기 위해서는 자가균형트리를 사용해야 한다.

- Heap이란.. 힙은 최댓값 혹은 최솟값을 빠르게 찾기 위한 이진트리이다. (이진 탐색 트리와는 다르게 힙 트리에서는 중복 값을 허용한다) 힙은 느슨한 정렬 상태(반정렬상태)를 유지하는데, 최소 힙의 경우 부모는 자식보다 작고, 최대 힙의 경우 부모는 자식보다 크다. - 힙의 삽입, 삭제 힙의 삽입 새 요소를 힙의 마지막노드에 이어서 삽입하고 부모 노드와 비교하여 교환하는 형식으로 이루어진다. 힙의 삭제 힙의 루트에서 삭제 후 가장 마지막 노드를 루트 노드 자리로 바꿔준다. 이후에는 삽입때와 마찬가지로 부모 자식 노드를 비교해준다. - 시간복잡도 힙의 삽입과 삭제는 힙의 높이만큼 O(logN)의 시간 복잡도를 갖고, 힙의 정렬의 시간 복잡도는 O(N*logN)이다. (전체 데이터 N * 삽입 시간 복..