이진 트리(Binary Tree)

트리는 계층형 자료구조 입니다.
이진 트리는 각각의 노드가 최대 2개의 자식을 가질 수 있습니다.
결과적으로 각각의 노드는 데이터와 왼쪽 자식, 오른쪽 자식을 가질 수 있습니다.

이진 트리의 특징들

1. 트리의 레벨에 대하여 노드의 최대 갯수는 2^l 입니다.(l은 레벨)
2. 트리의 높이에 대하여 최대 노드는 2^(h+1) - 1 입니다.(h는 높이, 높이는 루트 노드에서 리프 노드까지 도달하는데 필요한 최대 간선 수)

이진트리의 연산들

1. 삽입
2. 삭제
3. 검색
4. 순회
5. 트리의 높이 구하기
6. 트리의 레벨 구하기
7. 전체 트리의 크기 구하기

이진트리의 순회

1. 전위 순회: root->left child-> right child 순서로 트리를 순회
2. 중위 순회: left child -> root -> right child 순서로 트리를 순회
3. 후위 순회: left child->right child-> root 순서로 트리를 순회

이진 탐색 트리(Binary Search Tree)

이진 탐색은 빠른 검색이 주요 기능인 트리입니다.

이진 탐색 트리의 특징

1. 왼쪽 서브트리의 노드들은 현재 노드보다 무조건 작은 값을 가집니다.
2. 오른쪽 서브트리의 노드들은 현재 노드보다 무조건 큰 값을 가집니다.
3. 왼쪽 오른쪽 서브트리에 대해서도 1번과 2번 조건을 만족합니다.

이진트리의 연산들

1. 검색
2. 삽입
3. 삭제
4. N번째 값 찾기
5. BST트리인지 아닌지 확인

이진 힙(Binary Heap)

특별한 형태의 이진 트리입니다.

이진 힙의 특징

1. 완전 트리이다. 그래서 배열로도 구현 가능하다.
2. 최소 힙과 최대 힙이 있다. 최소 힙은 현재 노드가 왼쪽 오른쪽 서브트리보다 작은 값을 가지며 서브트리에서도 똑같은 규칙이 적용된다. 최대 힙은 현재 노드가 왼쪽 오른쪽 서브트리보다 큰 값을 가지며 서브트리에서도 똑같은 규칙이 적용된다.

해슁(Hashing)

해슁은 키와 값을 매칭시켜 O(1) 시간 복잡도 만에 데이터를 찾을 수 있게 만들어 줍니다. 최악의 경우는 O(N)이 걸립니다.

좋은 해쉬의 특징

1. 입력에 대한 결과값이 똑같음
2. 효율적으로 값을 찾아냄.
3. 값이 골고루 퍼져 있음.
4. 충돌을 최소화 함.
5. 적재율이 높음.

해쉬 테이블

키에 매칭되는 값을 가지는 배열.

충돌 핸들링

충돌은 두 개의 서로 다른 키가 같은 배열 공간을 가리킬 때 생김.

체이닝

충돌을 방지하기 위해 배열 공간에 하나의 값만 저장하는 것이 아니라 링크드 리스트나 배열을 이용하여 여러 개의 값을 저장할 수 있게 만드는 것