AVLTree 類別擴充了BST 類別來覆蓋insert 和deletedeletedeletedeleteAVLTree
類別的完整原始碼。
package demo;
public class AVLTree<E extends Comparable<E>> extends BST<E> {
/** Create an empty AVL tree */
public AVLTree() {}
/** Create an AVL tree from an array of objects */
public AVLTree(E[] objects) {
super(objects);
}
@Override /** Override createNewNode to create an AVLTreeNode */
protected AVLTreeNode<E> createNewNode(E e) {
return new AVLTreeNode<E>(e);
}
@Override /** Insert an element and rebalance if necessary */
public boolean insert(E e) {
boolean successful = super.insert(e);
if (!successful)
return false; // e is already in the tree
else {
balancePath(e); // Balance from e to the root if necessary
}
return true; // e is inserted
}
/** Update the height of a specified node */
private void updateHeight(AVLTreeNode<E> node) {
if (node.left == null && node.right == null) // node is a leaf
node.height = 0;
else if (node.left == null) // node has no left subtree
node.height = 1 + ((AVLTreeNode<E>)(node.right)).height;
else if (node.right == null) // node has no right subtree
node.height = 1 + ((AVLTreeNode<E>)(node.left)).height;
else
node.height = 1 + Math.max(((AVLTreeNode<E>)(node.right)).height, ((AVLTreeNode<E>)(node.left)).height);
}
/** Balance the nodes in the path from the specified
* node to the root if necessary
*/
private void balancePath(E e) {
java.util.ArrayList<TreeNode<E>> path = path(e);
for (int i = path.size() - 1; i >= 0; i--) {
AVLTreeNode<E> A = (AVLTreeNode<E>)(path.get(i));
updateHeight(A);
AVLTreeNode<E> parentOfA = (A == root) ? null : (AVLTreeNode<E>)(path.get(i - 1));
switch (balanceFactor(A)) {
case -2:
if (balanceFactor((AVLTreeNode<E>)A.left) <= 0) {
balanceLL(A, parentOfA); // Perform LL rotation
}
else {
balanceLR(A, parentOfA); // Perform LR rotation
}
break;
case +2:
if (balanceFactor((AVLTreeNode<E>)A.right) >= 0) {
balanceRR(A, parentOfA); // Perform RR rotation
}
else {
balanceRL(A, parentOfA); // Perform RL rotation
}
}
}
}
/** Return the balance factor of the node */
private int balanceFactor(AVLTreeNode<E> node) {
if (node.right == null) // node has no right subtree
return -node.height;
else if (node.left == null) // node has no left subtree
return +node.height;
else
return ((AVLTreeNode<E>)node.right).height - ((AVLTreeNode<E>)node.left).height;
}
/** Balance LL (see Figure 26.2) */
private void balanceLL(TreeNode<E> A, TreeNode<E> parentOfA) {
TreeNode<E> B = A.left; // A is left-heavy and B is left-heavy
if (A == root) {
root = B;
}
else {
if (parentOfA.left == A) {
parentOfA.left = B;
}
else {
parentOfA.right = B;
}
}
A.left = B.right; // Make T2 the left subtree of A
B.right = A; // Make A the left child of B
updateHeight((AVLTreeNode<E>)A);
updateHeight((AVLTreeNode<E>)B);
}
/** Balance LR (see Figure 26.4) */
private void balanceLR(TreeNode<E> A, TreeNode<E> parentOfA) {
TreeNode<E> B = A.left; // A is left-heavy
TreeNode<E> C = B.right; // B is right-heavy
if (A == root) {
root = C;
}
else {
if (parentOfA.left == A) {
parentOfA.left = C;
}
else {
parentOfA.right = C;
}
}
A.left = C.right; // Make T3 the left subtree of A
B.right = C.left; // Make T2 the right subtree of B
C.left = B;
C.right = A;
// Adjust heights
updateHeight((AVLTreeNode<E>)A);
updateHeight((AVLTreeNode<E>)B);
updateHeight((AVLTreeNode<E>)C);
}
/** Balance RR (see Figure 26.3) */
private void balanceRR(TreeNode<E> A, TreeNode<E> parentOfA) {
TreeNode<E> B = A.right; // A is right-heavy and B is right-heavy
if (A == root) {
root = B;
}
else {
if (parentOfA.left == A) {
parentOfA.left = B;
}
else {
parentOfA.right = B;
}
}
A.right = B.left; // Make T2 the right subtree of A
B.left = A;
updateHeight((AVLTreeNode<E>)A);
updateHeight((AVLTreeNode<E>)B);
}
/** Balance RL (see Figure 26.5) */
private void balanceRL(TreeNode<E> A, TreeNode<E> parentOfA) {
TreeNode<E> B = A.right; // A is right-heavy
TreeNode<E> C = B.left; // B is left-heavy
if (A == root) {
root = C;
}
else {
if (parentOfA.left == A) {
parentOfA.left = C;
}
else {
parentOfA.right = C;
}
}
A.right = C.left; // Make T2 the right subtree of A
B.left = C.right; // Make T3 the left subtree of B
C.left = A;
C.right = B;
// Adjust heights
updateHeight((AVLTreeNode<E>)A);
updateHeight((AVLTreeNode<E>)B);
updateHeight((AVLTreeNode<E>)C);
}
@Override /** Delete an element from the AVL tree.
* Return true if the element is deleted successfully
* Return false if the element is not in the tree */
public boolean delete(E element) {
if (root == null)
return false; // Element is not in the tree
// Locate the node to be deleted and also locate its parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null) {
if (element.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (element.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
break; // Element is in the tree pointed by current
}
if (current == null)
return false; // Element is not in the tree
// Case 1: current has no left children (See Figure 25.10)
if (current.left == null) {
// Connect the parent with the right child of the current node
if (parent == null) {
root = current.right;
}
else {
if (element.compareTo(parent.element) < 0)
parent.left = current.right;
else
parent.right = current.right;
// Balance the tree if necessary
balancePath(parent.element);
}
}
else {
// Case 2: The current node has a left child
// Locate the rightmost node in the left subtree of
// the current node and also its parent
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right; // Keep going to the right
}
// Replace the element in current by the element in rightMost
current.element = rightMost.element;
// Eliminate rightmost node
if (parentOfRightMost.right == rightMost)
parentOfRightMost.right = rightMost.left;
else
// Special case: parentOfRightMost is current
parentOfRightMost.left = rightMost.left;
// Balance the tree if necessary
balancePath(parentOfRightMost.element);
}
size--;
return true; // Element inserted
}
/** AVLTreeNode is TreeNode plus height */
protected static class AVLTreeNode<E extends Comparable<E>> extends BST.TreeNode<E> {
protected int height = 0; // New data field
public AVLTreeNode(E e) {
super(e);
}
}
}
登入後複製
AVLTree 類別擴充了 BST。與BST 類別一樣，AVLTree 類別有一個無參數建構函數，用於建構一個空的AVLTree（第5 行）和一個用於建立初始AVLTree
來自元素數組（第8-10 行）。
BST 類別中定義的 createNewNode() 方法建立一個 TreeNode。重寫此方法以傳回 AVLTreeNode
（第 13-15 行）。
AVLTree 中的 insert 方法在第 18-27 行被覆蓋。此方法首先呼叫 BST 中的 insert 方法，然後呼叫 balancePath(e)
（第 23 行）以確保樹是平衡的。
balancePath 方法首先取得從包含元素 e
的節點到根節點的路徑上的節點（第 45 行）。對於路徑中的每個節點，更新其高度（第 48 行），檢查其平衡係數（第 51 行），並在必要時執行適當的旋轉（第 51-67 行）。
第 82-178 行定義了四種執行旋轉的方法。每個方法都使用兩個 TreeNode 參數 — A 和 parentOfA 進行呼叫 — 以在節點 A 處執行適當的旋轉。貼文中的附圖說明如何執行每次旋轉。旋轉後，節點 A、B 和 C
的高度更新（第 98、125、148、175 行）。
AVLTree 中的 delete 方法在第 183-248 行重寫。此方法與 BST
類別中實作的方法相同，但在兩種情況下需要在刪除後重新平衡節點（第 218、243 行）。
以上是AVLTree 類的詳細內容。更多資訊請關注PHP中文網其他相關文章！
