균형 잡힌 나무의 정의

균형 잡힌 나무의 정의

---

나는 누군가가 나를 위해 균형 잡힌 트리의 정의를 명확히 해줄 수 있는지 궁금합니다. 나는 "각 하위 트리가 균형을 이루고 두 하위 트리의 높이가 최대 1만큼 다른 경우 트리가 균형을 이룹니다.

이것이 멍청한 질문이라면 사과드립니다. 그러나이 정의가 나무의 잎까지 모든 노드에 적용됩니까, 아니면 루트에서 바로 떨어진 왼쪽 및 오른쪽 하위 트리에만 적용됩니까? 이것을 프레임하는 또 다른 방법은 트리의 내부 노드가 불균형하고 전체 트리가 균형을 유지하는 것이 가능할까요?

---

제약 조건은 일반적으로 모든 하위 트리에 재귀 적으로 적용됩니다. 즉, 트리는 다음과 같은 경우에만 균형을 이룹니다.

1. 왼쪽 및 오른쪽 하위 트리의 높이가 최대 1만큼 다릅니다.
2. 왼쪽 하위 트리가 균형을 이루고 있으며
3. 올바른 하위 트리가 균형을 이룹니다.

이것에 따르면 다음 트리는 균형을 이룹니다.

     A
   /   \
  B     C  
 /     / \  
D     E   F  
     /  
    G  

다음 은 C의 하위 트리의 높이가 2만큼 다르기 때문에 균형 이 맞지 않습니다 .

     A
   /   \
  B     C   <-- difference = 2
 /     /
D     E  
     /  
    G  

즉, 첫 번째 점의 특정 제약 조건은 트리 유형에 따라 다릅니다. 위에 나열된 것은 AVL 트리 의 일반적인 것입니다 .

예를 들어, 빨강-검정 나무 는 더 부드러운 제약을 부과합니다.

---

"균형"을 정의하는 방법에는 여러 가지가 있습니다. 주요 목표는 모든 노드의 깊이를 O(log(n)).

말씀하신 균형 조건은 AVL 트리에 대한 것 같습니다 .
다음은 AVL 트리의 균형 조건에 대한 공식적인 정의입니다 .

AVL의 모든 노드에서 왼쪽 하위 트리 의 높이는 오른쪽 하위 트리의 높이 에서 최대 1 만큼 다릅니다 .

다음 질문, " 높이 "는 무엇입니까?

이진 트리에서 노드 의 " 높이 "는 해당 노드에서 리프까지 가장 긴 경로의 길이입니다.

이상하지만 일반적인 경우가 하나 있습니다.

사람들은 빈 나무의 높이를 (-1).

예를 들어 루트의 왼쪽 자식은 null다음과 같습니다.

              A  (Height = 2)
           /     \
(height =-1)       B (Height = 1) <-- Unbalanced because 1-(-1)=2 >1
                    \
                     C (Height = 0)

결정할 두 가지 예 :

예, 균형 잡힌 트리 예 :

        A (h=3)
     /     \
 B(h=1)     C (h=2)        
/          /   \
D (h=0)  E(h=0)  F (h=1)
               /
              G (h=0)

아니요, 균형 잡힌 트리가 아닙니다 .

        A (h=3)
     /     \
 B(h=0)     C (h=2)        <-- Unbalanced: 2-0 =2 > 1
           /   \
        E(h=1)  F (h=0)
        /     \
      H (h=0)   G (h=0)      

---

이 두 가지 사이에는 차이가 없습니다. 생각해보세요.

Let's take a simpler definition, "A positive number is even if it is zero or that number minus two is even." Does this say 8 is even if 6 is even? Or does this say 8 is even if 6, 4, 2, and 0 are even?

There's no difference. If it says 8 is even if 6 is even, it also says 6 is even if 4 is even. And thus it also says 4 is even if 2 is even. And thus it says 2 is even if 0 is even. So if it says 8 is even if 6 is even, it (indirectly) says 8 is even if 6, 4, 2, and 0 are even.

It's the same thing here. Any indirect sub-tree can be found by a chain of direct sub-trees. So even if it only applies directly to direct sub-trees, it still applies indirectly to all sub-trees (and thus all nodes).

---

Balanced tree is a tree whose height is of order of log(number of elements in the tree).

height = O(log(n))
O, as in asymptotic notation i.e. height should have same or lower asymptotic
growth rate than log(n)
n: number of elements in the tree

The definition given "a tree is balanced of each sub-tree is balanced and the height of the two sub-trees differ by at most one" is followed by AVL trees.

Since, AVL trees are balanced but not all balanced trees are AVL trees, balanced trees don't hold this definition and internal nodes can be unbalanced in them. However, AVL trees require all internal nodes to be balanced.

---

the aim of balanced tree is to reach the leaf in a minimum of traversal (min height). The degree of the tree is the number of branches minus 1. A Balanced tree may be not Binary.

---

1. The height of a node in a tree is the length of the longest path from that node downward to a leaf, counting both the start and end vertices of the path.
2. A node in a tree is height-balanced if the heights of its subtrees differ by no more than 1.
3. A tree is height-balanced if all of its nodes are height-balanced.

참고URL : https://stackoverflow.com/questions/8015630/definition-of-a-balanced-tree