Tree 란

안녕하세요.

오늘은 자료구조 트리(Tree)에 대해 포스팅 합니다.

필수적으로 알아야 할것들만 정리하였습니다.

트리구조에 대해 대략적으로 설명하므로, 특정 용어나 개념들은 따로 찾아봐야 합니다.

 

트리(Tree) 란

위 본문의 그림과 같이 노드간선으로 이루어진 것을 그래프(Graph) 라고 합니다.

트리는 이러한 그래프 의 일종 입니다. 아래의 규칙을 따르는 그래프트리라고 일컫습니다.

사실 규칙을 외울 필요는 없고, 이런 형태구나 정도로 기억하면 될 거 같습니다.

 

트리 규칙

  • 특정 노드는 오직 하나의 조상 노드와 N 개의 자식 노드와 연결됩니다.

    • 특정노드에서 조상노드, 자식노드는 레벨의 차이가 반드시 1이어야 합니다.
    • C 노드는 하나의 조상 노드인 A와 2개의 자식 노드인 G , H와 연결됩니다.
  • 여러 노드가 한 노드를 가리킬 수 없습니다.
  • 노드와 노드를 잇는 길(간선)이 하나만 존재합니다.

 

또한 트리는 다음과 같은 특징들을 가집니다.

높이

트리는 루트로 부터 레벨 을 셀 수가 있는데 이때 최대 레벨의 값을 높이라 부를 수 있습니다.

따라서, 예제의 트리의 높이는 3입니다.

 

말단 노드(리프 노드)

자식이 없는 노드를 말단 노드 또는 리프 노드라 일컫습니다.

 

형제 노드

같은 부모를 가지는 노드들을 형제(sibling)노드라 부릅니다.

 

서브 트리

트리안에서 특정 범위를 묶어 하나의 작은 트리를 구성 할 수 있습니다.

예제 트리의 빨간 박스, 파란 박스 와 같은 예시처럼 묶을 수 있으며 이를 서브 트리라 일컫습니다.

 

이진트리 (Binary Tree) 란

트리의 특정 노드는 자식의 개수를 제한 없이 가질 수 있는데요.

이때, 최대 2개의 자식 노드만 가질 수 있다 는 조건을 추가한것을 이진트리라고 부릅니다.

쉽게 말해, 노드가 왼쪽 자식오른쪽 자식을 갖는 특징을 가집니다.

예제의 트리도 이진트리라 부를 수 있습니다.

 

이진트리구조를 갖추면, 해당 구조가 제공하는 연산의 이점들이 존재합니다.

예를들면, 노드의 개수를 알면 높이를 알 수 있습니다.

레벨(N)당 노드의 개수는 2^N 이기 때문입니다.

 

대표적으로 사용되는 연산은 탐색입니다.

너무나도 유명한 이진 탐색 트리 를 구성할 수 있습니다.

 

특정 조건이 추가된 이진 트리들이 있습니다.

완전 이진트리

  • 모든 레벨에서의 노드가 꽉차 있어야 합니다.

  • 예외적으로, 마지막 레벨에서의 노드는 꽉차 있지 않아도 되지만 왼쪽에서 차례대로 채워져야만 합니다.

  • 예시 트리도 완전 이진트리 입니다.

  • 예시 트리에서 N 만 없애거나, (M, N) 을 없애거나, (L, M, N)을 없앤 케이스도 완전 이진트리입니다.

전 이진트리

  • 특정 노드의 자식이 0개 또는 2개로만 구성되어 있는 트리를 의미합니다.
  • 예시 트리에서 (G, H)를 없애거나, (E, F, K, L, M, N)을 없앤 케이스를 전 이진트리로 볼 수 있습니다.

 

포화 이진트리

  • 모든 말단 노드가 같은 높이에 있어야 합니다.

    • 예를들어, (E, F, K, L, M, N)을 없앤 케이스를 전 이진트리형태는 말단 노드인 B가 다른 말단 노드인 G와 레벨이 동일하지 않습니다.
  • 마지막 레벨에서 노드의 개수가 최대가 되어야 합니다.

  • 예시 트리도 포화 이진트리라 부를 수 있습니다.

 

이진 탐색트리

  • 노드의 자식은 아래의 규칙을 따릅니다.

    • 오른쪽 노드의 값 < 현재 노드의 값 < 왼쪽노드의 값
  • 값을 이용한 규칙을 통해 구조를 쌓으면 추후 이진 탐색을 사용할 수 있습니다.

다음 포스팅에서 자세히 다룰 예정입니다.

 

