이진 트리 (AVL)의 밸런싱

Question

좋아, 이것은 CS 멤버들에 대한 이론 영역에서 또 다른 하나입니다.

90 년대에는 BST를 구현하는 데 상당히 적합했습니다. 내 머리를 절대 쓸 수없는 유일한 방법은 이진 트리 (AVL)의 균형을 맞추는 알고리즘의 복잡성이었습니다.

혹시이 문제에 대해 도움을 주실 수 있습니까?

Answer 1

희생양 나무는 아마도 가장 간단한 균형 결정 알고리즘을 가지고 있습니다. 어떤 삽입으로 인해 새 노드가 너무 깊어지면 높이 균형보다는 무게 균형을보고 다시 균형을 이룰 노드를 찾습니다. 삭제시 재조정할지 여부에 대한 규칙도 간단합니다. 노드에 비밀 정보를 저장하지 않습니다. 알고리즘이 정확하다는 것을 입증하는 것이 더 까다 롭지 만 알고리즘을 이해하는 데 필요하지 않습니다. ...

그러나 AVL과 달리 항상 높이 균형이 맞지 않습니다. 적색 - 검정색과 마찬가지로 그 불균형은 제한되어 있지만, 적색 - 검정색과 달리 매개 변수로 조정할 수 있기 때문에 대부분의 실제적인 목적을 위해 필요에 따라 균형 잡힌 것처럼 보입니다. 나는 너무 조심스럽게 튜닝하면 최악의 경우 삽입을 위해 AVL보다 나쁘거나 나 빠진다는 생각이 듭니다.

응답 내가 AVL 나무를 이해하고 내 개인적인 경로를 제공하겠습니다 편집

에 의문을 제기합니다.

먼저 트리 회전이 무엇인지 이해해야하므로, AVL 알고리즘을 들어 본 모든 것을 무시하고 이해해야합니다. 오른쪽 회전과 왼쪽 회전 인 머리를 똑바로 세우고, 각각이 나무에 무엇을하는지, 아니면 정확한 방법에 대한 설명만으로 당신을 혼란에 빠뜨릴 것입니다.

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

다음으로 노드를 추가하거나 제거한 경우 트리의 균형을 조정했을 수 있습니다. 그러나 추가하거나 제거한 노드의 조상 인 노드의 균형을 변경했을뿐입니다. 그래서, 당신이해야 할 일은 트리를 다시 올리는 작업을하는 것입니다. 회전을 사용하여 발견 된 불균형 노드의 균형을 유지하고 균형점을 업데이트하면 트리가 다시 균형을 이룰 때까지 계속됩니다.

이해의 마지막 부분은 발견 한 각 노드의 균형을 조정하는 데 사용 된 특정 회전을 알맞은 참조로 찾는 것입니다.이 개념은 높은 개념과 반대되는 개념입니다. AVL 트리 코드를 수정하는 동안 또는 데이터 구조 시험 중에 세부 사항 만 기억하면됩니다. 디버거에서 AVL 트리 코드를 열어 본지 몇 년이 지났습니다. 구현은 일을하고 일을 계속하는 경향이 있습니다. 그래서 나는 정말로 기억하지 않는다. 몇 가지 포커 칩을 사용하여 테이블에서 일종의 작업을 수행 할 수 있지만 모든 케이스가 실제로 있는지를 확인하는 것은 어렵습니다 (많지 않음). 그것을 찾는데 최고입니다.

그런 다음 모든 것을 코드로 번역해야합니다.

코드 목록을 보는 것이 마지막 단계를 제외한 모든 단계에서 도움이된다고 생각하지 않으므로 무시하십시오. 코드가 명확하게 작성된 최상의 경우에도, 다이어그램없이 프로세스의 텍스트 설명으로 보입니다. 보다 전형적인 경우에는 C 구조체 조작의 혼란입니다. 책에 충실하십시오.

Answer 2

노드 밸런싱 알고리즘을위한 코드를 게시하는 것이 좋지 않을 것 같습니다. 그러나 red-black trees에 대한 Wikipedia 기사에는 알고리즘의 완전한 C 구현이 포함되어 있으며 AVL trees의 기사에는 고품질 구현에 대한 여러 링크가 있습니다.

이러한 두 가지 구현은 대부분의 범용 시나리오에 충분합니다.

Answer 3

전체 프로그램이 적절하지 않다고 동의합니다.

클래식 AVL 및 RB 트리는 결정 론적 접근법을 사용하지만 균형을 유지하고 키의 통계 분포에 관계없이 균형을 유지하는 데 비용이 덜 드는 "Randomized binary search trees"을 살펴볼 것을 제안합니다.

Answer 4

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

삽입/삭제가 훨씬 효율적이기 때문에 Red-Black 트리가 더 나은 대안 일 수 있습니다. 이 구조는 리프에 대한 최장 경로가 최단 경로의 두 배를 넘지 않는다는 것을 보장합니다. 따라서 AVL 트리보다 균형이 잘 잡히지 않으면 서 최악의 불균형을 피할 수 있습니다.

나무가 여러 번 읽히고 만들어지면 변경되지 않으므로 균형 잡힌 AVL 트리의 추가 오버 헤드가 가치가 있습니다. 또한 Red-Black 트리는 노드의 "색상"을 제공하는 각 노드에 대해 추가로 1 비트의 저장소를 필요로합니다.

Answer 5

저는 최근에 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 
    } 
} 

Answer 6

AVL 트리 균형 조정을 위해 방금 여기에 모든 사람들과 공유하는 기능을 썼습니다. 이 구현은 완벽하다고 생각합니다./질문/비판 쿼리는 물론 환영의 위치 :

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

, 나는 여기에 내 코드를 게시 시도 유래에 초보자이기하지만 나쁜 서식 문제와 함께 붙어 있었다. 그래서 위의 링크에 파일을 업로드했습니다.

건배.

Answer 7

자체 균형 조정 avl 트리 @http://code.google.com/p/self-balancing-avl-tree/의 구현이 있습니다. 또한 로그 시간 연결 및 분할 작업과 맵/멀티 맵 콜렉션을 구현합니다.