트리 이론 기본편 -중위 순회의 특징 응용하기-
1. 이진 탐색 트리의 특징 이진 탐색 트리는 어떠한 경우에도 왼쪽 서브 트리의 루트 루트 > 오른쪽 서브트리 순서대로 순회를 하게 된다. 그렇다면 주어진 이진 트리의 노드를 중위순회한다면, 트리에 넣어야할 데이터의 순서가 주어지며 그러한 순서대로 데이터를 작은 값부터 넣으면 "왼쪽 서브 트리의 루트 2 > 3 > 4 > 5 > ..
1. 이진 탐색 트리의 특징 이진 탐색 트리는 어떠한 경우에도 왼쪽 서브 트리의 루트 루트 > 오른쪽 서브트리 순서대로 순회를 하게 된다. 그렇다면 주어진 이진 트리의 노드를 중위순회한다면, 트리에 넣어야할 데이터의 순서가 주어지며 그러한 순서대로 데이터를 작은 값부터 넣으면 "왼쪽 서브 트리의 루트 2 > 3 > 4 > 5 > ..
1. 수식 트리(expression binary tree) 수식을 표현하는 이진 트리 수식 이진 트리라고도 부른다 연산자는 루트 노드이거나 가지 노드 루트와 잎 사이의 중간 노드들을 가지 노드라고 하나봐 피연산자는 모두 잎 노드에 존재함 전위, 중위, 후위순회를 이용해서 순회하면 수식의 전위표기법, 중위표기법, 후위표기법이 된다 2. 예시 다음과 같은 트리를 전위, 중위, 후위순회 해서 전위표기법, 중위표기법, 후위표기법을 구해보면? 2-1) 구현 예시 #class 정의 class Node: def __init__(self,data): self.data = data self.left = None self.right = None #tree 정의 root = Node('+') root.left = Node(..
1. 배열을 이용한 이진 트리 표현 루트의 번호를 1로 하고 레벨 n에 대하여 왼쪽부터 오른쪽으로 $2^{n}$부터 시작하여 번호를 부여 노드 번호를 index로 해서 배열에 노드 정보를 저장 완전 이진트리일때만 가능할듯 아니라면 빈 부분은 0으로 채우고 데이터를 넣으면 될것 같은데 조금 복잡해질것 같고 높이 h가 주어진다면.. h의 노드 최대개수는 $2^{h+1}-1$개니까 [0]*$2^{h+1}-1$으로 초기화 노드 개수 n개가 주어진다면 뭐 [0]*(n+1)로 초기화하면 될듯 라고 생각했는데.. 이게 아니야 왜 그런지는 뒤에 쓴다 1-1) 노드 번호의 특징 완전이진트리처럼 번호를 붙이는 방식인 1번부터 n번까지를 왼쪽부터 오른쪽으로 차례대로 붙일때만 성립함 1)레벨 n의 시작 노드 번호는 $2^{n..
1. 이진트리 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리 모든 노드들이 자식 노드를 "최대" 2개까지만 가질 수 있는 트리 각 자식 노드를 왼쪽 자식 노드(left child node), 오른쪽 자식 노드(right child node) 이진 트리 예시 4가지.. 모든 노드가 자식 노드를 "최대" 2개만 가지면 이진 트리가 된다 자식 노드가 아예 없어도 된다는 소리 2. 특징 레벨 i에서(높이 i에서) 노드의 최대 개수는 $2^{i}$개 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 h+1개 최대 개수는 $2^{h+1}-1$개 3. 종류 이진트리의 종류에 따라 저장, 표현, 알고리즘 등이 달라질 수 있으므로 잘 구분해야한다 3-1) 포화 이진 트리(full binary tree..
1. 트리의 개념 비선형 구조 원소들 간에 1:n 관계를 가지는 자료구조 원소들 간에 계층관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리 모양의 구조 ############### 선형구조와 비선형구조 간단히 ################################# 2. 트리의 정의 1개 이상의 노드로 이루어진 유한 집합 즉, 노드가 1개만 있어도 트리 최상위 노드를 root라고 부른다 루트 이외의 나머지 노드들은 n개의 부분집합 $T_{1}, T_{2}, T_{3},... , T_{n}$으로 분리 가능하다 그림과 같이 $T_{1}, T_{2}, T_{3},... , T_{n}$도 하나의 트리가 되며, 루트의 부 트리(subtree)가 된다 그러니까 어떤 tree의 일..
서로소 집합 알고리즘(disjoint set) 그래프 내에서 여러개의 node가 존재할 때 2개의 node를 선택해서 이 node가 서로 같은 node에 속하는지 판별하는 알고리즘 예를 들어 다음과 같이 8개의 node가 존재한다면 이런 경우는 부모 node가 자기 자신인 경우이다 이제 1과 2가 연결되었다고 생각해보자 이런 경우 2의 부모 node는 1이 된다 이렇게 합쳐나가는 과정을 union알고리즘이라고 부른다 이번엔 2와 3도 연결되었다고 가정해본다면 그러면 3의 부모 node는 2가 되는데 3과 1이 연결되었다는 것은 어떻게 아는가? 3의 부모 node는 2이고 2의 부모 node는 1이라서 부모 node만 보고서는 판단할 수가 없다 그렇지만 재귀함수를 사용하면 3의 부모 node가 2를 가리키..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck