2017-03-27 11 views
2

WAVL (약한 AVL)과 레드 블랙 트리의 차이점은 무엇입니까? RB보다 WAVL을 사용해야하는 특별한 이유가 있습니까?WAVL (약한 AVL)과 레드 블랙 트리의 차이점은 무엇입니까?

+0

안녕하세요, 스택 오버플로에 오신 것을 환영합니다. 이 질문에 대한 답변은 사실에 근거하지 않은 답변 또는 개인적 선호 때문에 편향된 답변이 될 수 있음에 유의하십시오. 아마도 각 옵션에 대해 주어진 목적을 달성하는 것이 더 나은 다른 사용 사례가있을 수 있습니다. 이에 대한 대답을 얻으려면 질문에 어떤 세부 사항을 추가하는 것을 고려하십시오.이를 어떻게 사용하고 싶은지, 각 옵션이 당신의 필요를 충족시키지 못하는 이유에 대해 생각해보십시오. 어떤 옵션이 당신에게 옳은지 알아낼 수 있기를 바랍니다 :) –

답변

1

WAVL 트리는 AVL 트리와 레드 블랙 트리의 최상의 특성을 결합하려는 시도입니다. WAVL 트리에 삽입하는 것만으로 AVL 트리와 동일한 트리를 만들 수 있습니다. 빨강 - 검정 트리보다 더 엄격하게 균형 잡힌 트리이므로 빨강 - 검정 트리가 더 불균형 해지는 상황에서 WAVL 트리가 더 잘 수행 될 것으로 예상 할 수 있습니다. WAVL의 삭제는 AVL 트리의 삭제보다 약간 간단합니다. WAVL 삭제는 1 ~ 2 회 회전 만 수행하고 잠재적으로 루트까지 중지하지 않습니다.

+0

말하기는 간단하지만 알고리즘에 대한 진실을 확인하는 데 도움이되는 웹상의 WAVL을 설명하는 것은 없습니다. –

+0

WAVL 나무에 관해 웹에서 필요한 모든 정보를 찾을 수있을 것 같습니다. 확인하려는 진실은 무엇입니까? 그 (것)들에 관하여 본래 종이는 모든 세부 사항을 포함하고 성과는 Ben Pfaff 2004 년 종이에서 포함되는 AVL 나무와 유사하다 (AVL 20 % 빨갛 검정보다는 더 빠른). –

+0

감사합니다. 나는 모든 규칙을 상세히 설명하는 원초적 종이를 읽고 싶었다. 또한 AVL은 Red Black Tree보다 20 % 빠릅니다. 재귀 또는 반복 사용, 새 노드 생성 방법 (뱅크에서 또는 아닌), 수행 작업 : 읽기 대 v 대 삭제 및시기와 같은 성능에 영향을 줄 수있는 많은 변수가 있기 때문에 이상하게 들립니다. 두 구현 모두 동일한 최적화를 공유합니다. 나는 당신의 대답에 참고 문헌 (링크)을 포함시키는 것이 좋을 것이다. 액세스 할 수없는 것 같습니다 ??? –