이진 트리 로테이션

Question

AVL 검색 트리를 구현 중입니다. 지금까지 코딩 부분을 마쳤으며 버그를 테스트하기 시작했습니다. 내 노드 회전 방법이 도청 된 것을 알았고 신에게있어 나는 그 문제가 무엇인지 이해할 수 없다.

알고리즘은 종이에서와 같이 작동하지만 컴퓨터에서 실행될 때 트리 노드가 누출됩니다.

이

은 왼쪽에 노드를 회전하는 데 사용 방법 : 부분 균형 나는 AVL 댓글을 달았 내 삽입 방법에 http://pastebin.com/mPHj29Af

bool avl_search_tree::avl_tree_node::rotate_left() 
{ 
    if (_right_child != NULL) { 
        avl_tree_node *new_root = _right_child; 
  
        if (_parent != NULL) { 
            if (_parent->_left_child == this) { 
                _parent->_left_child = new_root; 
            } else { 
                _parent->_right_child = new_root; 
            } 
        } 
  
        new_root->_parent = _parent; 
        _parent = new_root; 
  
        _right_child = new_root->_left_child; 
        new_root->_left_child = this; 
  
        if (_right_child != NULL) { 
            _right_child->_parent = this; 
        } 
  
        //update heights 
        update_height(); 
        new_root->update_height(); 
  
        return true; 
    } 
  
    return false; 
} 

대신 난 그냥에 새로 삽입 된 노드를 회전하기 위해 노력하고있어 왼쪽. 오름차순으로 정수를 삽입 한 결과 : 내 트리에는 초기 루트 (삽입 된 첫 번째 노드) 만 포함되고 다른 모든 노드는 유출됩니다.

내가 미쳐 가기 시작하면 문제를 식별하는 데 큰 도움이됩니다.

레코드의 경우 : 회전을 사용하지 않으면 트리가 노드를 누설하지 않으며 정상적인 불균형 이진 검색 트리 (삽입 및 조회 용)로 작동합니다.

편집 : AJG85의 의견에 내가 관찰 추가 할 것입니다 인해 : (내 경우 32 비트 정수에) 내가 키 값을 인쇄합니다 avl_search_tree :: avl_tree_node의 소멸자 방법의 printf '확인'을 추가

을 정리하기 전에, 방금 삽입 한 키를 인쇄 할 avl_search_tree의 삽입 메소드에.

그런 다음 프로그램의 진입 점에서 힙에 avl_search_tree를 할당하고 키를 오름차순으로 추가 한 다음 삭제합니다. 삽입에 성공했다하지만 루트가 삭제 된 thatall 의미

bool avl_search_tree::insert(const int&) : 1 
bool avl_search_tree::insert(const int&) : 2 
bool avl_search_tree::insert(const int&) : 3 
bool avl_search_tree::insert(const int&) : 4 
bool avl_search_tree::insert(const int&) : 5 
bool avl_search_tree::insert(const int&) : 6 
bool avl_search_tree::insert(const int&) : 7 
bool avl_search_tree::insert(const int&) : 8 
avl_search_tree::avl_tree_node::~avl_tree_node() : 1 

: AVL 균형으로

내가 터미널에서 다음과 같은 출력을 얻을 수 있었다.

AVL 밸런싱은 일반적인 이진 검색 트리처럼 작동합니다. 터미널 출력은 다음과 같습니다.

bool avl_search_tree::insert(const int&) : 1 
bool avl_search_tree::insert(const int&) : 2 
bool avl_search_tree::insert(const int&) : 3 
bool avl_search_tree::insert(const int&) : 4 
bool avl_search_tree::insert(const int&) : 5 
bool avl_search_tree::insert(const int&) : 6 
bool avl_search_tree::insert(const int&) : 7 
bool avl_search_tree::insert(const int&) : 8 
avl_search_tree::avl_tree_node::~avl_tree_node() : 1 
avl_search_tree::avl_tree_node::~avl_tree_node() : 2 
avl_search_tree::avl_tree_node::~avl_tree_node() : 3 
avl_search_tree::avl_tree_node::~avl_tree_node() : 4 
avl_search_tree::avl_tree_node::~avl_tree_node() : 5 
avl_search_tree::avl_tree_node::~avl_tree_node() : 6 
avl_search_tree::avl_tree_node::~avl_tree_node() : 7 
avl_search_tree::avl_tree_node::~avl_tree_node() : 8 

이는 모든 것이 올바르게 정리되었음을 의미합니다.

이제 순환 방법이 문제라는 결론에 어떻게 도달 했습니까? 주석 처리 된 AVL 밸런싱 서브 루틴 아래에서 새로 추가 된 모든 노드를 왼쪽으로 회전시키는 선을 추가했습니다. 결과? AVL Balancing 서브 루틴이 활성화 된 경우와 같습니다.

그리고 update_height() 메서드에 관해서는 어떤 식 으로든 트리 구조를 변경하지 않습니다.

이 내용이 명확 해지기를 바랍니다.

편집 2 :

좀 더 일을 명확히하려면, 자신은 avl_tree_node 소멸자가 구현되는 방법입니다

avl_search_tree::avl_tree_node::~avl_tree_node() 
{ 
    printf("%s : %d\n", __PRETTY_FUNCTION__, *_key); 

    if (_left_child != NULL) { 
     delete _left_child; 
    } 

    if (_right_child != NULL) { 
     delete _right_child; 
    } 

    if (_key != NULL) { 
     delete _key; 
    } 
} 

_left_child 및 _right_child는 힙에 할당 된 개체를 avl_tree_node에 대한 포인터입니다.

편집 3 : AGJ85의 2 코멘트에

