TIL-231004(자료구조 & 알고리즘 3주차)

📝오늘 공부한 것

• 프로그래머스 문제풀기
• 스파르타코딩클럽 자료구조 & 알고리즘 3주차 강의 듣기
• 이력서 수정하기

 

알게 된 점❗

[  트리  ]

뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료구조

비선형 구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어 있다.

 

Queue와 Stack은 자료 구조 중 선형 구조라고 함!

선형구조는 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미한다.

 

선형구조와 비선형 구조의 차이점은 형태뿐만 아니라 용도에서도 차이점이 많다.

선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고,

비선형 구조는 표현에 초점이 맞춰져 있다.

 

트리에서 나오는 용어들!

Node: 트리에서 데이터를 저장하는 기본 요소

Root Node: 트리 맨 위에 있는 노드

Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄

Parent Node: 어떤 노드의 상위 레벨에 연결된 노드

Child Node: 어떤 노드의 하위 레벨에 연결된 노드

Leaf Node(Terminal Node): Child Node가 하나도 없는 노드

Sibling: 동일한 Parent Node를 가진 노드

Depth: 트리에서 Node가 가질 수 있는 최대 Level

 

트리의 종류

이진트리, 이진 탐색 트리, 균형 트리, 이진 힙 등 다양한 트리가 있다.

이진 트리의 특징 : 각 노드가 최대 두 개의 자식을 가진다.

완전 이진 트리의 특징 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다.

 

[  완전 이진 트리  ]

완전 이진 트리는 왼쪽부터 데이터가 쌓이게 되는데, 이를 순서대로 배열에 쌓으면서 표현할 수 있다.

      8      Level 0 -> [8] 첫번째 레벨의 8을 넣고,
    6   3    Level 1 -> [8, 6, 3] 다음 레벨인 6, 3을 넣고
   4 2 5     Level 2 -> [8, 6, 3, 4, 2, 5] 다음 레벨인 4, 2, 5를 넣으면 된다!

 

트리의 높이는, 루트 노드부터 가장 아래 리프 노드까지의 길이이다.

      o      Level 0  # 루트 노드
    o   o    Level 1
   o o o     Level 2  # 가장 아래 리프 노드

이 트리의 높이는 ? 2 - 0 = 2

 

각 레벨에 노드가 꽉 차 있으면 각 레벨에 최대로 들어갈 수 있는 노드의 개수는 2^k개수임을 알 수 있다.

      1            Level 0 -> 1개
    2   3          Level 1 -> 2개 
   4 5 6 7         Level 2 -> 4개
 8 9....... 14 15  Level 3 -> 8개 
                   Level k -> 2^k 개

 

만약 높이가 h일때 모든 노드가 꽉 차있는 완전 이진 트리의 노드 개수는 

1 + 2^1 + 2^2 + 2^3 + 2^4 ..... 2^h

즉, 이를 수식으로 표현하면 2^(h+1) - 1 이 된다!

 

높이가 h 일 때 최대 노드의 개수는 2^(h+1) - 1개이다.

그러면 이 때 최대 노드의 개수가 N이라면, h 는  N = 2^(h+1) - 1 → h = log_2(N+1)-1 라고 할 수 있다.

즉! 완전 이진 트리 노드의 개수가 N일 때 최대 높이가 log_2(N+1) - 1 이므로 이진 트리의 높이는 최대로 해봤자 O(log(N))임을 알 수 있다!