참고로 rb 와 avl 트리 효율에 대해 이전에 올렸던 글이 있어서
링크해 둡니다. 근래에 제가 open source 로 진행중인
coral 라이브러리 프로젝트에 rb 도 구현해넣으려고 하는데,
여전히 rb 의 효율에 대해서는 의문이네요. 지금은 libavl 가지고
실시간 성능 테스트를 해보려 하는 중입니다.
아마 깊이는 2배까지 차이가 날 수 있을 겁니다.
일단 Big O notation으로는 Search Time이 AVL과 RB가 차이가 없을 겁니다. 그렇다고 해도 상수 차이로 인해서 Search가 AVL이 더 좋을 수가 있겠죠. 그러나 기껏해봐야 2배 이상 차이가 안 납니다. 그런데 노드의 추가 삭제가 자주 일어나는 상황이라면 AVL은 너무 오버헤드가 크게 되죠. 그에 비해 RB는 비교적 트리의 구조를 적게 바꾸고 추가 삭제를 하게 되죠. 그 점이 검색 시간의 차이보다 더 크게 작용해서 RB가 유용하게 되는 걸 겁니다.
MFC STL의 map, set 구조를 한번 보시기 바랍니다.
내부에서 xtree 라는걸 이용하고 있는데.
그 xtree가 red-black tree인걸로 알고 있습니다.
STL은 MFC의 일부가 아니라, 표준C++ 스펙의 일부입니다만;;
MFC소스를 아무리 봐도 STL의 소스는 안나오리라는 것이죠;;
압니다.
다만 MFC STL 이라고 언급한 이유는.
Visual Studio 6.0 에서 STL을 찾아가면서, 가장 쉽게 접근할 수 있기 때문이죠..
조금만 살펴보면, MFC에서 다른 회사의 STL코드를 가져가 쓴다는것을 알수 있을것입니다.
구입해서 사용한다가 보다 맞는 말이겠죠. ?
(우리가 MFC 살때 같이 사는건가. ? 머 그런 라이센스 문제는 그냥 넘어가겠습니다.)
WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra
압니다.
다만 MFC STL 이라고 언급한 이유는.
Visual Studio 6.0 에서 STL을 찾아가면서, 가장 쉽게 접근할 수 있기 때문이죠..
조금만 살펴보면, MFC에서 다른 회사의 STL코드를 가져가 쓴다는것을 알수 있을것입니다.
구입해서 사용한다가 보다 맞는 말이겠죠. ?
(우리가 MFC 살때 같이 사는건가. ? 머 그런 라이센스 문제는 그냥 넘어가겠습니다.)
무슨 의미인 것인지 모르겠군요. 한가지 질문을 먼저 드리겠습니다.
Visaul Studio에 STL이 있다고 적으신 것인지요? 아니면 MFC 속에 STL도 있다고 쓰신건가요?
압니다.
다만 MFC STL 이라고 언급한 이유는.
Visual Studio 6.0 에서 STL을 찾아가면서, 가장 쉽게 접근할 수 있기 때문이죠..
조금만 살펴보면, MFC에서 다른 회사의 STL코드를 가져가 쓴다는것을 알수 있을것입니다.
구입해서 사용한다가 보다 맞는 말이겠죠. ?
(우리가 MFC 살때 같이 사는건가. ? 머 그런 라이센스 문제는 그냥 넘어가겠습니다.)
무슨 의미인 것인지 모르겠군요. 한가지 질문을 먼저 드리겠습니다.
Visaul Studio에 STL이 있다고 적으신 것인지요? 아니면 MFC 속에 STL도 있다고 쓰신건가요?
일단 딴지를 목적으로 글을 올리시는 듯 해서..
어떤방법으로 대답을 하여도 벗어나기 힘들 지 않을까 하는 생각이 드네요..
알다시피 MFC에 STL이 있는것은 아닙니다.
하지만 Visual Studio 6.0 이라고 해야할지 Visual C++ 6.0이라고 해야 할 지...
거기에 STL이 제공된다고 해야겠죠...
물론 MS에서 자체제작된 STL이 아니라 http://www.dinkumware.com/ 에서 제공하는 STL을 이용하고 있는걸로 알고있는데..
이것도 틀린것은 아니겟죠 ??
PS:
음. 제가 글을 올리고 나니. 좀 딴지성이 느껴지네요.
님께서 단지 글을 잘못 올린것을 정정하고자 하는 의도였다면.
죄송스럽게 생각합니다.
WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra
압니다.
다만 MFC STL 이라고 언급한 이유는.
Visual Studio 6.0 에서 STL을 찾아가면서, 가장 쉽게 접근할 수 있기 때문이죠..
조금만 살펴보면, MFC에서 다른 회사의 STL코드를 가져가 쓴다는것을 알수 있을것입니다.
구입해서 사용한다가 보다 맞는 말이겠죠. ?
(우리가 MFC 살때 같이 사는건가. ? 머 그런 라이센스 문제는 그냥 넘어가겠습니다.)
무슨 의미인 것인지 모르겠군요. 한가지 질문을 먼저 드리겠습니다.
Visaul Studio에 STL이 있다고 적으신 것인지요? 아니면 MFC 속에 STL도 있다고 쓰신건가요?
일단 딴지를 목적으로 글을 올리시는 듯 해서..
어떤방법으로 대답을 하여도 벗어나기 힘들 지 않을까 하는 생각이 드네요..
알다시피 MFC에 STL이 있는것은 아닙니다.
하지만 Visual Studio 6.0 이라고 해야할지 Visual C++ 6.0이라고 해야 할 지...
거기에 STL이 제공된다고 해야겠죠...
물론 MS에서 자체제작된 STL이 아니라 http://www.dinkumware.com/ 에서 제공하는 STL을 이용하고 있는걸로 알고있는데..
이것도 틀린것은 아니겟죠 ??
PS:
음. 제가 글을 올리고 나니. 좀 딴지성이 느껴지네요.
님께서 단지 글을 잘못 올린것을 정정하고자 하는 의도였다면.
죄송스럽게 생각합니다.
보통은 그냥 "VC++ 내장 STL"이라고 말합니다.
열어봤는데 소스에 다음과 같이 되있네요.
/*
* Copyright (c) 1992-2002 by P.J. Plauger. ALL RIGHTS RESERVED.
* Consult your license regarding permissions and restrictions.
*/
/*
* This file is derived from software bearing the following
* restrictions:
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this
* software and its documentation for any purpose is hereby
* granted without fee, provided that the above copyright notice
* appear in all copies and that both that copyright notice and
* this permission notice appear in supporting documentation.
* Hewlett-Packard Company makes no representations about the
* suitability of this software for any purpose. It is provided
* "as is" without express or implied warranty.
V3.13:0009 */
theuhm님과 주고 받은 글을 보면서 이해가 안되는 부분이 있어서 글을 적었습니다. 내가 질문한 내용의 전자일 것이라 생각하고 있지만 htna님의 말을 직접 듣지 않는 한 그것은 추측에 불과하기 때문에 질문한 것입니다.
네 전자의 것을 얘기하려 했던것 입니다.
kkb110 wrote:
보통은 그냥 "VC++ 내장 STL"이라고 말합니다.
정확하게 가리키는 용어가 있는지는 모르겠습니다.
뭐. 어디서 부르느냐에 따라 틀린것이겠습니다만.
저희 회사에서는 그냥 STL 이라 하네요..
kkb110 wrote:
/*
* Copyright (c) 1992-2002 by P.J. Plauger. ALL RIGHTS RESERVED.
* Consult your license regarding permissions and restrictions.
*/
/*
* This file is derived from software bearing the following
* restrictions:
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this
* software and its documentation for any purpose is hereby
* granted without fee, provided that the above copyright notice
* appear in all copies and that both that copyright notice and
* this permission notice appear in supporting documentation.
* Hewlett-Packard Company makes no representations about the
* suitability of this software for any purpose. It is provided
* "as is" without express or implied warranty.
V3.13:0009 */
제가 영어가 좀 짧아서 그럽니다만.
여기의 내용이 Hewlett-Packard Company 의 STL이라는 것을 의미하는 것인가요?
그것보다는 자유로운 사용(사용, 복사, 수정, 재분배, 판매)을 위해서는 반드시 위의 내용을 포함하고 있어야 한다(위의 copyright 부분을 화일에 포함하고 있어야 한다)는 의미에 가까운것 같은데 말이죠...
MSDN을 봐도, Visual C++ 5.0 까지는 STL을 위해 Hewlett-Packard Company 의 것을 사용했다는 말은 있는데, 6.0 이상에 대해서는 언급이 없군요. http://www.dinkumware.com/ 에서는 6.0 부터 7.1 까지 지원하고 있다고 얘기하고 있구요...
WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra
여기의 내용이 Hewlett-Packard Company 의 STL이라는 것을 의미하는 것인가요?
그것보다는 자유로운 사용(사용, 복사, 수정, 재분배, 판매)을 위해서는 반드시 위의 내용을 포함하고 있어야 한다(위의 copyright 부분을 화일에 포함하고 있어야 한다)는 의미에 가까운것 같은데 말이죠...
MSDN을 봐도, Visual C++ 5.0 까지는 STL을 위해 Hewlett-Packard Company 의 것을 사용했다는 말은 있는데, 6.0 이상에 대해서는 언급이 없군요. http://www.dinkumware.com/ 에서는 6.0 부터 7.1 까지 지원하고 있다고 얘기하고 있구요...
이미 알고 계신 내용일지도 모르겠습니다만 STL과 HP는 상당히 관련이 많습니다.
STL 개발의 주역인 Alexander Stepanov가 HP에 재직할 당시에 STL의 기초를
마련했고 HP는 그 연구 결과를 공개했습니다. 말씀하신 내용은 STL의 아이디어가
HP에서 비롯되었음을 뜻하는 것 같습니다. 이와는 별도로 그 위쪽의 라이센스 조항은
MSVC++의 STL 구현이 Dinkumware의 Plauger에 의한 것임을 나타내는 것이고요.
여기의 내용이 Hewlett-Packard Company 의 STL이라는 것을 의미하는 것인가요?
그것보다는 자유로운 사용(사용, 복사, 수정, 재분배, 판매)을 위해서는 반드시 위의 내용을 포함하고 있어야 한다(위의 copyright 부분을 화일에 포함하고 있어야 한다)는 의미에 가까운것 같은데 말이죠...
MSDN을 봐도, Visual C++ 5.0 까지는 STL을 위해 Hewlett-Packard Company 의 것을 사용했다는 말은 있는데, 6.0 이상에 대해서는 언급이 없군요. http://www.dinkumware.com/ 에서는 6.0 부터 7.1 까지 지원하고 있다고 얘기하고 있구요...
이미 알고 계신 내용일지도 모르겠습니다만 STL과 HP는 상당히 관련이 많습니다.
STL 개발의 주역인 Alexander Stepanov가 HP에 재직할 당시에 STL의 기초를
마련했고 HP는 그 연구 결과를 공개했습니다. 말씀하신 내용은 STL의 아이디어가
HP에서 비롯되었음을 뜻하는 것 같습니다. 이와는 별도로 그 위쪽의 라이센스 조항은
MSVC++의 STL 구현이 Dinkumware의 Plauger에 의한 것임을 나타내는 것이고요.
네...
제가 오해를 한 듯 합니다.
Hewlett-Packard Company 에서 만든 STL을 사용한다는 의미였었나 하고 받아들였었습니다.
그냥 단순이 STL code를 열어보니, 저러한 license 항목이 있었구나 라는 얘기였었는듯 하네요..
^^
요즘 부족한 실력에도 불구하고, KDLP에 글을 자주 올리게 되네요..
많이 배우고 있습니다.
PS:
대략적인 스토리는 알고 있었지만,
누가 어디서 같이 지명이나 그러한 것에대해서는 대략 기억을 안하는 편입니다. ( 귀찮이즘의 압박이.. ^^; )
잘 듣고 갑니다..
WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra
AVL이 회전수가 적은데 회전을 해야하는 상황이 자주 일어나고 rb는 회전수가 많지만 그런 일이 잘 안 일어나죠. 한번 일어났다고 하면 경우에 따라 여러번 회전을 해야 하죠. AVL은 한번만 (제가 보기엔 사실은 두번까지..) 하면 되죠.
그렇다면 만약에 소팅된 자료가 순서대로 들어오면 rb는 불리해지는 겁니다. 그런데 자료가 추가되고 삭제되는 횟수가 비슷하고 좋은 랜덤성을 띈다면 rb는 회전을 계속 안 하게 될지도 모르죠.(특히 자료의 수가 많아지면 rb가 많이 회전해야 할 상황이 올 확률이 낮겠죠.) 그런데 회전을 하는 상황이 많이 일어나고자 어떤 자료를 만든다면... AVL이 더 좋아지죠. 소팅된 자료가 들어오는 경우가 그 큰 예가 되겠죠.
rb는 운에 어느정도 작용하고 AVL은 회전수가 1,2인것을 거의 보장하므로 실시간으로 처리해줘야 하는 것에는 AVL이 더 좋을것 같습니다.(대충 걸리는 시간을 어느정도 예상 가능?) 평균은 rb가 더 좋은것 같은 느낌은 그냥 제 느낌이구요.. 별 차이 없다고 생각합니다. 아주아주 많이 많이 과장하자면 머지소트와 퀵소트 같은 느낌이네요.
MFC STL의 map, set 구조를 한번 보시기 바랍니다.내부에서
MFC STL의 map, set 구조를 한번 보시기 바랍니다.
내부에서 xtree 라는걸 이용하고 있는데.
그 xtree가 red-black tree인걸로 알고 있습니다.
WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra
기본적인 개념은 Fundamentals of Data Structures
기본적인 개념은 Fundamentals of Data Structures in C 책의 마지막 장인 Search Structures를 보세요.
구현 참조는 리눅스 커널 소스에서 /usr/src/linux/lib/rbtree.c, 그리고 다음의 사이트를 보시면 도움이 되실듯 하네요.
* http://libredblack.sourceforge.net/
* http://www.eli.sdsu.edu/courses/fall96/cs660/notes/redBlack/redBlack.html#RTFToC1
감사합니다. ^^아주 조금 감이 잡히긴 하는데 아직 잘 모르겠네요.
감사합니다. ^^
아주 조금 감이 잡히긴 하는데 아직 잘 모르겠네요.
rb트리를 보다보니 깊이가 2개가 차이가 날수도 있더군요 -.-
avl에서는 이런경우가 없는데요...
rb보다 avl이 효율적이지 않나요?
^^
Introduction to Algorithm 에 rb tree 가 자세하게 나옵니다.
13. Red-Black Tree
-----------
청하가 제안하는 소프트웨어 엔지니어로써 재미있게 사는 법
http://sozu.tistory.com
[quote]감사합니다. ^^ 아주 조금 감이 잡히긴 하는데 아직 잘
혹시 위의 트리 그림이 프로그램에서 생성해준건가요???
그렇다믄... 어떤 라이브러리인지.... 궁금하네요...
아님.. 직접 만드셨나요?
콘솔에서 트리 그리다가 대충 끝내긴 했는데....
콘솔 넓이 때문에 31개 짜리 포화이진 트리 이상은 무리더라구요...쩝...
Re: red black tree 구현한 좋은 소스 없나요?
위에서 소개해 주셨는데, 저도 Introduction to algorithms
참고하고 있구요.
GNU libavl 이 있는데 여기 rb 구현도 있습니다. 이 제작자도
이 책을 참고했다고 적혀있습니다.
http://www.stanford.edu/~blp/avl/
참고로 rb 와 avl 트리 효율에 대해 이전에 올렸던 글이 있어서
링크해 둡니다. 근래에 제가 open source 로 진행중인
coral 라이브러리 프로젝트에 rb 도 구현해넣으려고 하는데,
여전히 rb 의 효율에 대해서는 의문이네요. 지금은 libavl 가지고
실시간 성능 테스트를 해보려 하는 중입니다.
http://bbs.kldp.org/viewtopic.php?t=3499&highlight=avl
Orion Project : http://orionids.org
RB와 AVL
아마 깊이는 2배까지 차이가 날 수 있을 겁니다.
일단 Big O notation으로는 Search Time이 AVL과 RB가 차이가 없을 겁니다. 그렇다고 해도 상수 차이로 인해서 Search가 AVL이 더 좋을 수가 있겠죠. 그러나 기껏해봐야 2배 이상 차이가 안 납니다. 그런데 노드의 추가 삭제가 자주 일어나는 상황이라면 AVL은 너무 오버헤드가 크게 되죠. 그에 비해 RB는 비교적 트리의 구조를 적게 바꾸고 추가 삭제를 하게 되죠. 그 점이 검색 시간의 차이보다 더 크게 작용해서 RB가 유용하게 되는 걸 겁니다.
블로그: http://turtleforward.blogspot.com
위의 이미지는 이 프로그램을 캡쳐한겁니다. ^^http://webpa
위의 이미지는 이 프로그램을 캡쳐한겁니다. ^^
http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm
답변 감사드립니다.
혹시나해서 물어봅니다. ^^
2배까지 차이가 난다는게...2개가 아닌지요... :oops:
조금 생각해보니 2배가 맞는말인것 같네요.... :) 레드블렉트
조금 생각해보니 2배가 맞는말인것 같네요.... :)
레드블렉트리의 정의자체가 블랙의 깊이만 양쪽이 똑같으면 되니깐,
한쪽엔 블렉만 넣고, 한쪽엔 레드와 블렉을 섞에서 넣으면.....?
틀릴지도 모르겠지만...지금 추측하기엔 이렇네요 ^^
libavl 저자 홈페이지에 균형트리의 구현에 대해 비교해놓은 논문이 있
libavl 저자 홈페이지에 균형트리의 구현에 대해 비교해놓은 논문이 있네요.
http://www.stanford.edu/~blp/papers/index.html
http://www.stanford.edu/~blp/papers/libavl.pdf
Splay tree도 구현할 후보에 올려놓으세요. 구현이 간단하고 실제 성능도 꽤 좋습니다.
[quote="htna"]MFC STL의 map, set 구조를 한번 보
STL은 MFC의 일부가 아니라, 표준C++ 스펙의 일부입니다만;;
MFC소스를 아무리 봐도 STL의 소스는 안나오리라는 것이죠;;
..
[quote="theuhm"][quote="htna"]MFC STL의 m
압니다.
다만 MFC STL 이라고 언급한 이유는.
Visual Studio 6.0 에서 STL을 찾아가면서, 가장 쉽게 접근할 수 있기 때문이죠..
조금만 살펴보면, MFC에서 다른 회사의 STL코드를 가져가 쓴다는것을 알수 있을것입니다.
구입해서 사용한다가 보다 맞는 말이겠죠. ?
(우리가 MFC 살때 같이 사는건가. ? 머 그런 라이센스 문제는 그냥 넘어가겠습니다.)
WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra
[quote="cdpark"]libavl 저자 홈페이지에 균형트리의 구현
미처 이 논문은 발견하지 못했었군요. 감사합니다.
지난번 직접 질문했을 때는 자기도 모른다 했었는데, 그 이후 테스트를 진행했나봅니다.
결론은 다음과 같은데요.
하지만, Real world 테스트에서는 AVL 이 가장 좋은 결과를
보여주고 있네요. 이것은 AVL 이 '차후 접근'에서 높이가 RB보다
낮기 때문에 유리한 것 같습니다.
저는 노드 추가시 RB 의 최대 회전수가 lg n 임에 비해 AVL 최대
회전수는 1 이어서 트리 높이가 2만 되어도 AVL 최대 회전수와
같아지기 때문에, 노드 추가시에도 AVL 이 더 빠르지 않을까
생각했는데, 노드 추가시 회전수는 RB 가 더 작은 것 같군요.
실험적인 벤치마크 결과이고, Real world 테스트가 아닌 결과들은
RB 나 AVL 이나 시간차가 작은 편이라, 결과적으로는 '모두
구현하는 게 속편하다' 일 것 같군요. :)
Orion Project : http://orionids.org
[quote="htna"]압니다.다만 MFC STL 이라고 언급한 이
무슨 의미인 것인지 모르겠군요. 한가지 질문을 먼저 드리겠습니다.
Visaul Studio에 STL이 있다고 적으신 것인지요? 아니면 MFC 속에 STL도 있다고 쓰신건가요?
- 죠커's blog / HanIRC:#CN
[quote="CN"][quote="htna"]압니다.다만 MFC S
일단 딴지를 목적으로 글을 올리시는 듯 해서..
어떤방법으로 대답을 하여도 벗어나기 힘들 지 않을까 하는 생각이 드네요..
알다시피 MFC에 STL이 있는것은 아닙니다.
하지만 Visual Studio 6.0 이라고 해야할지 Visual C++ 6.0이라고 해야 할 지...
거기에 STL이 제공된다고 해야겠죠...
물론 MS에서 자체제작된 STL이 아니라 http://www.dinkumware.com/ 에서 제공하는 STL을 이용하고 있는걸로 알고있는데..
이것도 틀린것은 아니겟죠 ??
PS:
음. 제가 글을 올리고 나니. 좀 딴지성이 느껴지네요.
님께서 단지 글을 잘못 올린것을 정정하고자 하는 의도였다면.
죄송스럽게 생각합니다.
WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra
[quote="htna"]님께서 단지 글을 잘못 올린것을 정정하고자 하는
정정하고자 하는 것도 아니며 딴지 걸고자 하는 것도 아닙니다. 굳이 의미를 부여하자면 확실히 하고 싶었다가 맞을 겁니다.
theuhm님과 주고 받은 글을 보면서 이해가 안되는 부분이 있어서 글을 적었습니다. 내가 질문한 내용의 전자일 것이라 생각하고 있지만 htna님의 말을 직접 듣지 않는 한 그것은 추측에 불과하기 때문에 질문한 것입니다.
- 죠커's blog / HanIRC:#CN
[quote="htna"][quote="CN"][quote="htna"]
보통은 그냥 "VC++ 내장 STL"이라고 말합니다.
열어봤는데 소스에 다음과 같이 되있네요.
[quote="CN"]theuhm님과 주고 받은 글을 보면서 이해가 안되
네 전자의 것을 얘기하려 했던것 입니다.
정확하게 가리키는 용어가 있는지는 모르겠습니다.
뭐. 어디서 부르느냐에 따라 틀린것이겠습니다만.
저희 회사에서는 그냥 STL 이라 하네요..
제가 영어가 좀 짧아서 그럽니다만.
여기의 내용이 Hewlett-Packard Company 의 STL이라는 것을 의미하는 것인가요?
그것보다는 자유로운 사용(사용, 복사, 수정, 재분배, 판매)을 위해서는 반드시 위의 내용을 포함하고 있어야 한다(위의 copyright 부분을 화일에 포함하고 있어야 한다)는 의미에 가까운것 같은데 말이죠...
MSDN을 봐도, Visual C++ 5.0 까지는 STL을 위해 Hewlett-Packard Company 의 것을 사용했다는 말은 있는데, 6.0 이상에 대해서는 언급이 없군요.
http://www.dinkumware.com/ 에서는 6.0 부터 7.1 까지 지원하고 있다고 얘기하고 있구요...
WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra
[quote="htna"]여기의 내용이 Hewlett-Packard
이미 알고 계신 내용일지도 모르겠습니다만 STL과 HP는 상당히 관련이 많습니다.
STL 개발의 주역인 Alexander Stepanov가 HP에 재직할 당시에 STL의 기초를
마련했고 HP는 그 연구 결과를 공개했습니다. 말씀하신 내용은 STL의 아이디어가
HP에서 비롯되었음을 뜻하는 것 같습니다. 이와는 별도로 그 위쪽의 라이센스 조항은
MSVC++의 STL 구현이 Dinkumware의 Plauger에 의한 것임을 나타내는 것이고요.
[quote="doldori"][quote="htna"]여기의 내용이
네...
제가 오해를 한 듯 합니다.
Hewlett-Packard Company 에서 만든 STL을 사용한다는 의미였었나 하고 받아들였었습니다.
그냥 단순이 STL code를 열어보니, 저러한 license 항목이 있었구나 라는 얘기였었는듯 하네요..
^^
요즘 부족한 실력에도 불구하고, KDLP에 글을 자주 올리게 되네요..
많이 배우고 있습니다.
PS:
대략적인 스토리는 알고 있었지만,
누가 어디서 같이 지명이나 그러한 것에대해서는 대략 기억을 안하는 편입니다. ( 귀찮이즘의 압박이.. ^^; )
잘 듣고 갑니다..
WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra
결과를 보면...
이제 실험 결과까지 나와있네요. 대충 예상했던 것이랑 비슷하네요.
AVL이 회전수가 적은데 회전을 해야하는 상황이 자주 일어나고 rb는 회전수가 많지만 그런 일이 잘 안 일어나죠. 한번 일어났다고 하면 경우에 따라 여러번 회전을 해야 하죠. AVL은 한번만 (제가 보기엔 사실은 두번까지..) 하면 되죠.
그렇다면 만약에 소팅된 자료가 순서대로 들어오면 rb는 불리해지는 겁니다. 그런데 자료가 추가되고 삭제되는 횟수가 비슷하고 좋은 랜덤성을 띈다면 rb는 회전을 계속 안 하게 될지도 모르죠.(특히 자료의 수가 많아지면 rb가 많이 회전해야 할 상황이 올 확률이 낮겠죠.) 그런데 회전을 하는 상황이 많이 일어나고자 어떤 자료를 만든다면... AVL이 더 좋아지죠. 소팅된 자료가 들어오는 경우가 그 큰 예가 되겠죠.
rb는 운에 어느정도 작용하고 AVL은 회전수가 1,2인것을 거의 보장하므로 실시간으로 처리해줘야 하는 것에는 AVL이 더 좋을것 같습니다.(대충 걸리는 시간을 어느정도 예상 가능?) 평균은 rb가 더 좋은것 같은 느낌은 그냥 제 느낌이구요.. 별 차이 없다고 생각합니다. 아주아주 많이 많이 과장하자면 머지소트와 퀵소트 같은 느낌이네요.
블로그: http://turtleforward.blogspot.com
댓글 달기