<div id="readability-page-1" class="page"><div tabindex="-1" id="___gatsby"><header><h2><a href="/">김로그</a></h2><nav><a href="/tags">tags</a>|<a href="/about">about</a></nav></header><main><article><header><time datetime="September 23, 2016">September 23, 2016</time><p><small><a rel="tag" href="/tags#자료구조">#자료구조</a> </small><small><a rel="tag" href="/tags#heap">#Heap</a> </small></p></header><section><h2>정의</h2>
<blockquote>
<ul>
<li>Complete Binary Tree</li>
<li>A가 B의 부모노드이면 A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.</li>
</ul>
</blockquote>
<p><strong>이진트리</strong>(Binary Tree)는 부모의 자식이 0~2개인 트리인데 이진트리의 <strong>모양</strong> 에 따라 이진트리를 분류 할 수 있다.</p>
<ul>
<li><strong>Rooted Binary Tree</strong> 는 모든 노드의 자식이 최대 2개인 루트를 가진 트리</li>
<li><strong>Full Binary Tree</strong> 단말 노드가 아닌 모든 노드가 2개의 자식을 가진트리</li>
<li><strong>Complete Binary Tree</strong> 마지막 레벨을 제외하고 모든 노드가 채워진 이진트리, 마지막 레벨의 노드들은 왼쪽부터 채워져있다.</li>
<li><strong>Perfect Binary Tree</strong> 루트(root)에서 부터 말단노드(leaf)까지의 거리가 모두 같은 트리</li>
</ul>
<p>이중 <strong>Heap</strong> 은 <strong>Complete Binary Tree</strong> 의 꼴을 하고 있다.
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/8/85/Complete_binary.pdf/page1-440px-Complete_binary.pdf.jpg"></p>
<h2>reference</h2>
<ul>
<li><a href="https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)" target="_blank" rel="noopener">위키피디아 - 힙</a></li>
<li><a href="https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC" target="_blank" rel="noopener">위키피디아 - 이진트리</a></li>
<li><a href="https://en.wikipedia.org/wiki/Heap_(data_structure)" target="_blank" rel="noopener">wikipedia - Heap</a></li>
<li><a href="https://namu.wiki/w/%ED%9E%99%20%ED%8A%B8%EB%A6%AC" target="_blank" rel="noopener">나무위키 - 힙 트리</a></li>
<li><a href="http://www.yes24.com/24/goods/2656393" target="_blank" rel="noopener">이석호. C++ 자료구조론 (2nd ed.). 인피니티북스.</a></li>
</ul></section><hr></article><nav><ul><li><a rel="prev" href="/data-structure/2016-09-09-5-bs-tree/">← 5.Binary Search Tree에 대해서 알아보자.</a></li><li><a rel="next" href="/develop/2016-10-14-es6-array-helper/">ES6 array helper method들을 알아보자 →</a></li></ul></nav></main></div></div>

Kimlog RSS Feed

KIM, WOOJUNG

정의
Complete Binary Tree
A가 B의 부모노드이면 A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.
이진트리(Binary Tree)는 부모의 자식이 0~2개인 트리인데 이진트리의 모양 에 따라 이진트리를 분류 할 수 있다.
Rooted Binary Tree 는 모든 노드의 자식이 최대 2개인 루트를 가진 트리
Full Binary Tree 단말 노드가 아닌 모든 노드가 2개의 자식을 가진트리
Complete Binary Tree 마지막 레벨을 제외하고 모든 노드가 채워진 이진트리, 마지막 레벨의 노드들은 왼쪽부터 채워져있다.
Perfect Binary Tree 루트(root)에서 부터 말단노드(leaf)까지의 거리가 모두 같은 트리
이중 Heap 은 Complete Binary Tree 의 꼴을 하고 있다.
reference
위키피디아 - 힙
위키피디아 - 이진트리
wikipedia - Heap
나무위키 - 힙 트리
이석호. C++ 자료구조론 (2nd ed.). 인피니티북스.

6.Heap에 대해서 알아보자.

댓글