AVL 회전에 대한 균형 계수/노드 높이 이해

Question

AVL 트리의 균형을 잡는 방법을 이해하는 데 어려움을 겪고 있습니다. 예를 들어, 나는 회전 물건을 이해하지만, 나는 노드 높이의 균형 계수를 찾는 방법을 알아낼 수 없습니다 :

http://i.imgur.com/yh5zNIl.png

사람이 우리가 실제로 각 노드에 대한 균형 계수를 찾는 방법 나에게 설명 할 수 ?

[왼쪽 하위 트리] - (오른쪽 하위 트리)]의 높이가 (-1 < = x < = 1) 그 불균형을 벗어났다는 것을 안다.하지만 " 엑스".

(편집 : 코드가 필요하지 않습니다. BF를 찾는 방법을 알고 싶습니다.)

Answer 1

질문을 올바르게 이해하면 주어진 노드의 밸런스 요소를 유지하는 방법을 알고 싶습니다. 트랙을 유지하는 가장 좋은 방법은 트리에서 "삽입"을 수행하는 것입니다. 새 노드가 "현재"노드의 왼쪽 또는 오른쪽으로 이동하는지 여부를 알기 때문입니다. 왼쪽으로 갈 때 균형을 감소시키고 오른쪽으로 갈 때 균형을 증가시킵니다. 아이디어는 "삽입"방법을 종료하기 전에 트리를 이미 균형있게 유지하는 것입니다.

내가 본 다른 접근법은 "삽입"중에 균형 조정을 수행하지 않는 것입니다. BST 에서처럼 삽입하면됩니다. 삽입 후에는 각 노드에서 왼쪽 하위 트리와 오른쪽 하위 트리 높이를 얻고 포인터를 다시 시작하는 균형 조정 작업을 시작합니다. 이것은 높이를 찾는 모든 노드에 대해 O (logn)를 발생시키고 모든 노드에 대해이를 수행하므로 n * O (logn)가되므로 좋은 접근 방법은 아닙니다.

나는 삽입 할 때마다 나무 균형을 유지하고 삽입하는 동안 별도로 높이를 계산하지 않는 "삽입"방법을 게시하고 있습니다. 도움이되는지보기 :

Node* 
AVL::insert(Node* node, int key, int value) 
{ 
    if(node == NULL) 
     node = new Node(key, value); 

    else if (key <= node->key) 
    { 
     node->balance--; 
     node->left = insert(node->left, key, value); 
    } 

    else if (key > node->key) 
    { 
     node->balance++; 
     node->right = insert(node->right, key, value); 
    } 

    // Right Tree Heavy 
    if (node->balance == 2) 
    { 
     // Left tree unbalanced 
     if (node->right && node->right->balance == 1) 
     { 
      // LL 
      node = singleLeftRotation(node); 
      node->balance = 0; 
      node->left->balance = 0; 
     } 
     if (node->right && node->right->balance == -1) 
     { 
      // LR 
      int nodeRLBalance = node->right->left->balance; 
      node = doubleLeftRotation(node); 
      node->balance = 0; 
      node->left->balance = nodeRLBalance == 1 ? -1 : 0; 
      node->right->balance = nodeRLBalance == -1 ? 1 : 0; 
     } 
    } 

    // Left Tree Heavy 
    if (node->balance == -2) 
    { 
     // Right tree unbalanced 
     if (node->left && node->left->balance == -1) 
     { 
      // RR 
      node = singleRightRotation(node); 
      node->balance = 0; 
      node->right->balance = 0; 
     } 
     if (node->left && node->left->balance == 1) 
     { 
      // RL 
      int nodeLRBalance = node->left->right->balance; 
      node = doubleRightRotation(node); 
      node->balance = 0; 
      node->left->balance = nodeLRBalance == 1 ? -1 : 0; 
      node->right->balance = nodeLRBalance == -1 ? 1 : 0; 
     } 
    } 

    return node; 
} 

Answer 2

노드의 균형 요소는 왼쪽 및 오른쪽 자손 노드의 높이의 차이입니다. 밸런스 = node.right.height - node.left.height - node.right.height

및 기타 등으로 밸런스 = node.left.height :

밸런스 계수 등의 일부에 의해 정의된다

그래프에서 일부 노드의 균형을 이해하려면 균형 요소를 정의하는 방법을 알아야합니다. 예를 들어, 위키 피 디아를 들어

는 node.left.height으로 정의 - node.right.height 당신은 수식 결과는 노드 균형 나는 균형 요소를 찾는 방법을 알고 싶어 Avl Tree Balance of Nodes Example