La classe AVLTree étend la classe BST pour remplacer les méthodes insert et delete pour rééquilibrer l'arbre si nécessaire. Le code ci-dessous donne le code source complet de la classe AVLTree.
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);
}
}
}
La classe AVLTree étend BST. Comme la classe BST, la classe AVLTree a un constructeur sans argument qui construit un AVLTree vide (lignes 5) et un constructeur qui crée un AVLTree à partir d'un tableau d'éléments (lignes 8 à 10).
La méthodecreateNewNode() définie dans la classe BST crée un TreeNode. Cette méthode est remplacée pour renvoyer un AVLTreeNode (lignes 13 à 15).
La méthodeinsert dans AVLTree est remplacée aux lignes 18 à 27. La méthode invoque d'abord la méthode insert dans BST, puis invoque balancePath(e) (ligne 23) pour s'assurer que l'arbre est équilibré.
La méthodebalancePath récupère d'abord les nœuds sur le chemin depuis le nœud qui contient l'élément e jusqu'à la racine (ligne 45). Pour chaque nœud du chemin, mettez à jour sa hauteur (ligne 48), vérifiez son facteur d'équilibre (ligne 51) et effectuez les rotations appropriées si nécessaire (lignes 51 à 67).
Quatre méthodes pour effectuer des rotations sont définies aux lignes 82 à 178. Chaque méthode est invoquée avec deux argumentsTreeNode—A et parentOfA—pour effectuer une rotation appropriée au nœud A. La manière dont chaque rotation est effectuée est illustrée dans les figures de l'article. Après la rotation, les hauteurs des nœuds A, B et C sont mises à jour (lignes 98, 125, 148, 175).
La méthodedelete dans AVLTree est remplacée aux lignes 183 à 248. La méthode est la même que celle implémentée dans la classe BST, sauf qu'il faut rééquilibrer les nœuds après suppression dans deux cas (lignes 218, 243).
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
