자료구조-비선형

1. Tree 

---

• 부모 노드와 자식 조드간의 연결로 이루어진 자료 구조
• Heap: Priority Queue를 구현
  • complete binary tree : tree채워질 때 왼쪽부터 채워짐.
  • Max heap: 부모 노드는 자식 노드보다 항상 크거나 같은 값을 갖는 경우
  • Min heap: 부모 노드는 자식 노드보다 항상 작거나 같은 값을 갖는 경우
  • heap 정렬에 사용할 수 있음.
• Binary Tree: 부모노드에 자식 노드가 2개 이하인 트리
• Binary Search Tree
  • key의 중복을 허용하지 않음
  • 왼쪽 자식 노드는 부모보다 작은 값, 오른 쪽 자식 노드는 부모 노드보다 큰 값
  • 자료 검색에 걸리는 시간 log2(n)ㄷ
  • inorder traversal 탐색을 하게 되면 자료가 정렬되어 출력됨.
• jdk class: TreeSet, TreeMap(Tree로 시작하는 class는 정렬 지원)

 

 

2. Graph

---

• 정점과 간선들의 유한 집합 G=(V,E)
• Vertex: 여러 특성을 가지는 객체, 노드
• Edge: 객체들의 연결 관계를 나타냄. link
  
  • 방향이 있는 경우 없는 경우 있음.
• 구현 방법 : 인접 행렬(adjacency matrix), 인접 리스트(adjacency list) 
• 탐색 방법: BFS(Bread First Serach), DFS(Depth First Search)

 

3. Hashing

---

• 자료를 검색하기 위한 자료구조
• key에 대한 자료를 검색하기 위한 dictianry 개념의 자료 구조
• key는 유일하고 value를 쌍으로 저장
• index=h(key): 해시 함수가 key에 대한 index를 반환해줌. 해당 index에 저장하거나 검색
• 해시 함수에 의해 index 연산이 산술적으로 가능 O(1)
• 저장되는 메모리 구조를 hash table이라 함.
• jdk: HashMap, Properties