이진트리 순회

이진트리를 연산하기 위해서는 순회는 빼놓을 수 없습니다. 방문하지 않으면 값을 알 수 없기 때문입니다.

순회는 많이 알려진 방법인 너비우선탐색(BFS), 깊이우선탐색(DFS) 으로 나눌 수 있습니다.

 

너비우선탐색(BFS)

레벨순으로 차례대로 탐색합니다.

예시 트리를 기준으로 설명드리자면, 아래와 같이 탐색합니다.

Root > A > B > C > D > E > F > G > H > I > J > K > L > M > N

 

깊이우선탐색(DFS)

탐색 방법 3가지가 존재합니다.

기본적으로 왼쪽 자식 노드에서 오른쪽 자식 노드로 순회를 한다고 가정(B -> C)하고 현재 노드(A)가 방문되는 순서를 기억하면 좋습니다.

  • 전위 순회 (pre-order traversal)

    • 현재 노드(A)가 첫번째로 방문 됩니다.
    • B ->C는 고정이므로 첫번째로 방문되려면 맨 앞에 배치 되어야 합니다.
    • A -> B -> C
  • 중위 순회 (in-order traversal)

    • 현재 노드(A)가 중간에 방문 됩니다.
    • B -> A -> C
  • 후위 순회 (post-order traversal)

    • 현재 노드(A)가 마지막에 방문 됩니다.
    • B -> C -> A

 

위 예시는 서브 트리가 존재하지 않는 트리인 경우 입니다.

만약 서브 트리가 존재한다면 어떻게 방문할까요?

이때는 서브 트리를 하나의 노드라 생각하고 방문합니다.

다음의 트리를 이용하여 전위 순회로 알아봅시다.

 

해당 예시의 서브 트리는 (B, D, E) 입니다.

STEP1: 서브 트리를 하나의 노드(BB)로 치환하여 전위 순회를 진행합니다.(A -> BB -> C)

STEP2: BB도 트리이므로 내부적으로 순회를 똑같이 진행합니다. (B -> D -> E)

STEP3: 서브 트리 순회 결과를 치환한 노드BB에 반영합니다. (A -> B -> D -> E -> C)

 

최초 분문의 예시를 각 방법으로 순회 하면 다음과 같습니다. (ROOT의 위치를 살펴보세요.)

전위 순회 : ROOT > A > C > G > H > D > I > J > B > E > K > L > F > M > N

중위 순회 : G > C > H > A > I > D > J > ROOT > K > E > L > B > M > F > N

후위 순회 : G > H > C > I > J > D > A > K > L > E > M > N > F > B > ROOT

 

오늘 준비한 내용은 여기까지 입니다.

읽어주셔서 감사합니다.

'자료구조' 카테고리의 다른 글

[자료구조] B 트리  (0) 2021.07.29
[자료구조] 이진탐색트리  (1) 2021.07.12

포스팅이 도움 되셨다면, 커피 한잔 후원해주세요!
더 좋은 포스팅 작성에 큰 힘이 됩니다.

Buy me a coffeeBuy me a coffee

안녕하세요. Mommoo 입니다.


앞으로 버블 정렬,선택 정렬, 삽입 정렬, 힙 정렬, 퀵 정렬을 만들어 볼텐데요,


이러한 정렬 들을 만들기 쉽게, 디버깅을 편하게 하기 위해 조상 클래스 Sort를 만들어 보고자 합니다.


기본목표는 아래와 같습니다.


    • 정렬들간의 비교분석을 위해 같은 배열 데이터를 참조하게 한다.
    • 데이터의 갯수만 변경하면 데이터가 갯수에 맞게, 랜덤값이 자동적으로 생성되게 한다.
    • 정렬들간의 비교를 위하여 공통된 행위 설계. ( sort할때 걸리는 시간, sort가 성공했는지 여부, 규격화된 디버깅 설계 등등...)
    • Comparable 인터페이스를 구현 해, Sort클래스를 상속받는 수 많은 정렬 클래스들이 시간 순으로 랭크화 하게 한다.


먼저 완성된 소스입니다.


특이점등을 설명해드리자면...


▶  6번의 DATA_LENGTH 변수는 추후에, 데이터 갯수를 표시하기 위해 public으로 공개했습니다.


▶  16번의 static 초기화 부분에서는 자동적으로 랜덤 값을 넣어주며, sort가 성공했는지 여부를 알기 위해

미리 sort된 배열도 하나 만들었습니다.


▶  각각의 자식 클래스마다 공통된 배열의 값을 참조를 해야하지만, 자식만의 배열을 가져야 하므로,

