Мобильная версия
Я пытаюсь реализовать Мы с AVL TREE столкнулись с проблемой: как обновлять высоту всякий раз, когда я вставляю новый узел?
Я знаю, что мне нужно обновлять высоту узла до конца.< /p>
Например, на изображении дерево имеет 2 узла: 50 и 52. H означает высоту, а BF означает коэффициент баланса. После вставки узла 51 и обновления высот всех его предков (52 и 50) я сталкиваюсь с узлом 50, высота которого обновлена до 3, а BF — до 2, и он становится несбалансированным.
После выполнения поворота вправо влево высоты перепутались. Как правильно обновить высоту после любого поворота?
Коэффициент баланса = node.right - node.left
public void insertTree(String word) {
if (nodeCount == 0) {
this.root = new AVLNode(word, 1, 0, null, null, null);
AVLNode left = new AVLNode(null, null, 0, 0, this.root, null, null);
AVLNode right = new AVLNode(null, null, 0, 0, this.root, null, null);
this.root.setLeft(left);
this.root.setRight(right);
this.nodeCount++;
return;
}
AVLNode nodeFound = treeSearch(word, this.root);
AVLNode left = new AVLNode(null, 0, 0, nodeFound, null, null);
AVLNode right = new AVLNode(null, 0, 0, nodeFound, null, null);
nodeFound.setWord(word);
nodeFound.setLeft(left);
nodeFound.setRight(right);
nodeFound.setHeight(1);
nodeFound.setBF(0);
this.nodeCount++;
// Update height
updateTree(nodeFound.getParent());
}
public void updateTree(AVLNode node) {
while (node != null) {
AVLNode nodeParent = node.getParent();
node.setHeight(height2(node));
balanceFactor(node);
// Check if its necessary to do any rotation. Update the ancestor of the node
balance(node);
node = nodeParent;
}
}
public int height(AVLNode node) {
int heightLeft = node.getLeft().getHeight();
int heightRight = node.getRight().getHeight();
int height = 1 + Math.max(heightLeft, heightRight);
return height;
}
Подробнее здесь: https://stackoverflow.com/questions/740 ... a-rotation
