Spanning Tree

N개의 노드들의 connected graph에서 얻을 수 있음

  • depth-first traversal 또는 breadth-first traversal 을 통해 확인
  • N개의 node와 N-1개의 edges로 된 Tree
  • cycle은 그래프로부터 제거됨 - 한번 방문한 노드는 다시 방문하지 않기에 cycle이 생길 수 없음

한개 이상의 spanning tree는 같은 그래프에서 구할 수 있음

추가정보

그래프가 connected 일 때, dfs나 bfs는 암묵적으로 그래프 G의 edge를 두개의 집합으로 분리

  • T(for tree edges): edge의 집합으로 사용되거나 search 도중에 방문
  • N(for nontree edges): 남아있는 edge의 집합
  • T의 edge는 G의 모든 vertex들을 포함하는 트리를 형성

요약

  • Spanning Tree는 G의 edge로만 구성되며 G안의 모든 vertex들을 포함하는 트리
  • 다시말해, 정점집합 v를 그대로 두고 (각 점들을 움직이지 않고) 간선(link)를 v-1개(v개의 link로 연결하면 cycle이 생김)만 남겨 트리가 되도록 만든 것.

Spanning Tree의 이점

  1. spanning tree에 nontree edge를 추가한다면 cycle이 됨

  2. spanning tree는  V(G’) = V(G) 이고 G’는 connected 와 같은 G의 minimum 그래프 G’임

  3. |E(G’)| = n - 1 이라면 |V(G)| = n 임
    • edge를 최소한으로 사용하므로 minimum cost spanning tree 이다.

예시

Depth-First Traversal Search

Breadth-First Traversal Search

Minimum Spanning Tree

N 개의 노드들의 weighted connected 그래프에서 얻을 수 있음

총 weighted가 최소한인 spanning tree

일반적으로 unique가 아님

minimum-cost 문제를 모델링하고 해결하는데 사용됨

어느 노드에서 시작하느냐에 따라 결과가 달라질 수 있음

추가정보

weighted undirected 그래프의 spanning tree 비용

  • spanning tree 안에 있는 edge의 cost(weight)의 합
  • 최소비용의 spanning tree
  • KruskalPrimSollin 알고리즘이 대표
  • greedy method: 단계적으로 최적의 해결책을 구성하고, 어떤 기준을 사용하여 각 단계에서 최적의 결정을 내림

spanning tree는 최소비용을 기준

  • 그래프 안에 있는 edge만을 사용
  • 정확하게 n-1 개의 edge를 사용
  • cycle을 유발할 수 있는 edge는 사용하지 않을 수 있음

요약

  • 각 연결한 link의 edge가 가장 작은 신장트리를 말한다.
  • 여기에 prim's, kruskal's, sollin's algorithm이 대표적이고 이 알고리즘들은 전부 greedy method이다. greedy 방법은 현재의 상황에서 자신이 최선의 선택을 하는 방법을 사용한다.

Prim 알고리즘

  1. 그래프의 node에서 시작
  2. 모든 인접한 node들을 계산
  3. 최소한의 edge의 weight를 선택
  4. 선택된 인접한 노드에서 계속 시작
    • 선택되지 않은 모든 edge를 계산
    • 새로 인접한 모든 edge들을 계산
    • 최소한의 weight를 가진 edge를 선택. 단 cycle은 피함
  5. 그래프의 모든 node들을 포함할 때까지 진행하고 모든 노드는 1번만 방문하도록 고려

추가정보

단일 vertex를 포함하는 T 라는 트리에서 시작

T ∪ {(u,v)}가 트리(cycle은 안됨)가 되도록 T의 최소비용인 edge(u,v)를 추가하고 T가 n-1 edge를 포함할 때까지 이 단계를 반복

알고리즘의 각 단계에서 선택되는 edge의 집합

  • prim 알고리즘은 나무를 형성하고 kruskal 알고리즘은 숲을 형성

요약

  • 어느 한 점을 선택해 해당 점에서 갈 수 있는 최소의 edge를 결정한 다음 잇는다이은 다음 두 점에서 갈 수 있는 최소의 edge를 다시 결정해 잇고 이러한 방식으로 모든 vertex를 이을 때 까지 한다.

예시

위와 같은 그래프를 prim알고리즘을 사용하여 탐색

