EzDoum

찾기
처음으로 | 찾기 | 아카이브 | 글 올리기 | 링크 | 자료실 | 통계 | 연락처 | 자유게시판
이지도움 특집
전체보기
네트워크
TI OMAP35x
TI DaVinci
Analog Blackfin
RobotWar2005
임베디드!
캐쉬의 모든것
메모리 할당 알고리즘
CPU 파이프라이닝
자료구조(Tree)
금융

Login
이름

암호

기억하기


사용자 등록

현재 접속중인 등록 사용자는 0명, 익명 사용자는 5명 입니다.
전체 등록 사용자: 751명

마지막 답장
·libcurl + fuse 조합으로 되는게 많네. (1)
·Linux Ftrace에 관해 (3)
·Android MTP ( Media Transfer Protocol ) (1)
·Lighttpd에 인증을 digest 사용시 IE 오동작 문제? (1)
·Dtrace에 관해 (1)

최근글
·OpenSSL and multi-threads (0)
·ARM 환경에서 OpenCL 사용 (0)
·IoT용 WIFI 모듈 비교 ( MCU ) 클래스 (0)
·Glances - 리눅스 여러 가지 항목을 한 화면에서 모니터링 (0)
·plugin 방식의 로그 분석기 (0)

뜨거운 감자
·나는 인터렉티브한 환경에서 역어셈블 한다. (12)
·GNU REGEX (정규표현식) 프로그래밍 강좌 (7)
·SoCRobotWar 2005 - 신입생 기초 교육자료 (7)
·ASP.NET의 데이터 그리드와 사용자 컨트롤 (7)
·DHTML Editing Control (7)

가장 많이 읽은 글
·[Cache] 2-way Set-Associative 방식이란 무엇일까? (2)
·멀티쓰레드(Pthread) 프로그래밍
·GNU REGEX (정규표현식) 프로그래밍 강좌 (7)
·Sorting Algorithm Animation (2)
·SoCRobotWar 2005 - 신입생 기초 교육자료 (7)

트리 발전사라고 해야 하나 ^^?
글쓴이: EzDoum 글쓴날: 2002년 07월 01일 오전 01:31




각종 트리를 구현하는 알고리즘을 정리하던 중에,
C로 배우는 알고리즘 1권에 균형트리에 관한 종합적인 이해를 제공하는
글이 있어서... 올려봅니다.

이진트리 -> AVL트리 -> 2-3트리 -> 2-3-4트리 -> Red-Black트리, B-트리 -> T-트리

이 순서 대로 공부하면 더 이해가 잘되리라고 생각합니다.
전 엉뚱하게도 거꾸로 접근해서 좀 삽질좀 했습니다 ;;


● 균형잡는 나무 구조들의 분석

여러가지의 많은 균형잡는 나무 구조들을 알아보았지만 이들은 크게 이진 나무를 그대로 사용하는 균형잡는 나무 구성법과 M-노드로 나무를 구성하는 법 두 가지로 구분될 수 있을 것이다.

이진 나무를 그대로 이용하는 구성법은 AVL 나무와 빨강-검정 나무가 있다. AVL 나무는 균형의 유지 상태를 저장하는 균형도(Balance Factor)라는 정보를 필요로 했으며 이 균형도는 AVL 나무에 자료가 삽입되거나 삭제될 때 다시 전체적으로 갱신되어야 하는 단점이 있었다. 하지만 중요한 개념들(나무의 회전이나 균형도)은 이후의 균형잡는 나무들에 큰 영향을 미쳤다.

빨강-검정 나무는 노드의 색깔을 저장하는 1비트의 플랙으로 나무의 전체적인 균형을 잡는다. 빨강-검정 나무는 개념적으로 2-3-4 나무와 똑같지만 이진 나무 구조를 그대로 사용하는 점이 2-3-4 나무에 비해서 가지는 장점이다. 빨강-검정 나무는 색상 변환과 회전을 통하여 균현을 유지하는 절묘하고 복잡한 동작들이 정의되어야 한다.

M-노드로 구성하는 법은 2-3 나무와 2-3-4 나무를 알아보았는데 2-3 나무는 역추적하여 나무를 다시 구성해야 하는 단점이 있어서 치명적이었다. 하지만 2-3-4 나무는 4-노드의 분할을 위해서 역추적할 필요가 없기 때문에 훨씬 간편한다. M-노드로 구성되는 법은 메모리에서 구현하기에는 약간 무리가 따른다. 일단은 프로그램을 작성하면 낭비되는 메모리 양이 많아진다. 2-3-4나무를 위해서는 노드의 구조가 3개의 키와 4개의 링크를 준비해야 하는데, 2-노드를 저장하면 노드의 절반 가량이 낭비된다. M-노드로 구성하는 법은 확장되어서 이후에 다르게 될 B-나무라는 막강한 검색법으로 발전된다. B-나무는 외부 검색(DISK)에서 좋은 효율을 보이는 균형잡는 검색 나무 구조이다.


ps.

그리고 이것은 각종 트리를 애플릿으로 구현한 것인데,
제가 지금까지 본 예제중에 가장 이해하기 쉽게 만든 것이더군요;;

AVL Tree Applet (splay, Red-black, AVL tree)
http://www.seanet.com/users/arsen/avltree.html

