자바의 비선형 자료구조

내가 잘 모르는 거 위주로 정리

이진 검색 트리

• 중복을 허용하지 않음
• 왼쪽 자식 노드는 부모 노드보다 작은 값, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가짐.
• 자료 검색에 걸리는 시간이 평균 log(n)
• 자료를 순서대로 넣지 않을 때 쓸만함.
• inorder traversal을 하면 자료가 정렬됨.
• 자바에서는 TreeSet, TreeMap 이 이걸 씀.
• 좌우를 거꾸로 넣으면 내림차순으로도 정렬할 수 있음.

그래프

• 점점과 간선의 유한 집합.
• 정점(vertex)
• 간선(edge)
• 인접행렬, 인접리스트로 구현할 수 있음.
• 탐색은 BFS, DFS를 이용함.

해싱

• 자료를 검색하기 위한 자료 구조
• 키에 대한 자료를 검색하기 위한 사전 개념의 자료 구조. (key, dictionary)
• key / value를 쌍으로 저장. key는 유일값임.
• 해시 함수에 key를 넣으면 index값을 반환해줌. 이 인덱스 위치에 자료를 저장하게 됨.
• 자바에서는 HashMap이 이 형태임.