기본적으로 해시테이블은 key가 해싱되서 메모리에 관리됨. 이때 해싱된 값이 같아서 서로 같은 메모리 공간을 차지하게 되는 충돌 문제가 생길 수 있음. 그래서 충분히 메모리를 할당시켜줘야 한다.
만약 해싱된 값이 중복된다면 이를 분리 연결법(Seperate) 혹은 개방 주소형(Open Adressing)으로 관리할 수 있다.
Tree : Graph와 비슷하지만 단방향이며 cyclic하지 않음.
용어
Tree가 값을 순회하는 방식은 크게 전위, 중위, 하위 순회로 나뉜다. 보통 순회하는 알고리즘을 짤 때 재귀 구조를 많이 사용하는 편이며 Stack을 통해서도 구현이 가능하다.
def dfs(node):
#print(node) 전위순회
dfs(node.left)
#print(node) 중위순회
dfs(node.right)
#print(node) 후위순회
전위 순회 : 부모 좌측 우측
중위 순회 : 좌측 부모 우측
하위 순회 : 좌측 우측 부모