안녕하세요?
허프만 코드를 이용해서 압축 프로그램을 구현중에 있습니다.
트리를 이용하여 구현을 할 계획인데..
보통 트리는 root부터 삽입이 들어가잖나여..
근데 예를 들어서 리프(leaf)노트가 10개가 주어지고
이 리프노드를 이용해서 트리를 밑에서 구성해서 root까지 올라가는
방법이 뭐 없을까여?
흠.. 잠깐 생각해봤는데, 별로 좋은 방법이 아닌 것 같습니다.
첫째로, 일단 말씀하시는 tree를 보면, 그 트리는 node 추가가 어려울 것 같습니다. 나중에 node가 늘어나게 되면, leaf node가 늘어날텐데 그 경우는 어쩌실 생각인가요?
둘째로, 그와 같은 tree를 만들었다 해도, 어떤 algorithm을 쓰실 생각인가요? 아주 특이한 경우가 없다면, 대개 root부터 시작하는게 tree의 장점을 가장 잘 살리는 것이라 생각합니다.
궂이 leaf node에서 시작하는 tree를 만들겠다면, 그리고 Huffman tree라면, binary tree일 것이므로, array로 만드는게 무난할 거라 봅니다.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html Korean Ver: http://cinsk.github.io/cfaqs/
트리를 상향식(Bottom-Up)과 하향식(Top-Down) 으로 나눌 수 있다고 합니다.
이름 그대로 상향식은 Leaf에서 삽입이 발생하여 root를 생성하는 것이고, 하향식은 root에서 삽입이 발생하여 Leaf 를 생성하는 것을 말합니다.
바이너리 트리와 같은 종류를 하향식 트리라고 하겠죠... 바이너리 트리의 삽입 연산에 대해서 정확히 이해 한다면 당근 삽입은 Root에서 발생하기 때문에 Leaf를 먼저 구성한다는 이야기는 트리의 정의에 위배가 됩니다.
참고로 상향식 트리중 대표적인게 B-Tree 입니다. 비슷한 종류로 B+Tree, B*-Tree 등이 있습니다.
세상은 하나..........
허프만트리 구현한걸 참고하시면 돔이 될듯합니다. 참고만 하세요...http://www.hanbitbook.co.kr/web/examples/1063
텍스트 포맷에 대한 자세한 정보
<code>
<blockcode>
<apache>
<applescript>
<autoconf>
<awk>
<bash>
<c>
<cpp>
<css>
<diff>
<drupal5>
<drupal6>
<gdb>
<html>
<html5>
<java>
<javascript>
<ldif>
<lua>
<make>
<mysql>
<perl>
<perl6>
<php>
<pgsql>
<proftpd>
<python>
<reg>
<spec>
<ruby>
<foo>
[foo]
흠.. 잠깐 생각해봤는데, 별로 좋은 방법이 아닌 것 같습니다.첫
흠.. 잠깐 생각해봤는데, 별로 좋은 방법이 아닌 것 같습니다.
첫째로, 일단 말씀하시는 tree를 보면, 그 트리는 node 추가가 어려울
것 같습니다. 나중에 node가 늘어나게 되면, leaf node가 늘어날텐데 그
경우는 어쩌실 생각인가요?
둘째로, 그와 같은 tree를 만들었다 해도, 어떤 algorithm을 쓰실 생각인가요?
아주 특이한 경우가 없다면, 대개 root부터 시작하는게 tree의 장점을 가장
잘 살리는 것이라 생각합니다.
궂이 leaf node에서 시작하는 tree를 만들겠다면, 그리고 Huffman tree라면,
binary tree일 것이므로, array로 만드는게 무난할 거라 봅니다.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
Korean Ver: http://cinsk.github.io/cfaqs/
상향식 트리와 하향식 트리
트리를 상향식(Bottom-Up)과 하향식(Top-Down) 으로 나눌 수 있다고 합니다.
이름 그대로 상향식은 Leaf에서 삽입이 발생하여 root를 생성하는 것이고, 하향식은 root에서 삽입이 발생하여 Leaf 를 생성하는 것을 말합니다.
바이너리 트리와 같은 종류를 하향식 트리라고 하겠죠... 바이너리 트리의 삽입 연산에 대해서 정확히 이해 한다면 당근 삽입은 Root에서 발생하기 때문에 Leaf를 먼저 구성한다는 이야기는 트리의 정의에 위배가 됩니다.
참고로 상향식 트리중 대표적인게 B-Tree 입니다. 비슷한 종류로 B+Tree, B*-Tree 등이 있습니다.
세상은 하나..........
허프만트리 구현한걸 참고하시면 돔이 될듯합니다.참고만 하세요...
허프만트리 구현한걸 참고하시면 돔이 될듯합니다.
참고만 하세요...
http://www.hanbitbook.co.kr/web/examples/1063
댓글 달기