덕분에 나는이 문제를 발견했다. 내 rotate 메소드에서는 루트가 옮겨 질 때마다 트리의 루트 포인터를 새로운 루트에 실제로 업데이트해야한다는 것을 잊어 버렸습니다.

기본적으로 트리의 루트는 항상 첫 번째 삽입 된 노드를 가리키고 필요할 때 포인터를 업데이트하지 않고 실제로 회전 구성된 새 트리의 루트를 누설시킵니다. :)

감사합니다. AGJ85!

Answer 1

AGJ85의 두 번째 의견 덕분에 문제가 발견되었습니다. 내 rotate 메소드에서는 루트가 옮겨 질 때마다 트리의 루트 포인터를 새로운 루트에 실제로 업데이트해야한다는 것을 잊어 버렸습니다.

기본적으로 트리의 루트는 항상 첫 번째 삽입 된 노드를 가리키고 필요할 때 포인터를 업데이트하지 않고 실제로 회전 구성된 새 트리의 루트를 누설시킵니다. :)

Answer 2

EDIT - 젠장 - 문제가 이미 해결 된 것을 본 적이 없습니다 (질문에서 답). 그럼에도 불구하고이 가치가있는 구제책에 대한 답변이없는 도움말이있을 수 있습니다.

내가 철저하게 확인하지 않은,하지만 난 당신이이 줄에서 잘못되어 가고 있다고 생각 ...

_right_child = new_root->_left_child; 

하고 문제가 이미 라인에 new_root->_left_child을 덮어 쓸 수도 있다는 것을

... 난 당신이, 시작시, 같은 지역 정의의 블록이있다해야 어떻게 생각

_parent->_left_child = new_root; 

...

avl_tree_node *orig_parent  = _parent; 
avl_tree_node *orig_this  = this; 
avl_tree_node *orig_left_child = _left_child; 
avl_tree_node *orig_right_child = _right_child; 

그런 다음 나중에 할당 할 소스로 orig_ 로컬 변수를 사용하십시오. 이렇게하면 회전 중에 다양한 포인터를 통한 데이터 흐름에 대해 걱정할 필요가 없습니다. 옵티마이 저는 이에 대해 걱정할 가치가있는 중복 작업을 제거해야하며, 어쨌든 그다지 중요하지 않습니다.

추가 점을 몇 ...

첫째, C++ (그리고 C) 주요 밑줄 표준 예비 식별자, 두 번 밑줄. 표준 및 컴파일러가 제공하는 라이브러리를 사용하면 놀랄만 한 상호 작용을 얻을 수 있다고 주장합니다. 그렇다고해서 회원 식별자에 매크로 관련성이 있어야합니다. 후행 밑줄은 괜찮습니다 - 나는 그들을 포함 경비원에 사용하는 경향이 있습니다.

구성원 변수의 일반적인 규칙은 m 또는 m_ 인자를 추가하는 것입니다. 아마 더 일반적인, 아마, 어떤 특별한 접두사 또는 접미사도 전혀 가지지 않고있다.

둘째, 부모 링크가 노드에 저장되어 있지 않은 AVL 트리를 구현하는 것이 더 쉬울 수도 있고 그렇지 않을 수도 있습니다. 아직 AVL 트리를 구현하지는 못했지만 적 블랙 트리를 한 번 구현했습니다. 많은 알고리즘이 재귀 검색을 첫 단계로 포함해야합니다. 발견 된 노드를 기억하고 해당 노드까지의 경로를 삭제하는 표준 검색 만 수행 할 수는 없습니다. 그러나 재귀 구현이 너무 나쁘지 않고 저글링에 대한 지침이 적습니다.

마지막으로, 일반적인 알고리즘 -이 알고리즘을 "건조 실행"하려고하면 엄격히 작업을 단계별로 수행하고 관련 정보 소스를 모두 확인하십시오. 이미 이걸 수정 했니?). 스피드에 대한 세부 사항 중 일부를 건너 뛰는 습관을 가지기가 매우 쉽습니다. 유용한 기계 보조 드라이 런은 디버거에서 코드를 단계별로 실행하고 모든 단계의 결과가 용지 드라이 런과 일치하는지 확인하는 것입니다.

EDIT - 한 가지 더 알려주세요.이 문구는이 문맥에서 잘 모르기 때문에이 글을 끝내지 않을 것입니다. 나는 대개 간단한 구조체를 사용하여 데이터 구조 노드를 구현합니다. 데이터 숨김이 없으며 멤버 함수가 거의 없습니다. 대부분의 코드는 데이터 구조와 별도로 유지되며 종종 "도구"클래스로 유지됩니다. 나는 이것이 오래된 "부서진 모양"을 깨뜨리는 것을 압니다. OOP 원칙이지만, IMO는 실제로 더 잘 작동합니다.

Answer 3

코드에서 찾고 있던 버그를 발견했습니다. (당신이 말한 것처럼, 루트가 바뀌면 트리 루트 포인터를 새로운 루트로 업데이트하지 않았습니다. 이것은 목록 및 트리 삽입/삭제 메소드의 일반적인 패러다임으로, 트리의 루트 또는 루트의 헤드를 가리키는 포인터를 반환합니다. if 당신은 패러다임이 다시 실수를하지 않을 것을 기억하십시오.)보기의 더 높은 수준에서

, 내가 대신에 유사한 성능을 가진 AA Tree, 사용하는 것입니다 AVL Tree 또는 Red-Black Tree 코드 문제를 방지하기 위해 사용했던 기술 O (n) 공간 및 O (log n) 시간을 사용하여 삽입, 삭제 및 검색합니다. 그러나 AA 트리는 코드 작성이 훨씬 간단합니다.