B-D의 edge를 선택할 경우, cycle이 되기 때문에 선택하지 않음

예시2


위와 같은 그래프를 prim알고리즘을 사용하여 탐색

Kruskal 알고리즘

prim 알고리즘과 다르게 어느 한 vertex를 선택하지 않고 전체 link의 edge중 가장 작은 edge를 찾아 잇는다그 다음 가장 작은 edge를 이어가는 방식

예시

위와 같은 그래프를 kruskal 알고리즘을 사용하여 탐색

Dijkstra 알고리즘

source에서 destination 까지 최단거리는 무엇일까?

Dijkstra 알고리즘은 단일 출발지에서 그래프 이론 안에 있는 가장 짧은 경로 찾기 문제를 해결하는 알고리즘

directed와 undirected 그래프 모두 작동하지만 모든 edge는 양수의 weight를 가져야 함

접근법: greedy 알고리즘

Input: Weighted 그래프 G={E,V} 와 출발지 vertex v∈V이고 모든 edge는 양수

Output: 주어진 출발지 vertex v∈V 에서 다른 모든 vertex까지의 최단 경로 길이 (또는 최단 경로 그 자체)


출발점에서 모든 목적지까지의 가장 짧은 경로를 탐색 - greedy 알고리즘

  • 양수의 edge 비용만 탐색: Dijkstra 알고리즘
  • 음수를 포함한 모든 edge 비용을 탐색: Bellman-ford 알고리즘
  • 모든 pair의 가장 짧은 경로 탐색 (dynamic programming): floyd 알고리즘

기본컨셉

edge가 양수인 길을 선택


(A,B)  (A,C) 이므로 (A,B) 선택

(A,B,C)  (A,C), (A,B,D) 이므로 (A,B,C) 선택

(A,B,D)  (A,B,C,E), (A,B,C,F), (A,B,C,G) 이므로 (A,B,D) 선택

위와 같은 방법으로 A에서 모든 vertex까지의 모든 경로를 찾을때까지 반복

기본컨셉설명

  1. S는 가장 짧은 경로를 가지는 v0을 포함하는 vertex들의 집합을 나타내도록 함
  2. S가 아닌 w의 경우, dist[w]는 v0에서 출발해 S의 vertex들을 지나고 w로 끝나는 최단 경로의 길이라고 나타냄
  3. S 안에 있지 않은 vertex u를 찾을 수 있고 dist[u]는 minimum이고 S안에 u를 추가함
  4. 경로를 적절하게 유지


해당 알고리즘의 시간복잡도는 (|V|2)

예시

A 에서부터 시작

요약

  • 시작점에서 모든 도착점까지 가장 짧은 path의 cost를 찾는 알고리즘.


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

Sorting (Bubble, Selection, Insertion Sort)  (0) 2018.09.30
트리 탐색 방법 (Tree traversal)  (0) 2018.09.28
Spanning Tree (Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘)  (0) 2018.09.26
Graph  (0) 2018.09.26
AVL Tree  (0) 2018.08.17
Binary Search Tree  (0) 2018.08.15

Graph

트리는 그래프의 특수한 케이스

그래프는 다양한 문제를 모델링 하는 것과 문제를 해결하기 위해 알고리즘을 고안하는데 유용


용어

vertex, vertices(vertex의 복수형): 트리의 Node와 동일개념

  • root node와 leaf node가 아닌 모든 노드

edge: 트리의 link와 동일개념

  • undirected edge ( = undirected graph)
  • directed edge ( = directed graph)
    • 단방향, 양방향
    • in-degree (해당노드로 들어오는 방향성 있는 edge), out-degree (해당노드에서 나가는 방향성 있는 edge)
  • weighted edge ( = (directed or undirected) weighted graph)
    • 서울 - 제주도 와 서울 - LA의 weight는 다름

정의1

graph G=(V,E)


V(G): empty가 없는 vertex들의 유한한 집합

  • v1, v2, ..., vi, vj, ... ∈ V(G)

E(G): empty가 가능한 유한한 edge들의 집합

  • (vi, vj) ∈ E(G) 이면 vi, vj ∈ V(G)

undirected graph

  • (vi,vj) = (vj,vi)

directed graph ordered

  • <vi,vj> ≠ <vj,vi>

