Graph이란
그래프! 뭔가 정보를 효과적으로 전달할때 사용하는 시각적 지표? 라고알고있습니다만
비슷한 개념이지만 역시 머리가 좀아픕니다
이해한걸 풀어보자면 아래와 같습니다
점을 정점으로(vertex) 이어지는 선을 간선으로(edge) 라고 부릅니다
그래프의 종류는 여러가지 있습니다. 다 이해해서 외워야 될까요? 근대 이름만보면 어느정도 이해가됩니다 함께 보시죠
무향 그래프(undirected graph) 는 보시면 un이 붙었기때문에 뭔가 아니거나 없습니다
두 정점이 단방향, 즉 한쪽의 머리만있는 화살표로 표현된 간서이 있는것입니다
진입차수(in-degree), 진출차수(out-degree) 진입하고 나가는 긍까, 화살표의 세모부분이 나에게 향해있으면 진입 나가는거면 진출?
인접 두 정점간에 간선이 있다면 두 정점은 인접한 정점, 행렬간에 간선이 있다면 인접 행렬입니다. 인정행렬에서 중요한점은 가장 빠른 경로를 찾고자할때 사용합니다 이러한 성질을 이용하여 정점을 나열해서 메모리를 효율적으로 사용한 것이 인접 리스트입니다.
자기 루프 정점에서 진출하는 간선이 곧 바로 자기 자신에게 향해져있는 모양새를 자기 루프를 가졌다 라고 합니다
Tree란?
트리라고해서 저는 위로뻗는 생각을 했습니다 하지만 내용을 보고 아래로 뻗은, 어찌보면 뿌리같다는 생각을 했습니다 가장위에있는 root로 부터 여러개의 node들(뿌리)로 뻗어져 내려갑니다. 여기서 중요한 개념은 아래와 같습니다.
1. 데이터가 바로 아래에 있는 하나 이상의 데이터에 단 방향으로 연결되는 계층적 자료구조라고 정의 할 수 있다.
2. 하나의 뒤에 여러개의 데이터가 존재할 수 있는 비선형 구조라고 볼 수 있기 때문에 사이클은 없다 자식노드가 없다면 리프노드라고 부른다.
3. 이런 트리구조의 데이터는 높이와 길이를 구할 수 있다. 루트로 부터 찾고자하는 노드까지의 거리를 레벨이라고 부르고 특정 노드부터 시작하여 루트까지의 레벨을 노드의 깊이라고 표현한다.
Binary Search Tree (이진 탐색 트리)
위에 말한 트리구조에서 자식 노드가 최대 두개인 노드들로 구성된 트리를 이진 트리라고 합니다. 종류는 아래와 같습니다.
완전 이진 트리 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.
정 이진 트리 각 노드가 0개 혹은 2개의 자식 노드를 갖습니다.
포화 이진 트리 정 이진 트리이면서 완전 이진트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져있는 트리입니다.
