이진 트리 균형 (AVL)

StackOverflow https://stackoverflow.com/questions/133610

문제

좋아, 이것은 CS 사람들을위한 이론 영역의 또 다른 것입니다.

90 년대에 나는 BST를 구현하는 데 상당히 잘했습니다. 내가 머리를 돌릴 수없는 유일한 것은 이진 트리 (AVL)의 균형을 잡기 위해 알고리즘의 복잡성이었습니다.

너희들이 나를 도울 수 있습니까?

도움이 되었습니까?

해결책

희생양 트리는 아마도 가장 간단한 균형 결정 알고리즘을 가지고있을 수 있습니다. 삽입으로 새 노드가 너무 깊어지면 높이 균형보다는 무게 균형을 보면 재조정되는 노드를 찾습니다. 삭제에 대한 재조정 여부에 대한 규칙도 간단합니다. 노드에 비전 정보를 저장하지 않습니다. 그것이 옳다는 것을 증명하는 것은 까다 롭지 만 알고리즘을 이해하기 위해 필요하지 않습니다 ...

그러나 AVL과 달리 항상 높이 균형이 맞지 않습니다. Red-Black과 마찬가지로 불균형이 제한되지만 Red-Black과 달리 매개 변수로 조정할 수 있으므로 대부분의 실제 목적으로 필요한만큼 균형이 맞습니다. 그래도 너무 단단히 조정하면 최악의 삽입에 대해 AVL보다 나쁘거나 나쁘게 끝납니다.

질문 편집에 대한 응답

나는 AVL 나무를 이해하는 개인적인 길을 제공 할 것입니다.

먼저 트리 회전이 무엇인지 이해해야하므로 AVL 알고리즘을들은 다른 모든 것을 무시하고 이해합니다. 오른쪽 회전이고 왼쪽 회전 인 머리에 똑바로 들어가고, 각각이 나무에하는 일, 그렇지 않으면 정확한 방법에 대한 설명은 당신을 혼란스럽게 할 것입니다.

다음으로 AVL 나무의 균형을 맞추기위한 트릭은 각 노드가 왼쪽과 오른쪽 하위 트리의 높이의 차이를 기록한다는 것입니다. '높이 균형'의 정의는 트리의 모든 노드에 대해 -1에서 1 사이에 있다는 것입니다.

다음으로, 노드를 추가하거나 제거한 경우 트리의 균형이 맞지 않을 수 있습니다. 그러나 추가하거나 제거한 노드의 조상 인 노드의 균형 만 변경할 수 있습니다. 따라서, 당신이해야 할 일은 트리를 백업하고, 회전을 사용하여 찾은 불균형 노드의 균형을 맞추고, 균형 점수를 다시 균형을 잡을 때까지 균형 점수를 업데이트하는 것입니다.

이해의 마지막 부분은 괜찮은 참조에서 찾은 각 노드를 재조정하는 데 사용되는 특정 회전을 찾는 것입니다. 이것은 높은 개념과 반대로 "기술"입니다. AVL 트리 코드를 수정하는 동안 또는 데이터 구조 시험 중에는 세부 사항 만 기억하면됩니다. Debugger에서 AVL 트리 코드를 열어 놓은 지 몇 년이 지났습니다. 구현은 그들이 일하는 지점에 도달 한 다음 계속 일하는 경향이 있습니다. 그래서 나는 정말로 기억하지 못한다. 몇 개의 포커 칩을 사용하여 테이블에서 작업 할 수는 있지만 실제로 모든 경우가 많지는 않습니다 (많은 것은 아닙니다). 그것을 찾는 것이 가장 좋습니다.

그런 다음 모든 것을 코드로 번역하는 사업이 있습니다.

코드 목록을 보는 것이 마지막 단계를 제외한 모든 단계에서 많은 도움이된다고 생각하지 않으므로 무시하십시오. 코드가 명확하게 작성된 최선의 경우에도 프로세스에 대한 교과서 설명처럼 보이지만 다이어그램이 없습니다. 보다 일반적인 경우에는 C 구조 조작의 혼란입니다. 그러니 책을 고수하십시오.

다른 팁

노드 밸런싱 알고리즘에 대한 완전한 코드를 게시하는 것이 좋지 않다고 생각합니다. 그러나 Wikipedia 기사 빨간색 나무 알고리즘의 완전한 C 구현과 AVL 나무 고품질 구현에 대한 몇 가지 링크도 있습니다.

이 두 구현은 대부분의 일반 목적 시나리오에 충분합니다.

나는 최근에 AVL 나무와 함께 일을 해왔다.

균형을 잡는 방법에 대한 최선의 도움은 Google 검색이었습니다.

방금이 의사 코드를 코딩했습니다 (회전 방법을 이해하면 구현하기가 매우 쉽습니다).

IF tree is right heavy
{
  IF tree's right subtree is left heavy
  {
     Perform Double Left rotation 
  }
  ELSE
  {
     Perform Single Left rotation
  }
}
ELSE IF tree is left heavy
{
  IF tree's left subtree is right heavy
  {
     Perform Double Right rotation
  }
  ELSE
  {
     Perform Single Right rotation
  }
}

나는 완전한 프로그램이 적절하지 않다는 데 동의합니다.

고전적인 AVL과 RB 트리는 결정 론적 접근 방식을 사용하지만, 나는 살펴 보는 것이 좋습니다. "무작위 이진 검색 트리"키의 통계 분포에 관계없이 균형을 유지하고 균형을 유지하는 데 비용이 적게 들고 균형이 적습니다.

AVL 트리는 삽입/삭제 당 많은 회전을 수행해야하기 때문에 비효율적입니다.

삽입/삭제가 훨씬 더 효율적이기 때문에 빨간색 트리는 아마도 더 나은 대안 일 것입니다. 이 구조는 잎으로가는 가장 긴 경로가 가장 짧은 경로의 두 배를 넘지 않도록 보장합니다. 따라서 AVL 트리보다 균형이 잘 잡히지 않지만 최악의 불균형 케이스는 피합니다.

트리가 여러 번 읽히고 만들어진 후에 변경되지 않으면 완전히 균형 잡힌 AVL 트리에 대한 추가 오버 헤드의 가치가있을 수 있습니다. 또한 빨간색 트리는 각 노드에 대해 하나의 추가 스토리지가 필요하므로 노드의 "색상"을 제공합니다.

AVL 트리의 균형을 맞추기 위해 나는 여기서 모든 사람들과 공유 할 생각을 썼습니다. 이 구현은 완벽하다고 생각합니다. 질문/질문/비판은 물론 환영합니다.

http://uploading.com/files/5883f1c7/avl_balance.cpp/

StackoverFlow의 초보자이기 때문에 여기에 코드를 게시하려고 시도했지만 형식 문제가 잘못되었습니다. 따라서 위의 링크에 파일을 업로드했습니다.

건배.

셀프 밸런싱 AVL 트리 @의 완전한 구현이 있습니다. http://code.google.com/p/self-balancing-avl-tree/ . 또한 맵/멀티 맵 컬렉션뿐만 아니라 로그 시간 연결 및 분할 작업을 구현합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top