이진트리2 [Algorithms] 이진트리(Binary tree) 이진 트리(binary tree)란 한 노드가 최대 두 개의 자식 노드를 가지는 트리를 말한다. 보통 첫 번째 노드를 부모 노드라고 하며 자식 노드는 왼쪽 노드(left noe)와 오른쪽 노드(right node)로 부른다. 이진 트리는 이진 탐색 트리와 이진 힙의 구현에 흔히 쓰이는 자료구조다. 용어정의 방향 간선(directed edge) : 부모 노드에서 자식 노드로 가는 경로를 가리킨다. 위 그림에서 화살표로 표현되어 있다. 루트 노드(root node) : 자신의 위로 부모 노드가 없는 노드다. 트리는 하나의 루트 노드만을 가진다. 단말 노드(leaf node) : 자식 노드가 없는 노드다. 노드의 깊이(depth) : 루트 노드에서 특정 단말 노드까지의 길이다. 레벨(level)이라고 부르기도.. 2017. 4. 19. [Algorithms] B tree에 대한 개념 정리 B-트리(B-tree)에 대해 공부한 후 문서로 남긴다. B트리에 대해 자세히 알아본 계기는 인턴 과정 중이었다. 데이터베이스와 파일 시스템에서 널리 사용되기 때문인 것 같다. B트리는 이진 트리를 확장한 개념인데, (그러나 B-트리는 이진 트리가 아니다.) 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조다. B트리 쓰임새 디스크 I/O의 기본 단위는 블록이다. 디스크로부터 데이터를 읽거나 기록할 때 이를 포함하는 디스크 블록 전체를 메모리로 읽어오고 다시 블록 전체를 디스크에 기록하는 방식으로 디스크 I/O가 일어난다. 디스크에 접근하기 위한 시간은 다음과 같이 구할 수 있다. Access time = seek time + latency + transfer time; - se.. 2017. 4. 17. 이전 1 다음
