언제나 휴일

[C언어 알고리즘] 3.4.1 트리의 용어[그림 3.7] 트리의 구조 트리에는 부모가 없는 노드가 없거나 유일합니다. 그리고 이를 루트라고 말합니다. 그리고 트리에서 자료를 보관하는 것을 정점(Vertex) 혹은 노드(Node)라고 부르며 정점에서 다른 정점으로 가는 경로를 간선(Edge) 혹은 링크(Link, 다른 노드의 위치 정보)라고 부릅니다. 언제나 트리의 정점은 간선 개수보다 1개 많습니다. N(V) = N(E)+1 , N(V)는 정점의 개수, N(E)는 간선의 개수 루트에서 자신에게 걸리는 거리를 레벨(Level)이라 부르고 루트를 Level 1로 출발합니다. 그리고 가장 높은 레벨(Level)을 트리의 높이(Height) 혹은 깊이(Depth)라고 부릅니다. 간선은 링크 혹은 가지라고도 부르..

[C언어 알고리즘] 3.4 이진 탐색 트리 이번에는 재귀 알고리즘으로 구현하는 이진 탐색 트리를 알아봅시다. 이진 탐색 트리는 검색 효율을 높이기 위해 만들어진 트리입니다. 이진 탐색 트리를 살펴보기 전에 먼저 트리가 무엇인지 살펴보기로 해요. 트리는 대표적인 비선형 자료구조입니다. 비선형 자료구조는 자료를 보관하는 구조를 하나의 선의 형태로 표시할 수 없는 자료구조를 말하며 트리와 그래프 등이 있습니다. 그 중에 트리는 뿌리에서부터 계층적으로 자료를 보관하는 자료구조입니다. 트리는 방향성 있는 그래프로 표현하며 사이클이 존재하지 않고(ACycle) 고립 상태가 없는(No Island) 자료구조입니다. 트리는 다음처럼 루트와 서브 트리의 집합으로 정의할 수 있습니다. Tree = {root , sub t..

트리 트리(Tree): 방향성 있고 사이클이 없고 고립 영역이 없는 그래프 정점(Vertext or Node)과 간선(Edge or Branch)으로 표현할 수 있음 정점의 개수가 N이면 간선의 수는 N-1 트리의 용어 루트(Root): 트리 계층의 맨 위에 있는 노드, 부모가 없는 노드 레벨(Level): Root를 1로 출발해서 자신에 도달하는 데 걸리는 거리 높이(Height): 트리의 가장 높은 Level, 깊이(Depth)라고도 부름 가지(Branch): 부모와 자식간의 경로(간선) 조상(Ancestors): 자신에게 오기 위한 경로에 있는 모든 노드들 부모(Parent): Level N인 노드와 연결된 Level N-1인 노드 자식(Son): Level N인 노드와 연결된 Level N_+1인..

7.1 트리의 용어 트리에는 부모가 없는 노드가 없거나 유일합니다. 그리고 이를 루트라고 말합니다. 그리고 트리에서 자료를 보관하는 것을 정점(Vertex) 혹은 노드(Node)라고 부르며 정점에서 다른 정점으로 가는 경로를 간선(Edge) 혹은 링크(Link, 다른 노드의 위치 정보)라고 부릅니다. 언제나 트리의 정점은 간선 개수보다 1개 많습니다. N(V) = N(E)+1 , N(V)는 정점의 개수, N(E)는 간선의 개수 루트에서 자신에게 걸리는 거리를 레벨(Level)이라 부르고 루트를 Level 1로 출발합니다. 그리고 가장 높은 레벨(Level)을 트리의 높이(Height) 혹은 깊이(Depth)라고 부릅니다. 간선은 링크 혹은 가지라고도 부르며 Level N인 노드로 가기 위한 Level N..

7. 이진 탐색 트리 이번에는 재귀 알고리즘으로 구현하는 이진 탐색 트리를 알아봅시다. 이진 탐색 트리는 검색 효율을 높이기 위해 만들어진 트리입니다. 이진 탐색 트리를 살펴보기 전에 먼저 트리가 무엇인지 살펴보기로 해요. 트리는 대표적인 비선형 자료구조입니다. 비선형 자료구조는 자료를 보관하는 구조를 하나의 선의 형태로 표시할 수 없는 자료구조를 말하며 트리와 그래프 등이 있습니다. 그 중에 트리는 뿌리에서부터 계층적으로 자료를 보관하는 자료구조입니다. 트리는 방향성 있는 그래프로 표현하며 사이클이 존재하지 않고(ACycle) 고립 상태가 없는(No Island) 자료구조입니다. 트리는 다음처럼 루트와 서브 트리의 집합으로 정의할 수 있습니다.Tree = {root , sub trees} sub tre..