해쉬(Hash)
해쉬는 'key'와 'value'를 저장하여 빠르게 데이터를 받아오고 업데이트하고 싶을 때 사용하는 자료구조이다.
해쉬 테이블의 내부 구현은 키를 해쉬함수를 통해 임의의 값으로 변경한 뒤 배열의 인덱스로 변환하여 해당하는 값에 데이터를 저장한다.
이때 같은 인덱스 값이 나와 충돌을 일으킬 수 있는데,
첫번째 해결방법은 인덱스 내에서 LinkedList 방식을 사용하는거다.
이 방식을 체이닝(Chaining)이라고 한다.
아래 이미지를 보면 이해할 수 있을거다.
이미지 출처
두번째 해결 방법은 배열의 다음 남는 공간에 넣는것이다.
이 방식은 개방 주소법(Open Addressing)이라고 한다.
트리(Tree)
트리는 위 혹은 아래로 뻗어있는 계층형 비선형 자료 구조이다.
큐와 스택은 선형구조(데이터들을 순차적으로 나열)이다.
Node: 트리에서 데이터를 저장하는 기본 요소
Root Node: 트리 맨 위에 있는 노드
Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
Child Node: 어떤 노드의 하위 레벨에 연결된 노드
Leaf Node(Terminal Node): Child Node가 하나도 없는 노드
Sibling: 동일한 Parent Node를 가진 노드
Depth: 트리에서 Node가 가질 수 있는 최대 Level트리의 종류는 이진트리 / 이진탐색트리 / 균현트리 / 이진 힙 등 다양하게 있다.
이진트리는 자식노드를 최대 2개까지 가질수있는 특징이 있고,
완전 이진트리는 노드를 삽입할때 최하단 왼쪽노드부터 차례대로 삽입해야 하는 특징이 있다.
트리를 구현할 때는 편의성을 위해 0번째 인덱스를 사용하지 않고 [None]을 넣어놓는다. 그렇게 하면
1. 현재 인덱스 2 -> 왼쪽 자식의 인덱스
2. 현재 인덱스 2 + 1 -> 오른쪽 자식의 인덱스
3. 현재 인덱스 // 2 -> 부모의 인덱스
이런식으로 부모,자식 인덱스를 찾는게 쉽기 때문이다.
완전 이진트리의 높이는 0층 = 1개, k층부터는2^k개 이다.
모든 노드가 꽉차있는 경우에는 2^(h + 1) - 1 로 노드의 개수를 구할 수 있다.
이진트리의 높이는 최대로 해봤자 O(log(N))이다.
