[24일차] Tree, Graph, BinSerachTree

유태형·2022년 5월 27일

Java 알고리즘 코드스테이츠

코드스테이츠

목록 보기

24/77

오늘의 목표

Tree
Graph
BinSearchTree

내용

Tree

Tree는 최상위 노드인 root에서 부터 사방으로 뻗어나가는 형태가 나무와 많이 닮아 있다고 하여 트리 구조라고 부릅니다.
최상단의 1개의 노드를 root, 마지막에 위치한 노드들을 leaf라고 부르고 root에서 leaf로만 움직이는 단방향 그래프입니다.

명칭	설명
Sibling	같은 부모를 둔 노드들 간 형제관계입니다.
Parent Node	계층관계에서 부모관계인 노드입니다.
Child Node	계층관계에서 자식관계인 노드입니다.
root Node	트리의 최상위 노드입니다. 부모노드가 존재하지 않습니다.
leaf Node	트리의 최하위 노드입니다. 제각각 깊이는 다를 수 있지만 자식 노드가 존재하지 않는 노드입니다.
깊이(Depth)	루트로부터 하위 계층의 특정 노드까지의 거리입니다.
레벨(Level)	같은 깊이를 가진 노드를 묶어 레벨이라고 부릅니다.
높이(Height)	가장 높은 깊이의 리프 노드부터 루트 노드까지의 거리입니다.
서브 트리(sub tree)	트리는 계층 구조를 가지고 있고 자식 노드에겐 또 다른 자식 노드가 있을 수 있습니다. 트리 안에서 작은 트리 구조를 갖춘 트리를 서브트리라고 부릅니다.

트리는 우리가 흔히 사용하고 있는 컴퓨터의 파일 시스템에서 찾아 볼수 있습니다. 리눅스를 예를들어 최상단 디렉토리인 루트'/'디렉토리로 부터 디렉토리 내부에 또다른 디렉토리나 파일이 있고 디렉토리가 존재하는 한 하위 계층의 디렉토리로 계속 이동할 수 있습니다.

Graph

수학이나 통계에서의 그래프틑 X축과 Y축을 기준으로 값이 X축의 증감에 따라 Y축이 어떻게 증감하는지 보여주지만 컴퓨터에서의 그래프는 점들과 선으로 이어진 관계를 표현한 자료구조입니다.

트리와 마찬가지로 여러개의 노드로 뻗어나갈 수 있지만, 트리와 다르게 여러 점에서 들어올 수도 있습니다. 또 싸이클(돌고 돌아 원래자리로 돌아옴)도 형성할 수 있는 점이 다릅니다.

점(vertex) : 데이터를 가진 하나의 독립적인 노드입니다.
간선(edge) : 노드와 노드를 연결하는 선입니다. 간선이 있다는건 관계가 존재한다는 뜻이며 간선에는 중요도 수치나, 방향을 설정할 수도 있습니다.

그래프의 표현 방법

그래프는 2가지 방법으로 표현할 수 있습니다.

2차원 배열로써 종과 횡을 from과 to를 구분하여 true나 false, 1과 0등으로 관계 여부를 표현할 수도 있습니다.

2차원 배열과 유사하게 List안에 또다른 List를 삽입하여 표현할 수도 있습니다. 해당 from리스트에 to노드의 존재여부로 관계를 표현할 수 있습니다.

배열과 리스트 모두 from노드와 to노드가 존재하는지 부터 확인을 주의해야 합니다.

용어	설명
인접 정점 (adjacent vertex)	하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻합니다.
가중치 그래프 (weighted Graph)	연결의 강도(추가적인 정보, 위의 예시에서는 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀져 있는 그래프를 뜻합니다.
비가중치 그래프 (unweighted Graph)	연결의 강도가 적혀져 있지 않는 그래프를 뜻합니다.
무(방)향 그래프 (undirected graph)	단방향(directed) 그래프로 구현된다면 A에서 B를 갈 수 있지만, B에서 A로 가는 것은 불가능합니다.(혹은 그 반대)
진입차수 (in-degree) / 진출차수 (out-degree)	한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냅니다.
인접 (adjacency)	두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점입니다.
자기 루프 (self loop)	정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현합니다. 다른 정점을 거치지 않는다는 것이 특징입니다.
사이클 (cycle)	한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현합니다.

BinarySearchTree

이진 트리	영어 표기	설명
정 이진 트리	Full binary Tree	각 노드가 0개 혹은 2개의 자식노드를 갖습니다.
포화 이진 트리	Perfect binary Tree	정 이진 트리이면서 완전 이진 트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다.
완전 이진 트리	Complete binary tree	마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽은 채워져 있어야 합니다.