data structure2 자료구조 이진 트리(Binary Tree)의 종류 Binary Tree 이진 트리 이진 트리(Binary Tree) 란 무엇인가? 각각의 노드가 최대 2개의 자식 노드를 가질 수 있는 트리이다. 정렬과 검색 알고리즘을 위한 하나의 도구 이진 트리의 모양에 따라 알고리즘의 성능에 차이가 있다. 트리의 형태는 레벨과 노드 수에 따라서 결정된다. 이진 트리(Binary Tree) 의 종류 1. Perfect binary tree 포화 이진 트리 포화 이진 트리는 모든 레벨의 노드가 가득 차있는 트리이다. 노드가 2개의 자식을 가지고 있다. 차수(Degree) 가 2 이다. 모든 노드가 가득 차있어 단말 노드부터 루트노드까지의 높이가 같다. 노드의 개수 n = 2^h - 1, h 는 높이 A는 B 와 C를 자식으로 가져 꽉 차있고, B는 D 와 E, C는 F .. 2020. 6. 11. [C 언어] Array Circular Queue 배열 원형 큐 구현 Array Circular Queue 배열 원형 큐 왜 원형 큐 (Circular Queue) 를 사용할까? 1. 기존의 배열 큐 (Array Queue) Memory Overflow 문제를 해결하기 위해서이다.- 배열의 Front 에 빈 노드가 있다고 할지라도, Front에 새로운 노드를 추가하려고 할때 Memory Overflow가 발생한다. 배열 큐의 특성상 배열의 크기는 이미 정해져있기 때문이다.- 배열을 이동시키는 방법으로 이 문제를 해결할 수 있다. 하지만 배열을 이동하는데 O(N)의 시간 복잡도가 필요하다. 따라서 배열의 크기가 커질수록 이 문제는 효율적이지 않은 방법이 된다.- 이 문제를 위한 효과적인 방법은 원형 큐(Circular Queue)를 이용하는것이다. 처럼 dequeue를 실행.. 2020. 6. 7. 이전 1 다음