요것 가지고 실험을 해보세요. 음 임의 값을 순서대로 적고 손으로
트리 모양을 그린 다음, 실제로 하나씩 넣어 보는 거죠;;;
그럼 잘 이해했나 알수 있을 껍니다.

아 마지막으로 한가지더, 일전에 올린 libavl를 보신분은 알겠지만,
트리에서 부모를 가지고 댕기거나 이전 다음 링크(threaded tree)를 들고 다니면 더욱
재미난 일들을 할수가 있죠..


[분류: C/C++ 인쇄용 페이지 본문 email로 보내기 ]

<  AVL Tree vs Red-Black Tree | Tree Rebalancing in Optimal Time and Space  >
트리 발전사라고 해야 하나 ^^? | 답장: 4개 | 본문에 답장
정렬 :  
icon_confused.gif 익명 2002년 07월 02일 오후 06:08 [ 이글에 답장 | 본문에 답장 | 책갈피 ]
공부하는 직장인입니다.

트리 이야기가 많이 나오는데

트리가 쓰이는 곳은 어디며 어떻게 활용하는지요.

옛날부터 궁금하던거라...^^

건승하세요.


답장 EzDoum 2002년 07월 02일 오후 10:36 [ 이글에 답장 | 본문에 답장 | 책갈피 ]
대부분 프로그래밍을 할때 자료구조로 사용하는 것이 예상되는
최대 크기로 배열을 선언해서 데이터를 저장합니다.
이렇게 하면 코딩은 간단해지나, 메모리 낭비가 심하고 최대값에
도달하게 되면 더 이상 자료를 찾을 수가 없게 되지요.

또, 배열에 들어간 자료는 정렬이 되어 있지 않아서, 내가 원하는
자료를 찾을려고 한다면 처음부터 순차적으로 뒤져야 하는
불편함도 있습니다.

이 두가지 이유가 트리를 사용하는 이유입니다.
즉, 필요할 때 메모리를 할당해서 사용을 하고,
데이터가 정렬이 되어 있어서 빠르게 검색이 필요할 때
트리가 사용됩니다.

주로 사용되는 용도는, 데이터베이스 처럼 정렬된 자료구조가
필요한 곳이겠죠.
--
걀걀걀...
[수정]

답장 익명 2002년 08월 10일 오전 01:21 [ 이글에 답장 | 본문에 답장 | 책갈피 ]
사람들이 잘못 알고 있는 것중에 하나가
AVL-Tree가 Balancing할 때
균형도(Balance Factor)를 다시 잡아야
하기때문에 느릴 것이다라고 합니다..
하지만 그런 논리는 AVL-tree를 안짜본 사람들이
남들이 만들어 논 책을 보고 하는 소리죠..
실제 Balance Factor를 다시 해준다고 해도
고작 3개~5개의 노드만 해주면 됩니다.
그 알고리즘은 글로 적기에 너무 길어서 생략하구요.
지금 까지 나온 알고리즘중 가장 빠른 검색, 삽입,삭제 속도를
가졌다는 겁니다...
AVL tree알고리즘을 직접 제작 않하신분들이어 깨어나십시오
관련 사이트 : http://www.hughes.com.au/
에 가시면 Mini SQL소스가 있습니다.
그중 avl*tree.c라는 소스를 찾아서 분석 해 보세요..
정말 Miracle한 소스입니다.


답장 EzDoum 2002년 08월 10일 오후 02:29 [ 이글에 답장 | 본문에 답장 | 책갈피 ]
이진 트리 효율에 관한 토론
http://kldp.org/script/bbs/read.php?table=qa2&no=2788&o[sc]=a&o[ss]=AVL&o[st]=a&o[at]=s&o[sct]=s&o[stt]=s
--
걀걀걀...
[수정]

트리 발전사라고 해야 하나 ^^? | 답장: 4개 | 본문에 답장
정렬 :  

답장 쓰기
글을 올리시려면 로그인 (사용자 등록) 하셔야 합니다.

검색
Google

분류
·공지 (6)
·인터넷 (87)
·하드웨어 (260)
·C/C++ (65)
·어셈블리 (7)
·리눅스 (136)
·리눅스 커널 (67)
·윈도우즈 (25)
·데이터베이스 (20)
·보안 (16)
·.NET (25)
·그래픽 (13)
·책소개 (42)
·호기심 천국 (80)
·잡담 (111)
·사랑 (3)

전체 본문수: 963
전체 답장수: 525


분류 : C/C++
최근글
최근글
가장 많이 읽은 글
·Sorting Algorithm Animation (2)
뜨거운 감자
·눈으로 보는 자료구조 (5)

EzDoum투표
이지도움 어때요?
이게 뭐야. 다시 안올란다. --;
아이 좋아라~ +_+;
관심없다.
먼가는 있는거 같은데 뭐하는 곳이지?
기타 (자유게시판에 글로 남겨 주세요)
[ 결과 | 투표 ]

랜덤 링크
http://kldp.net


 Home ^ BACK TO TOP ^ EzDoum - 도움이 필요하세요~??
 Powered by KorWeblog 1.5.8 Copyleft © 2001 EzDoum, 관리자: EzDoum