오늘
- Tree
- Graph
- Binary Search Tree
Tree
tree는 나무를 거꾸로 뒤집은 모양을 가지고 있다.
Graph
자바에서 그래프는 이런 모양.
동그라미(점)를 정점이라고 표현.
선은 간선이라고 말한다.
양쪽다 화살표가 있으면 양방향 간선, 한쪽만 있으면 단방향 간선이다.
인접행렬
말 그대로 다른 정점과 인접해 있는지를 표현하는 것인데 , 2차원 배열로 나타낸다.
A의 진출차수 : 1개 (A -> K) = [0][2]
P의 진출차수 : 1개 (P -> A) = [1][0]
K의 진출차수 : 3개 (K -> P) , (K -> A) (K -> Z) = [2][1], [2][0], [2][3]
Z의 진출차수 : 2개 (Z -> A) , (Z -> K) = [3][0], [3][2]
언제 활용?
네비게이션 같이 최단 경로를 확인하고 싶을 때 자주 사용된다.
인접 리스트
인접행렬과 의미는 똑같다. 다만 나타내는 것이 리스트 형태로 나타내질 뿐.
A -> K -> null
P -> A -> null
K -> P -> A -> Z -> null
Z -> A -> K -> null
양방향 간선일 경우 순서를 크게 중요하지 않다고 한다. 하지만 항상 예외는 있다는 것을 기억해두자.
그리고 우선순위를 중요하게 다뤄야 한다면 queue같은 자료구조를 사용하자.
언제 활용?
메모리를 효율적으로 활용하고 싶을 때.
활용 예제
그래프는 길을 찾을 때 유용하게 사용 가능하다.
네비게이션.
Binary Search Tree (이진트리)
자식 노드가 두개로 구성된 트리.
종류
정 이진 트리 (Full binary tree)
각 노드가 0개 or 2개의 자식 노드를 갖는다.
포화 이진 트리(Perfect binary tree)
정 이진트리이면서 완전 이진 트리인 경우. 모든 리프 노드의 레벨이 동일하며, 모든 레벨이 가득 채워져 있는 트리
완전 이진 트리(Complete binary tree)
마지막 레벨을 제외한 모든 노든가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.
트리 순회
트리는 항상 왼쪽부터 오른쪽으로 순회한다.
전위순회
중위 순회
후위 순회