집합의 표현 예시

V(G1) = {0,1,2,3}; E(G1) = {(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}

V(G2) = {0,1,2,3,4,5,6}; E(G2) = {(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)}

V(G3) = {0,1,2}; E(G3) = {<0,1>,<1,0>,<1,2>}

예시

상세

degree (of a vertex): vertex에 인접한 edge의 수

in-degree (of a vertex v): 방향성 있는 edge가 vertex를 향하고 있는 edge의 수

out-degree (of a vertex v): 방향성 있는 edge가 vertex에서 나가고 있는 edge의 수

그래프 제한사항

vertex에 edge가 없거나 자기자신을 가리키는 edge는 없음

하나의 vertex에서 다른 vertex를 연결하는 edge가 중복인 경우는 없음 (<=> multigraph)

정의2

  • subgraph: 그래프의 한 부분

  • connected graph: 모든 vertex가 연결된 그래프

  • disconnected graph: 한개의 vertex라도 연결되어 있지 않는 그래프

  • adjacent nodes: 인접한 vertex간 연결되어 있는 node 관계

  • complete (connected) graph: 모든 vertex가 adjacent node로 표현이 가능한 그래프. 전부 연결되어 있으므로 connected graph임

예시

정의3

  • path: vertex X에서 vertex Y까지 가는 edge의 연결된 경로
    • 아래 그림에서 A에서 D까지 가는 경로는 (A,B), (B,C), (C,D) 이므로 length=3임
  • cycle: 출발한 노드 다시 도착할 수 있는 구조
    • 아래 그림에서 ABCDA는 cycle 구조
  • cyclic graph: cycle 구조가 존재하는 그래프
  • acyclic graph: cycle 구조가 존재하지 않는 구조 (=tree)

예시

그래프 표현방식

Adjacency Matrix

(n x n) 2차원 배열 - (vertex)(edge)로 표현

  • n은 그래프 안에 존재하는 노드의 개수

만약 v1가 v2가 adjacent하다면 1로 표현하고 그렇지 않으면 0으로 표현




예시

장점

공간절감

방향성이 없는 그래프일 때, 공간의 절반을 절약할 수 있음

저장할 때, 위 또는 아래의 삼각형모양의 데이터만 저장하면 됨

방향성이 없는 그래프일 때, vertex i의 degree를 구하는 공식은  임

그래프 탐색방법

그래프에서 모든 vertex를 방문하는 방법은 아래와 같음

  • depth-first traversal
  • breadth-first traversal

Depth-First Traversal

  1. 한 노드에서 더이상 새로운 인접한 노드가 없을 때까지, 인접한 노드를 재귀적으로 방문하는 방법
  2. 재귀적으로 실행한 다음, 뒤로 돌아갈 때, 다음 새로운 인접한 노드를 재귀적으로 방문
  3. 처음 시작한 노드에서의 인접한 노드를 재귀적으로 전부 방문했다면 종료

방문 순서의 방법은 preorder tree traversal 과 유사


재귀적으로 실행되는 순서는 stack을 사용하여 구현하면 쉽다!

adjacent matrix로 구현한다고 하면 시간복잡도는 O(n2)임

예시


방문경로

Breadth-First Traversal

  1. 시작노드에서 인접한 노드를 한번 방문함
  2. 그 다음, 한번도 방문하지 않은 모든 인접한 노드를 방문
  3. 모든 노드를 방문했다면 종료

방문 순서의 방법은 level-order tree traversal 과 유사함

queue를 사용하여 구현하면 쉽다!

adjacent matrix로 구현한다고 하면 시간복잡도는 O(n2)임

예시

방문경로

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

트리 탐색 방법 (Tree traversal)  (0) 2018.09.28
Spanning Tree (Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘)  (0) 2018.09.26
Graph  (0) 2018.09.26
AVL Tree  (0) 2018.08.17
Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13


BST에서 위와 같은 Skewed Tree의 경우 복잡도가 O(n)이 나오는 한계점을 해결하기 위해 AVL Tree가 고안됨. AVL 은 해당 자료구조를 만든 사람의 앞글자를 하나씩 따서 만든 것(..)

AVL Tree 예시

AVL Tree

Not AVL Tree

용어

  • 노드의 height: h
  • balance factor: bf (왼쪽 서브트리의 height - 오른쪽 서브트리의 hegiht)
  • empty height: -1

특징

  • AVL 트리는 BST이면서 동시에 균형을 유지하고 있음
  • 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하 (왼쪽과 오른쪽 서브트리의 height 계산 결과가 1, 0, -1 이외라면 해당 트리는 AVL 트리가 아님 - 만약 height가 없는 경우는 -1)
    • 즉, 모든 노드들은 balance factor 를 알고 있음
  • 균형을 유지하고 있기 때문에 이진 검색 시의 효율성을 보장

문제는 이러한 균형을 맞추려 하다 보니 유지하는 방법이 복잡함. 예를 들어, 노드 삽입이나 삭제로 인해 왼쪽과 오른쪽 서브트리의 height의 계산결과가 2, -2가 나온 경우, 트리를 rotation 시켜줘야 함


rotation에는 2가지 관점이 있는데 AVL 트리를 height balance로 유지하는 것과 binary search tree로 유지하는 관점이 있음. 관점은 나뉘어 있지만 가장 중요한 것은 rotation 시키면서 트리의 height를 낮춰야 복잡도가 줄어듦

rotation의 방법은 4가지로 1번만 rotation 시키는 LL, RR와 2번 rotation 시키는 LR, RL이 존재.


Single Rotation

LL (Right)


왼쪽은 차이가 2이고 오른쪽은 0이므로 왼쪽이 무너진 경우. 이 경우는 오른쪽으로 트리를 회전시켜주면 해결

RR (Left)


왼쪽은 차이가 0이고 오른쪽은 2이므로 오른쪽이 무너진 경우. 이 경우는 왼쪽쪽으로 트리를 회전시켜주면 해결

Double Rotation

위에서 본 LL, RR과는 달리 방향이 일정하지가 않기 때문에 첫 회전에서는 LL 또는 RR로 방향을 맞춘 다음 다시 회전시켜 높이의 균형을 유지시켜줌

RL (Right & Left)


가장 마지막 노드인 422 값을 부모노드와 자리를 바꾸면 바로 RR의 형태를 이루기 때문에 자리를 바꾼 후, RR 로 회전을 한번 더 시킴.

LR(Left & Right)

가장 마지막 노드인 422 값을 부모노드와 자리를 바꾸면 바로 LL의 형태를 이루기 때문에 자리를 바꾼 후, LL 로 회전을 한번 더 시킴.

장단점

  • 검색, 삽입, 삭제 모두 O(logN)이며 항상 균형을 맞춤
  • 프로그래밍하기가 어렵고 디버깅 또한 어려움.
  • 위 검색, 삽입, 삭제가 빠르긴 하지만 균형을 맞추는데에 시간이 듦
  • 대규모 tree를 이룬 후 검색하는 것은 DB에서 주로 발생하는데 DB는 이미 B-Tree 자료구조를 사용 중임


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

Spanning Tree (Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘)  (0) 2018.09.26
Graph  (0) 2018.09.26
AVL Tree  (0) 2018.08.17
Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13
Binary Tree  (0) 2018.08.01

Binary Search Tree(BST - 이진검색트리) 는 비어있거나 아래의 속성을 만족하는 binary tree 입니다. 자세하게 Binary Search (이진 검색)과 Linked List를 결합한 자료구조입니다. 이진 검색의 검색능력을 유지하면서 빈번한 값의 삽입, 삭제가 가능하도록 고안되었습니다. 이진검색의 경우 검색에 소요되는 시간복잡도는 O(log₂n)으로 빠르지만 자료 입력, 삭제가 불가능합니다. linked list의 경우 자료 입력, 삭제에 필요한 시간복잡도는 O(1)로 효율적이지만 탐색하는 데에는 O(n)의 복잡도가 발생합니다.

정의

  1. 각각의 모든 node 들의 key는 중복된 값이 아님 (unique)
  2. 기존의 binary tree는 순서가 없지만 BST는 순서가 존재
  3. parent node의 왼쪽은 부모보다 작은 값이고 오른쪽은 부모보다 큰 값임
  4. 왼쪽, 오른쪽의 서브 트리또한 BST임

Search

  1. 찾고자 하는 Key와 root node값이 같으면 성공
  2. Key가 root node 값보다 작다면 (key < root node) 왼쪽의 sub tree로 이동
  3. Key가 root node 값보다 작다면 (key > root node) 오른쪽의 sub tree로 이동
  4. 1~3번 반복
  5. 만약 조건에 맞는 데이터가 없으면 실패 (tree에 값이 존재하지 않는 경우)


위 그림에서 120 값을 찾는 예시입니다. 

  1.  root node(=100)와 찾고자 하는 값 (=120) 비교
  2. root node보다 찾고자 하는 값이 더 크므로 (100 < 120) 오른쪽 subtree로 이동
  3. 오른쪽 subtree의 노드값(=150)과 찾고자 하는 값(=120)과 비교
  4. 찾고자 하는 값이 더 작으므로 (150 > 120) 왼쪽 subtree로 이동
  5. 120값이므로 검색 성공


Insert

값을 삽입하고자 하거나 찾고자 하는 값이 없을 경우 루트노드에서 시작, 값을 비교해가면서 tree의 가장 마지막까지 간 다음 값을 입력

예시

위 그림에서 80을 넣고자 하면 아래와 같은 위치에 삽입


Delete

  1. 첫 단계는 지우고자 하는 값이 해당 tree에 있는지 search
  2. 지우고자 하는 값이 leaft node(가장 마지막)에 위치해있으면, 그냥 지우면 됨
  3. internal node라면 다음과 같이 분기가 됨
    1. 지워야 하는 node가 child node를 1개 가지고 있는 경우, internal node를 지운 후 해당자리에 child node를 옮김
    2. 지워야 하는 node가 child node를 2개 가지고 있는 경우, 왼쪽의 subtree에서 가증 큰 노드 또는 오른쪽 subtree에서 가장 작은 노드를 옮김

예시

50 (leaf node) 삭제


75 (internal node 이며 1개의 child node 존재) 삭제


150 (internal node 이며 2 child node 존재) 삭제

1. 왼쪽의 subtree에서 가장 큰 노드를 이동


2. 오른쪽 subtree에서 가장 작은 노드를 이동



internal node이며 child node를 2개 가지고 있는 경우 삭제하는 방법은 2가지가 있지만 여기서 조건적으로 효율적인 방법이 존재.

1, 2번의 방법 중 트리의 height를 줄일 수 있는 방법을 채택하는 것이 향후 트리 검색의 속도를 향상시킬 수 있음

복잡도

BST는 검색, 삽입, 삭제 모두 O(h)임. h는 BST의 높이(height)

BST에서는 inorder(LVR) 검색 방식을 사용

BST는 평균(최상) 시간복잡도가 O(log₂n)이지만 최악의 경우 O(n)임. (skewed tree이면 node의 수만큼 시간이 소요됨)

  • tree가 complete binary tree거나 full binary tree이면 O(log₂n), skewed tree이면 O(n)

위 O(N)의 경우때문에 노드가 얼마 되지 않아도 검색속도가 나오지 않을 가능성이 존재함. 이 때문에 AVL Tree가 고안됨


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

Graph  (0) 2018.09.26
AVL Tree  (0) 2018.08.17
Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13
Binary Tree  (0) 2018.08.01
Tree  (0) 2018.07.31
  • Heap은 Complete Binary Tree를 기본으로 가지는 자료구조
  • 일반적으로 array로 구현하는 것이 좋음
  • Heap 은 최댓값 또는 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안됨
  • 시간복잡도: O(log₂N)
  • Heap은 다음과 같은 속성(property)를 만족함
    • A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소관계가 성립
  • 종종 priority queue를 보충하는대에 사용

종류

max heap: root노드가 가장 큰 수

min heap: root노드가 가장 작은 수

Max Heap

부모노드의 키가 자식노드의 키보다 항상 큼


Node Insertion

max heap에서 노드 추가는 말단의 맨 오른쪽의 leaf node에 자리를 하나 만들고 해당 노드에 값을 대입한 다음 parent node와 값을 비교하며 자리를 바꿔 나감. (root node 까지)

Node Deletion

max heap에서 노드 삭제는 항상 루트노드를 지움. 그 다음 complete binary tree를 유지하기 위해 tree를 재조정함. 말단의 맨 오른쪽 노드를 지운 다음, 루트 노드 자리에 옮기고 child node와 비교해 자리를 바꿔나감.


Max Heap에서 노드 추가, 삭제는 모두 트리의 depth만큼 걸림 -> O(log₂N)

Min Heap

부모노드의 키가 자식노드의 키보다 항상 작음



키의 대소관계는 오로지 부모노드와 자식노드 간에만 성립되며, 형제(sibling) 사이에는 대소관계가 정해지지 않음

Priority Queue

일반적인 queue는 FIFO 이기 때문에 먼저 들어온 데이터가 먼저 나가지만, priority queue는 우선순위가 높은 데이터 먼저 나감

새로운 노드가 삽입되면 우선순위에 맞는 위치에 삽입 (enqueue)

제거할 때는 우선순위가 가장 높은 맨 앞의 노드를 삭제 (dequeue)



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

AVL Tree  (0) 2018.08.17
Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13
Binary Tree  (0) 2018.08.01
Tree  (0) 2018.07.31
Stack, Queue, Circular Queue  (0) 2018.07.30



degree가 최대 2인 트리

i번째 level에 나올 수 있는 노드의 최대 개수는 2^(i - 1)

  • 주의 할 것은 전체 tree의 노드 최대 개수 또는 i번째 level까지 전체 노드의 개수가 아닌 i번째 level만 단독으로 보고 있음.

k가 tree의 depth일 때, 최대 노드의 개수는 : 2^k -1

위 그림에서 2번째 level의 노드의 최대 개수는 2^(2-1) = 2개이고, depth는 2^2-1 = 3개, height는 2^3 - 1 = 7개임


binary tree에는 skewed tree, complete binary tree, full(perfect) binary tree가 있음

Full (Perfect) Binary Tree

마지막 레벨까지 노드가 꽉 차게 있는 트리


Complete Binary Tree

노드가 왼쪽에서 오른쪽 순서로 순차적으로 존재하는 트리



위 그림에서 3번 노드가 없어도 complete binary node는 성립하지만 1번이나 2번 노드가 없으면 complete binary tree가 아니게 됨. 

Skewed Tree




binary tree를 구현하는 데엔 array로 구현하는 것이 좋지만 다른 트리에서는 효율성이 떨어지고 컴파일 언어에서 어레이 사이즈 제한때문에 저장공간 문제가 존재. C에서는 이를 linked list로 해결할 수 있음. (근데  linked list는 구현이 어려움)


Binary Tree Traversal

루트노드에서 시작해 linear 하게 노드를 1번씩 방문하는 방식은 아래와 같습니다.

V: 노드 방문

L: 왼쪽 branch를 타고 이동

R: 오른쪽 branch를 타고 이동


  • inorder: LVR (Left Visit Right)
  • preorder: VLR (Visit Left Right)
  • postorder: LRV (Left Right Visit)

예를 들어, preorder는 하위 트리를 탐색하기 전에 노드 방문이 완료

예시 (inorder: LVR)


  1. 루트노드인 X에서 시작.
  2. 왼쪽 브랜치가 있으므로 왼쪽 브랜치를 타고 Y 노드로 이동
  3. Y 노드에서도 왼쪽 브랜치가 있으므로 왼쪽 브랜치를 타고 S 노드로 이동
  4. S 노드에는 왼쪽 브랜치가 없어서 이동할 수 없음. 
  5. 왼쪽으로 이동할 수 없으므로 S 노드를 방문 후 오른쪽 브랜치로 이동하려하나 브랜치가 없어 Y노드로 롤백
  6. Y노드를 방문한 후 오른쪽 브랜치를 타고 이동하여 T 노드로 이동
  7. T노드는 4~5번과 동일.

위와 같은 순서로 값의 출력은 S, Y, T, X, Z 순으로 출력됨


위와 같이 binary tree의 모든 노드를 탐색하는 방법은 stack이 필요함. 

모든 노드를 탐색하는데에 걸리는 time complexity는 O(N)임 (N은 트리에 존재하는 노드의 개수)

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

Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13
Binary Tree  (0) 2018.08.01
Tree  (0) 2018.07.31
Stack, Queue, Circular Queue  (0) 2018.07.30
ADT, 복잡도(시간복잡도, 공간복잡도), 빅오 분석법  (0) 2018.07.29

+ Random Posts