28번의 배열을 protected로 추가했습니다.


▶  36, 39번의 메서드는 각 자식 클래스마다 독립적인 내용이므로 자식에게 구현을 맡겼습니다.


▶  42번의 start 메서드는 자식 클래스가 start 메서드를 사용했을시, sort가 진행되고 sort 진행시간이 기록됩니다.

또한, 프린팅을 줄 맞춰서 예쁘게 하기위해, 프린팅 정보중 너비가 제일 긴 텍스트의 길이를 저장했습니다.


▶  58번의 swap 함수는 sort에서 빠지지 않는 swap기능을 미리 구현해놓았습니다.


▶  117번의 toString메서드는 자식 클래스의 소트가 진행됬을경우, 정보를 프린팅 하기위해 구현했습니다.


▶  129번의 compareTo 메서드는 Comparable을 구현하기위해 오버라이딩 했습니다. 추후에

자식클래스들을 시간순으로 정렬하기 위해 작성했습니다.


준비한 내용은 여기까지 입니다.


다음 포스팅은, 이러한 Sort 클래스를 상속받아 Bubble 소트를 만들어보겠습니다!

포스팅이 도움 되셨다면, 커피 한잔 후원해주세요!
더 좋은 포스팅 작성에 큰 힘이 됩니다.

Buy me a coffeeBuy me a coffee

List와 Map의 차이 2편이다.


1편에서는 List에 대해 포스팅 했고,


오늘은 Map에 대해 포스팅한다.


아래는 1편 URL이다.


http://mommoo.tistory.com/33



Map을 이용해 저장할때는 List처럼


뭉텅이로 저장하는것이 아니라, Map에 아이템을 저장할때마다, 빈 공간을 찾아 저장한다.


따라서 List보다는 데이터 저장속도가 느릴 수 있다.  Map의 가장 큰 특징이라면,


쌍을이루는 Key와 Value값을 이용한다는 것이다.


따라서 단순한 포지션(0~10 같은 인덱션)보다는, 저장하고 싶은 데이터가 특별한 Key값을


가질때 Map을 사용하는것이 좋다. 아래의 예시는 자바언어로 작성하였다.



HashMap<String,String> hashMap = new HashMap<>();

hashMap.put("Key1" , " 키값이 Key1인 Value 입니다. ");

hashMap.put("Key2" , " 키값이 Key2인 Value 입니다. ");

hashMap.put("Key3" , " 키값이 Key3인 Value 입니다. ");

hashMap.put("Key4" , " 키값이 Key4인 Value 입니다. ");


System.out.println(hashMap.get("key1");

System.out.println(hashMap.get("key2");

System.out.println(hashMap.get("key3");

System.out.println(hashMap.get("key4");



------------- consol  -----------------


키값이 Key1인 Value 입니다.

키값이 Key2인 Value 입니다.

키값이 Key3인 Value 입니다.

키값이 Key4인 Value 입니다.


위의 예시는 key값을 String으로 데이터도 String으로 작성하였다.


만약 동일한 Key값을 사용하면 기존의 Key값을 가지고 있는 value가 사라지고


후에 저장한 valuse 값이 셋팅이 된다. key만 다르다면 value 값이 중복되도 상관 없다.


Map은 콘솔에 찍힌거와 같이 키값이 의미가 있을때 좋은 자료구조 이다.


ArrayList안에 원하는 데이터를 검색하는 경우에는 0번부터 해당 데이터가 있을때까지


검색을 해야하지만, (원하는 데이터의 index를 모르는 경우) hashMap의 경우는 


key값을 통해서 빠르게 데이터를 검색한다. 


요소의 추가 삭제는 List보다 성능이 나을때가 많다. 따라서, 검색성능은 기본적으로 Map이 좋다.



정리하자면,  Map 은빈번한 검색과, 범위데이터가 아닌 특정 데이터를 순간마다 캐치해야할 때 유리한 자료구조이다. 





'용어정리 > 프로그래밍용어' 카테고리의 다른 글

URL 이란?  (2) 2016.06.14
URI 이란?  (0) 2016.06.13
List와 Map의 차이 (1)  (0) 2016.04.26
XML 이란?  (9) 2016.01.26
상수(constant) 와 리터럴(literal)이란?  (16) 2016.01.06

포스팅이 도움 되셨다면, 커피 한잔 후원해주세요!
더 좋은 포스팅 작성에 큰 힘이 됩니다.

Buy me a coffeeBuy me a coffee

+ Recent posts