이진 검색 트리에서 높이를 계산하는 가장 좋은 방법은 무엇입니까? (AVL 트리 균형 조정)
AVL-tree 에서 노드 균형을 계산하는 가장 좋은 방법을 찾고 있습니다. 나는 그것이 작동한다고 생각했지만 무거운 삽입 / 업데이트 후에 제대로 작동하지 않는 것을 알 수 있습니다 (전혀).
이것은 두 부분으로 구성된 질문입니다. 첫 번째 부분은 하위 트리의 높이를 계산하는 방법입니다. "노드의 높이는 해당 노드에서 리프까지 가장 긴 하향 경로의 길이입니다. . " 이해하지만 구현하지 못합니다. 그리고 나를 더 혼란스럽게하기 위해이 인용문은 위키피디아의 tree-heights에서 찾을 수 있습니다. "일반적으로 값 -1은 노드가없는 하위 트리에 해당하는 반면 0은 노드가 하나 인 하위 트리에 해당합니다."
그리고 두 번째 부분은 AVL 트리에서 하위 트리의 균형 요인을 받고, 나는 개념을 이해 아무 문제 없어 한 "당신의 높이를 얻을 수 L및 R하위 나무와 빼기 R에서를 L" . 그리고 이것은 다음과 같이 정의됩니다.BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]
위키 백과에서 읽기는 AVL 트리에 삽입을 설명하는 처음 몇 줄에 다음과 같이 말합니다. "균형 계수가 -1, 0 또는 1이되면 트리는 여전히 AVL 형식이며 회전이 필요하지 않습니다."
그런 다음 "균형 계수가 2 또는 -2가되면이 노드에 뿌리를 둔 트리의 균형이 맞지 않으며 트리 회전이 필요합니다. 트리의 균형을 맞추려면 최대 단일 또는 이중 회전이 필요합니다."라고 말합니다. -이해하는데 문제가 없습니다.
그러나 (예, 항상 but이 있습니다).
여기에서 혼란 스러울 때 텍스트는 "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)) ). ( O (n) )
2 부-균형 조정
"R의 균형 계수가 1이면"이라고하면 오른쪽 가지의 균형 계수를 말하는 것입니다. 맨 위의 균형 계수가 2이면 단일 회전을할지, 아니면 회전 할지를 선택하는 방법을 알려줍니다. 이중 회전. (파이썬과 같은) 의사 코드에서 :
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
이게 말이 되길 바래
높이는 재귀에 의해 쉽게 구현되며 하위 트리의 최대 높이에 1을 더한 값을 취합니다.
"R의 균형 인자"는 균형이 맞지 않는 트리의 오른쪽 하위 트리를 나타냅니다.
즉석에서 나무 깊이를 계산할 필요가 없습니다.
작업을 수행 할 때 유지 관리 할 수 있습니다.
게다가 실제로 깊이 추적을 유지할 필요가 없습니다. 왼쪽과 오른쪽 나무 깊이의 차이를 간단히 추적 할 수 있습니다.
http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx
균형 요소 (왼쪽 및 오른쪽 하위 트리의 차이)를 추적하는 것만으로도 프로그래밍 POV에서 더 쉽게 찾을 수 있습니다. 단, 회전 후 균형 요소를 정렬하는 것이 PITA라는 점을 제외하면 ...
여기에 혼란 스러울 때 텍스트는 "R의 균형 계수가 1이면 해당 노드의 (외부) 오른쪽에서 삽입이 발생했으며 왼쪽 회전이 필요함을 의미합니다"라고 말합니다. 그러나 m 이해에서 텍스트는 균형 요소가 [-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
회전하기 전에-그리고 그 상태로 들어가기 위해 오른쪽 회전을해야 할 수도 있습니다. 하지만 이미 그 상태에 있다면 왼쪽 회전 만하면됩니다.
높이를 찾는 다른 방법이 있습니다. 높이라는 노드에 추가 속성을 추가하십시오.
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이면 해당 노드의 (외부) 오른쪽에서 삽입이 발생했으며 왼쪽 회전이 필요함을 의미합니다"라고 말합니다. 그러나 m 이해에서 텍스트는 균형 요소가 [-1, 1] 내에 있으면 균형을 맞출 필요가 없다고 말했습니까?
R현재 노드의 오른쪽 자식입니다 N.
이면 balance(N) = +2일종의 회전이 필요합니다. 하지만 어떤 회전을 사용할까요? 글쎄, 그것은에 달려 있습니다 balance(R): 그렇다면 balance(R) = +1왼쪽 회전이 필요하다면 N; 그러나 그렇다면 balance(R) = -1일종의 이중 회전이 필요합니다.
생성자에서 0으로 초기화 BinaryTree<T, Comparator>::Node된 subtreeHeight데이터 멤버를 제공 하고 다음을 사용하여 매번 자동으로 업데이트합니다.
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);
}
Here is the entire code: http://ideone.com/d6arrv
This BFS-like solution is pretty straightforward. Simply jumps levels one-by-one.
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
'programing tip' 카테고리의 다른 글
| conda environment.yml과 pip requirements.txt 결합 (0) | 2020.12.05 |
|---|---|
| Oracle DB에서 실행중인 프로세스를 어떻게 표시합니까? (0) | 2020.12.05 |
| 단위 테스트 파일 I / O (0) | 2020.12.05 |
| git을 사용하여 작업 트리를 인덱스 상태로 재설정하는 방법은 무엇입니까? (0) | 2020.12.05 |
| jsdoc로 익명 객체와 함수를 문서화하는 가장 좋은 방법 (0) | 2020.12.05 |