0
Java에서 BST AVL을 얻었습니다.이 노드는 마지막 10 개의 노드를 인쇄하여 균형을 유지해야합니다. 내 hack-y 솔루션은 노드 수를 알고 순차적 탐색의 마지막 10 개 노드에서 값을 가져 오는 것이 었습니다. 그것은 의도 한대로 작동하지 않습니다. 레코드는 성 키와 함께 저장되며 (중복 레코드는 보관되지 않음) 각 노드의 크기가 0으로 인쇄됩니다. 제 출력물은 예상대로 대부분 'Z'이름을 가지고 있습니다. 그리고 나서 26000의 첫 번째 기록이 출력됩니다. 나는 나무의 잘못과는 반대로, 내가 어떻게 내 인쇄물을 고안해 냈는지에 관한 문제를 추측하고있다. 지난 10 개의 노드를 인쇄하는 좀 더 우아한 방법이 있습니까? 지금 가지고있는 오류가 없거나 나무 회전에 결함이있을 가능성이 있습니까?AVL 균형 잡힌 트리 - 마지막 10 개 노드를 인쇄합니다.
중위 이송 출력 : (a get 함수를 통해 액세스 출력)
public void inOrder(Node x)
{
if (x == null)
return; //stops recursion when there is no Node
inOrder(x.left); //always traverse left first
inOrder(x.right); //traverse right
inOrderTraversalOutput += Integer.toString((size(x.left)) +
(size(x.right))) + "\n";
bstNodes++;
//total nodes - 17151
if (bstNodes > 17145)
lastnodes += x.val.toString() + "Node left size: " +
size(x.left) + "\n" + "Node right size: " + size(x.right) +
"\n" + "----------------------------------------------------\n";
}
//modified to print total number of nodes
public String getTraversal()
{
inOrderTraversalOutput += Integer.toString(bstNodes) + "\n";
return inOrderTraversalOutput;
}
풋 방법
private Node put(Node x, Key key, Value val)
{
if (x == null)
{
return new Node(key, val, 0);
}
int cmp = key.compareTo(x.key);
if (cmp < 0)
{
x.left = put(x.left, key, val);
//AVL Balance
if ((size(x.left) - size(x.right)) >= 2)
{
if (x.key.compareTo(x.left.key) < 0)
{
x = rotateWithLeftsapling(x);
} else
{
x = doubleWithLeftsapling(x);
}
}
} else if (cmp > 0)
{
x.right = put(x.right, key, val);
//AVL Balance
if ((size(x.right) - size(x.left)) >= 2)
{
if (x.key.compareTo(x.right.key) > 0)
{
x = rotateWithRightsapling(x);
} else
{
x = doubleWithRightsapling(x);
}
}
} else
{
x.val = val;
}
x.N = size(x.left) + size(x.right);
return x;
}