이진 검색 트리의 높이를 계산하는 가장 좋은 방법은 무엇입니까? (AVL-Tree 균형)
https://stackoverflow.com/questions/575772
-
05-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
노드 균형을 계산하는 가장 좋은 방법을 찾고 있습니다. AVL-Tree. 나는 그것이 작동한다고 생각했지만, 무거운 삽입/업데이트 후에는 그것이 올바르게 작동하지 않는다는 것을 알 수 있습니다.
이것은 일종의 두 부분 질문입니다. 첫 번째 부분은 하위 트리의 높이를 계산하는 방법입니다. 정의를 알고 있습니다. "노드의 높이는 해당 노드에서 잎까지 가장 긴 하향 경로의 길이입니다." 그리고 나는 그것을 이해하지만 그것을 구현하는 데 실패합니다. 그리고 더 혼란스럽게하려면이 인용문은 Wikipedia에서 나무-높이에서 찾을 수 있습니다. "일반적으로 -1 값은 노드가없는 하위 트리에 해당하는 반면 0은 하나의 노드가있는 하위 트리에 해당합니다."
그리고 두 번째 부분은 AVL 트리에서 하위 트리의 균형 계수를 얻는 것입니다. 개념을 이해하는 데 아무런 문제가 없습니다. "당신의 높이를 얻으십시오 L 그리고 R 서브 트리 및 빼기 R ~에서 L". 그리고 이것은 다음과 같은 것으로 정의됩니다. BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]
Wikipedia에 대한 읽기는 AVL 트리에 삽입을 설명하는 첫 몇 줄에 이것을 말합니다. "균형 계수가 -1, 0 또는 1이되면 트리는 여전히 AVL 형태이며 회전이 필요하지 않습니다."
그런 다음 계속해서 말합니다 "밸런스 계수가 2 또는 -2가되면이 노드에 뿌리를 둔 트리는 불균형이며 트리 회전이 필요합니다. 트리의 균형을 맞추기 위해 최대 단일 또는 이중 회전이 필요합니다." - 이해하는 데 어려움이 없습니다.
그러나 (예, 항상 있지만).
여기서 혼란스러워하는 곳이 있습니다. "r의 균형 계수가 1이라면, 해당 노드의 (외부) 오른쪽에서 삽입이 발생하고 왼쪽 회전이 필요하다는 것을 의미합니다.". 그러나 M에서 텍스트를 이해하면 (내가 인용 한대로) 균형 요소가 내면에있는 경우 [-1, 1] 그렇다면 균형이 필요하지 않았습니까?
나는 개념을 파악하는 데 너무 가깝다고 생각하고, 나무 회전을 내려 놓고, 일반적인 이진 검색 트리를 구현했으며, AVL 트리를 잡는 위기에 있었지만 그 필수 주현절을 놓치고있는 것 같습니다.
편집하다: 코드 예제는 항상 코드로 무언가를 파악하는 데 더 쉬운 시간을 보냈기 때문에 학업 공식보다 선호되지만 도움이 크게 높아집니다.
편집하다: 나는 모든 대답을 "받아 들여진"것으로 표시 할 수 있기를 바랍니다. 그러나 나에게 Nick의 대답은 처음으로 "아하"로 만들었습니다.
해결책
1 부 - 높이
Starblue가 말했듯이 높이는 재귀 적입니다. 의사 코드에서 :
height(node) = max(height(node.L), height(node.R)) + 1
이제 높이는 두 가지 방식으로 정의 될 수 있습니다. 루트에서 해당 노드로 경로의 노드 수일 수도 있고 링크 수일 수도 있습니다. 에 따르면 참조 한 페이지, 가장 일반적인 정의는 링크 수입니다. 이 경우 전체 의사 코드는 다음과 같습니다.
height(node):
if node == null:
return -1
else:
return max(height(node.L), height(node.R)) + 1
노드 수를 원한다면 코드는 다음과 같습니다.
height(node):
if node == null:
return 0
else:
return max(height(node.L), height(node.R)) + 1
어느 쪽이든, 재조정 알고리즘은 동일하게 작동해야한다고 생각합니다.
그러나 나무가 훨씬 더 효율적입니다 (O (ln (n))) 트리에 높이 정보를 저장하고 업데이트하는 경우 매번 계산하지 않고. (에))
2 부 - 밸런싱
"R의 균형 계수가 1 인 경우", 상단의 균형 계수가 2 일 때 오른쪽 분기의 균형 계수에 대해 이야기하고 있습니다. 단일 회전을 수행할지 여부를 선택하는 방법을 알려줍니다. 이중 회전. (Python Like) 의사 코드에서 :
if balance factor(top) = 2: // right is imbalanced
if balance factor(R) = 1: //
do a left rotation
else if balance factor(R) = -1:
do a double rotation
else: // must be -2, left is imbalanced
if balance factor(L) = 1: //
do a left rotation
else if balance factor(L) = -1:
do a double rotation
나는 이것이 의미가 있기를 바랍니다
다른 팁
높이는 재귀에 의해 쉽게 구현되며, 하위 트리의 높이와 하나의 최대 값을 가져갑니다.
"R의 균형 계수"는 균형이 맞지 않는 나무의 오른쪽 하위 트리를 나타냅니다.
즉석에서 나무 깊이를 계산할 필요가 없습니다.
작업을 수행 할 때 유지할 수 있습니다.
또한 실제로는 실제로 깊이 추적을 유지할 필요가 없습니다. 왼쪽과 오른쪽 나무 깊이의 차이를 추적 할 수 있습니다.
http://www.eternallyconfuzzled.com/tuts/datrastructures/jsw_tut_avl.aspx
균형 계수 (왼쪽과 오른쪽 서브 트리의 차이)를 추적하는 것만으로는 프로그래밍 POV에서 더 쉽게 발견됩니다. 회전 후 밸런스 계수를 분류하는 것을 제외하고는 ...
높이를 찾는 대체 방법은 다음과 같습니다. 높이라는 노드에 추가 속성을 추가하십시오.
class Node
{
data value; //data is a custom data type
node right;
node left;
int height;
}
이제 우리는 트리의 간단한 폭을 향한 순간을 수행하고 각 노드의 높이 값을 계속 업데이트합니다.
int height (Node root)
{
Queue<Node> q = Queue<Node>();
Node lastnode;
//reset height
root.height = 0;
q.Enqueue(root);
while(q.Count > 0)
{
lastnode = q.Dequeue();
if (lastnode.left != null){
lastnode.left.height = lastnode.height + 1;
q.Enqueue(lastnode.left);
}
if (lastnode.right != null){
lastnode.right.height = lastnode.height + 1;
q.Enqueue(lastnode.right);
}
}
return lastnode.height; //this will return a 0-based height, so just a root has a height of 0
}
건배,
글쎄, 당신은 다음과 같은 재귀 함수로 트리의 높이를 계산할 수 있습니다.
int height(struct tree *t) {
if (t == NULL)
return 0;
else
return max(height(t->left), height(t->right)) + 1;
}
적절한 정의와 함께 max() 그리고 struct tree. 시간을내어 왜 이것이 인용하는 경로 길이를 기반으로 정의에 해당하는지 알아 내야합니다. 이 함수는 빈 나무의 높이로 0을 사용합니다.
그러나 AVL 트리와 같은 경우, 필요할 때마다 실제로 높이를 계산한다고 생각하지 않습니다. 대신, 각 트리 노드는 해당 노드에 뿌리를 둔 하위 트리의 높이를 기억하는 추가 필드로 보강됩니다. 이 필드는 트리가 삽입 및 삭제에 의해 수정되므로 최신 상태로 유지해야합니다.
위에서 제안한 것처럼 나무 안에 캐싱하는 대신 매번 높이를 계산하면 AVL 트리 모양이 정확하지만 예상되는 로그 성능은 없습니다.
여기서 혼란스러워하는 곳이 있습니다. 텍스트는 "r의 균형 계수가 1이면 해당 노드의 (외부) 오른쪽에 삽입이 발생하고 왼쪽 회전이 필요하다는 것을 의미합니다." 그러나 텍스트를 이해하면서 (내가 인용 한 바와 같이) 잔액 계수가 [-1, 1] 내에 있다면 균형을 잡을 필요가 없다고 말했습니다.
R 현재 노드의 오른쪽 자식입니다 N.
만약에 balance(N) = +2, 당신은 일종의 회전이 필요합니다. 그러나 사용할 회전은 무엇입니까? 글쎄, 그것은 달라집니다 balance(R): 만약에 balance(R) = +1 그런 다음 왼쪽 회전이 필요합니다 N; 그러나 만약 balance(R) = -1 그러면 어떤 종류의 이중 회전이 필요합니다.
여기서 혼란스러워하는 곳이 있습니다. 텍스트는 "r의 균형 계수가 1이면 해당 노드의 (외부) 오른쪽에 삽입이 발생하고 왼쪽 회전이 필요하다는 것을 의미합니다." 그러나 텍스트를 이해하면서 (내가 인용 한 바와 같이) 잔액 계수가 [-1, 1] 내에 있다면 균형을 잡을 필요가 없다고 말했습니다.
좋아요, 주현절 시간.
회전이 무엇을하는지 고려하십시오. 왼쪽 회전에 대해 생각해 봅시다.
P = parent
O = ourself (the element we're rotating)
RC = right child
LC = left child (of the right child, not of ourself)
P
\
O
\
RC
/
LC
P
\
RC
/
O
\
LC
10
\
15
\
20
/
18
10
\
20
/
15
\
18
basically, what happens is;
1. our right child moves into our position
2. we become the left child of our right child
3. our right child's left child becomes our right
이제 여기서 알아야 할 큰 것 -이 왼쪽 회전은 나무의 깊이가 바뀌지 않았습니다. 우리는 더 이상 균형을 잡지 못했습니다.
그러나 - 그리고 여기 AVL의 마법이 있습니다 - 우리가 올바른 아이를 먼저 올바른 아이를 회전 시켰다면, 우리가 가진 것은 이것입니다 ...
P
\
O
\
LC
\
RC
그리고 이제 우리가 o 왼쪽으로 회전한다면, 우리가 얻는 것은 이것입니다 ...
P
\
LC
/ \
O RC
마법! 우리는 나무의 수준을 제거 할 수있었습니다. 우리는 나무 균형을 만들었습니다.
나무의 균형을 유지한다는 것은 과도한 깊이를 제거하고 상위 레벨을 더 완전히 포장하는 것을 의미합니다. 이것은 우리가 방금 한 일입니다.
단일/이중 회전에 관한 모든 것들이 단순히 하위 트리를 이렇게보아야한다는 것입니다.
P
\
O
\
LC
\
RC
회전하기 전에 - 해당 상태로 들어가기 위해 오른쪽 회전을해야 할 수도 있습니다. 그러나 이미 해당 상태에 있다면 왼쪽 회전 만 수행하면됩니다.
주다 BinaryTree<T, Comparator>::Node ㅏ subtreeHeight 데이터 멤버, 생성자에서 0으로 초기화하고 다음과 같이 매번 자동으로 업데이트됩니다.
template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::Node::setLeft (std::shared_ptr<Node>& node) {
const std::size_t formerLeftSubtreeSize = left ? left->subtreeSize : 0;
left = node;
if (node) {
node->parent = this->shared_from_this();
subtreeSize++;
node->depthFromRoot = depthFromRoot + 1;
const std::size_t h = node->subtreeHeight;
if (right)
subtreeHeight = std::max (right->subtreeHeight, h) + 1;
else
subtreeHeight = h + 1;
}
else {
subtreeSize -= formerLeftSubtreeSize;
subtreeHeight = right ? right->subtreeHeight + 1 : 0;
}
}
template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::Node::setRight (std::shared_ptr<Node>& node) {
const std::size_t formerRightSubtreeSize = right ? right->subtreeSize : 0;
right = node;
if (node) {
node->parent = this->shared_from_this();
subtreeSize++;
node->depthFromRoot = depthFromRoot + 1;
const std::size_t h = node->subtreeHeight;
if (left)
subtreeHeight = std::max (left->subtreeHeight, h) + 1;
else
subtreeHeight = h + 1;
}
else {
subtreeSize -= formerRightSubtreeSize;
subtreeHeight = left ? left->subtreeHeight + 1 : 0;
}
}
데이터 구성원에 유의하십시오 subtreeSize 그리고 depthFromRoot 또한 업데이트됩니다. 이러한 기능은 노드를 삽입 할 때 (모든 테스트), 예를 들어 호출됩니다.
template <typename T, typename Comparator>
inline std::shared_ptr<typename BinaryTree<T, Comparator>::Node>
BinaryTree<T, Comparator>::Node::insert (BinaryTree& tree, const T& t, std::shared_ptr<Node>& node) {
if (!node) {
std::shared_ptr<Node> newNode = std::make_shared<Node>(tree, t);
node = newNode;
return newNode;
}
if (getComparator()(t, node->value)) {
std::shared_ptr<Node> newLeft = insert(tree, t, node->left);
node->setLeft(newLeft);
}
else {
std::shared_ptr<Node> newRight = insert(tree, t, node->right);
node->setRight(newRight);
}
return node;
}
노드를 제거하는 경우 다른 버전을 사용하십시오. removeLeft 그리고 removeRight 교체하여 subtreeSize++; ~와 함께 subtreeSize--;. 알고리즘 rotateLeft 그리고 rotateRight 많은 문제없이 조정할 수 있습니다. 다음을 테스트하고 통과했습니다.
template <typename T, typename Comparator>
void BinaryTree<T, Comparator>::rotateLeft (std::shared_ptr<Node>& node) { // The root of the rotation is 'node', and its right child is the pivot of the rotation. The pivot will rotate counter-clockwise and become the new parent of 'node'.
std::shared_ptr<Node> pivot = node->right;
pivot->subtreeSize = node->subtreeSize;
pivot->depthFromRoot--;
node->subtreeSize--; // Since 'pivot' will no longer be in the subtree rooted at 'node'.
const std::size_t a = pivot->left ? pivot->left->subtreeHeight + 1 : 0; // Need to establish node->heightOfSubtree before pivot->heightOfSubtree is established, since pivot->heightOfSubtree depends on it.
node->subtreeHeight = node->left ? std::max(a, node->left->subtreeHeight + 1) : std::max<std::size_t>(a,1);
if (pivot->right) {
node->subtreeSize -= pivot->right->subtreeSize; // The subtree rooted at 'node' loses the subtree rooted at pivot->right.
pivot->subtreeHeight = std::max (pivot->right->subtreeHeight, node->subtreeHeight) + 1;
}
else
pivot->subtreeHeight = node->subtreeHeight + 1;
node->depthFromRoot++;
decreaseDepthFromRoot(pivot->right); // Recursive call for the entire subtree rooted at pivot->right.
increaseDepthFromRoot(node->left); // Recursive call for the entire subtree rooted at node->left.
pivot->parent = node->parent;
if (pivot->parent) { // pivot's new parent will be its former grandparent, which is not nullptr, so the grandparent must be updated with a new left or right child (depending on whether 'node' was its left or right child).
if (pivot->parent->left == node)
pivot->parent->left = pivot;
else
pivot->parent->right = pivot;
}
node->setRightSimple(pivot->left); // Since pivot->left->value is less than pivot->value but greater than node->value. We use the NoSizeAdjustment version because the 'subtreeSize' values of 'node' and 'pivot' are correct already.
pivot->setLeftSimple(node);
if (node == root) {
root = pivot;
root->parent = nullptr;
}
}
어디
inline void decreaseDepthFromRoot (std::shared_ptr<Node>& node) {adjustDepthFromRoot(node, -1);}
inline void increaseDepthFromRoot (std::shared_ptr<Node>& node) {adjustDepthFromRoot(node, 1);}
template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::adjustDepthFromRoot (std::shared_ptr<Node>& node, int adjustment) {
if (!node)
return;
node->depthFromRoot += adjustment;
adjustDepthFromRoot (node->left, adjustment);
adjustDepthFromRoot (node->right, adjustment);
}
전체 코드는 다음과 같습니다. http://ideone.com/d6arrv
이 BFS와 같은 솔루션은 매우 간단합니다. 단순히 레벨을 하나씩 점프합니다.
def getHeight(self,root, method='links'):
c_node = root
cur_lvl_nodes = [root]
nxt_lvl_nodes = []
height = {'links': -1, 'nodes': 0}[method]
while(cur_lvl_nodes or nxt_lvl_nodes):
for c_node in cur_lvl_nodes:
for n_node in filter(lambda x: x is not None, [c_node.left, c_node.right]):
nxt_lvl_nodes.append(n_node)
cur_lvl_nodes = nxt_lvl_nodes
nxt_lvl_nodes = []
height += 1
return height
