AVL트리에서 균형계수가 +2 혹은 -2가 되면 이뤄지는 회전에 대해서 이해가 안됩니다..ㅜㅜ LL회전과 LR회전 이런거요... 물론 소스그대로 포인터 연산은 소스수준에서는 이해가 가지만.. 왜 그렇게 해야하는지를 모르겠습니다. 다른분들은 어떻게 이해하셨나요....
AVL트리를 사용하는것은 빠른 검색을 필요로 할때 사용하는것입니다. insert나 delect시에는 느리지만 search를 할때는 2진 트리이기 때문에 빠른검색이 가능하기 때문입니다. 레벨 발란싱이나 이런것들은 트리가 단편화되서 한쪽에 트리로 몰리게 되면 시퀀스 서치나 차이가 없기 때문입니다. 답변이 되었기를 빌며^^
답변감사 ^^;
그런데... 거기까지는 알겠는데요. LL은 4개, LR같은경우 포인터를 6개가량 이동시켜줘야되잖아요... 이것을 그냥 외워야하는지...아니면 원칙이 있는건지 모르겠습니다.
흠...말로 설명하기는 어렵고...
그림을 그려서 회전 시켜보세요...
일정한 규칙이 있습니다...
바이너리 트리의 속성을 만족시키면서 자리를 바꾸려면 그렇게 할 수 밖에 없습니다...
소스 코드만 보지 마시고...그림을 그려서 한번 해보시면 금방 이해가 가실겁니다...
...
일단 그림을 그리신 다음에...
1. binary tree의 성질을 만족시켜야 한다는 점과,
2. sub-tree의 depth의 차이를 줄여야 한다는점
이 두가지 점을 생각하면서...트리를 바꿔보세요...
그러면 왜 그렇게 로테이션이 일어나야 하는지 쉽게 아실 수 있을겁니다...
텍스트 포맷에 대한 자세한 정보
<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]
AVL트리를 사용하는것은 빠른 검색을 필요로 할때 사용하는것입니다.i
AVL트리를 사용하는것은 빠른 검색을 필요로 할때 사용하는것입니다.
insert나 delect시에는 느리지만 search를 할때는 2진 트리이기 때문에 빠른검색이 가능하기 때문입니다.
레벨 발란싱이나 이런것들은 트리가 단편화되서 한쪽에 트리로 몰리게 되면 시퀀스 서치나 차이가 없기 때문입니다.
답변이 되었기를 빌며^^
답변감사 ^^;그런데... 거기까지는 알겠는데요.LL은 4개,
답변감사 ^^;
그런데... 거기까지는 알겠는데요.
LL은 4개, LR같은경우 포인터를 6개가량 이동시켜줘야되잖아요...
이것을 그냥 외워야하는지...아니면 원칙이 있는건지 모르겠습니다.
흠...
흠...말로 설명하기는 어렵고...
그림을 그려서 회전 시켜보세요...
일정한 규칙이 있습니다...
바이너리 트리의 속성을 만족시키면서 자리를 바꾸려면 그렇게 할 수 밖에 없습니다...
소스 코드만 보지 마시고...그림을 그려서 한번 해보시면 금방 이해가 가실겁니다...
...
일단 그림을 그리신 다음에...
1. binary tree의 성질을 만족시켜야 한다는 점과,
2. sub-tree의 depth의 차이를 줄여야 한다는점
이 두가지 점을 생각하면서...트리를 바꿔보세요...
그러면 왜 그렇게 로테이션이 일어나야 하는지 쉽게 아실 수 있을겁니다...
댓글 달기