В настоящее время я нахожусь в середине реализации вставки дерева AVL, и я борюсь за поддержание коэффициентов баланса при вставке и возврате в дерево.
Практически каждая реализация AVL, которую я могу найти в качестве примераиспользует высоту двух поддеревьев узла для вычисления коэффициента баланса, что-то вроде
node.balance = node.right.height - node.left.height
И это прекрасно, если ваш класс Node выглядит примерно так:
class Node {
int value, height;
Node left, right;
}
Хотя проблема заключается в том, что для этой конкретной реализации, это «против правил», чтобы отслеживать высоту узла, и вместо этого мы можем отслеживать только коэффициент баланса.Таким образом, класс Node выглядит как
class Node {
int value, balance;
Node left, right;
}
. Я знаю, что поддержание коэффициента баланса узла концептуально аналогично поддержанию высоты для каждой вставки в дерево, но для жизни я не могувыяснить все ситуации, в которых коэффициент баланса должен измениться для конкретного узла.
В настоящий момент я установил коэффициент баланса, реализованный вместо этого путем рекурсивного вызова функции высоты для каждого узла (неоптимально!), чтобы убедиться, что мои повороты и общая вставка верны.
node.balance = height(node.right) - height(node.left)
Где height() рекурсивно обходит дерево, чтобы найти самый длинный путь к листу.
И я проверилчто логика ротации действительно верна, но когда я начинаю писать код для поддержания баланса на +1, постепенно возвращаясь к дереву, код сразу превращается в спагетти, поскольку я явно не понимаю чего-то фундаментального в отношении фактора баланса узлов.
Если вы хотите увидеть этот код, я разместил его ниже (он немного длинный).И нижеприведенная реализация также является String AVL Tree, но идея та же.
Любой вклад приветствуется, спасибо!
class StringAVLNode {
private String item;
private int balance;
private StringAVLNode left, right;
// just one constructor, please
public StringAVLNode(String str) {
item = str;
balance = 0;
left = null; right = null;
}
public int getBalance () {
return balance;
}
public void setBalance ( int bal){
balance = bal;
}
public String getItem () {
return item;
}
public StringAVLNode getLeft () {
return left;
}
public void setLeft (StringAVLNode pt){
left = pt;
}
public StringAVLNode getRight () {
return right;
}
public void setRight (StringAVLNode pt){
right = pt;
}
public void insert(String str) {
root = insert(str, root);
}
private StringAVLNode insert(String str, StringAVLNode t) {
// Base case - Just insert the node
if (t == null)
t = new StringAVLNode(str);
else {
int balance, leftChildBalance, rightChildBalance;
leftChildBalance = t.getLeft() != null ? t.getLeft().getBalance() : -99;
rightChildBalance = t.getRight() != null ? t.getRight().getBalance() : -99;
// Perform string comparisons to determine left/right insert
int compareResult = str.compareToIgnoreCase(t.getItem());
if (compareResult < 0) {
t.setLeft(insert(str, t.getLeft()));
if (t.getRight() == null)
t.setBalance(t.getBalance()-1);
else if (leftChildBalance == 0 && t.getLeft().getBalance() != 0)
t.setBalance(t.getBalance()-1);
else if (leftChildBalance == -99 && t.getLeft() != null)
t.setBalance(t.getBalance()-1);
}
else if (compareResult > 0) {
t.setRight(insert(str, t.getRight()));
if (t.getLeft() == null)
t.setBalance(t.getBalance()+1);
else if (rightChildBalance == 0 && t.getRight().getBalance() != 0)
t.setBalance(t.getBalance()+1);
else if (rightChildBalance == -99 && t.getRight() != null)
t.setBalance(t.getBalance()+1);
}
balance = t.getBalance();
// Verbosify booleans
boolean rightImbalance = balance > 1; boolean leftImbalance = balance < -1;
// Imbalance tree situation calls balanceTrees() to handle the rotation logic
// ( Keeps insert() succinct )
if (rightImbalance || leftImbalance)
t = balanceTrees(balance, t);
}
return t;
}
// Rotation Handler
private StringAVLNode balanceTrees(int balance, StringAVLNode t) {
// Verbosify boolean values
boolean rightHeavy = balance > 1; boolean leftHeavy = balance < -1;
boolean requiresDoubleLeft = t.getRight() != null && t.getRight().getBalance() <= -1;
boolean requiresDoubleRight = t.getLeft() != null && t.getLeft().getBalance() >= 1;
if (rightHeavy) {
/** Do double left rotation by right rotating the right child subtree, then
* rotate left
*/
if (requiresDoubleLeft) {
t.setRight(rotateRight(t.getRight()));
t.getRight().setBalance(0);
t = rotateLeft(t);
t.setBalance(0);
}
else {
t = rotateLeft(t);
t.setBalance(0);
if (t.getLeft() != null) t.getLeft().setBalance(0);
if (t.getRight() != null) t.getRight().setBalance(0);
}
}
/** Do double right rotation by left rotating the left child subtree, then
* rotate right
*/
else if (leftHeavy) {
if (requiresDoubleRight) {
t.setLeft(rotateLeft(t.getLeft()));
t.getLeft().setBalance(0);
t = rotateRight(t);
t.setBalance(0);
}
else {
t = rotateRight(t);
t.setBalance(0);
if (t.getLeft() != null) t.getLeft().setBalance(0);
if (t.getRight() != null) t.getRight().setBalance(0);
}
}
if (t.getLeft() != null) {
if (t.getLeft().getRight() != null && t.getLeft().getLeft() == null)
t.getLeft().setBalance(1);
else if (t.getLeft().getLeft() != null && t.getLeft().getRight() == null)
t.getLeft().setBalance(-1);
else if ((t.getLeft().getLeft() != null && t.getLeft().getRight() != null)
|| (t.getLeft().getLeft() == null && t.getLeft().getRight() == null))
t.getLeft().setBalance(0);
}
if (t.getRight() != null) {
if (t.getRight().getRight() != null && t.getRight().getLeft() == null)
t.getRight().setBalance(1);
else if (t.getRight().getLeft() != null && t.getRight().getRight() == null)
t.getRight().setBalance(-1);
else if ((t.getRight().getLeft() != null && t.getRight().getRight() != null)
|| (t.getRight().getLeft() == null && t.getRight().getRight() == null))
t.getRight().setBalance(0);
}
return t;
}
}