avltree类扩展了bst类以重写insert和delete方法以在必要时重新平衡树。下面的代码给出了 avltree 类的完整源代码。
package demo;public class AVLTree<E extends Comparable> extends BST { /** 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 createNewNode(E e) { return new AVLTreeNode(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 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)(node.right)).height; else if (node.right == null) // node has no right subtree node.height = 1 + ((AVLTreeNode)(node.left)).height; else node.height = 1 + Math.max(((AVLTreeNode)(node.right)).height, ((AVLTreeNode)(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> path = path(e); for (int i = path.size() - 1; i >= 0; i--) { AVLTreeNode A = (AVLTreeNode)(path.get(i)); updateHeight(A); AVLTreeNode parentOfA = (A == root) ? null : (AVLTreeNode)(path.get(i - 1)); switch (balanceFactor(A)) { case -2: if (balanceFactor((AVLTreeNode)A.left) <= 0) { balanceLL(A, parentOfA); // Perform LL rotation } else { balanceLR(A, parentOfA); // Perform LR rotation } break; case +2: if (balanceFactor((AVLTreeNode)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 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)node.right).height - ((AVLTreeNode)node.left).height; } /** Balance LL (see Figure 26.2) */ private void balanceLL(TreeNode A, TreeNode parentOfA) { TreeNode 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)A); updateHeight((AVLTreeNode)B); } /** Balance LR (see Figure 26.4) */ private void balanceLR(TreeNode A, TreeNode parentOfA) { TreeNode B = A.left; // A is left-heavy TreeNode 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)A); updateHeight((AVLTreeNode)B); updateHeight((AVLTreeNode)C); } /** Balance RR (see Figure 26.3) */ private void balanceRR(TreeNode A, TreeNode parentOfA) { TreeNode 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)A); updateHeight((AVLTreeNode)B); } /** Balance RL (see Figure 26.5) */ private void balanceRL(TreeNode A, TreeNode parentOfA) { TreeNode B = A.right; // A is right-heavy TreeNode 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)A); updateHeight((AVLTreeNode)B); updateHeight((AVLTreeNode)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 parent = null; TreeNode current = root; while (current != null) { 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 parentOfRightMost = current; TreeNode 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> extends BST.TreeNode { 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 行）。
分类插件jquery.sort.js
分类插件jquery.sort.js
41 查看详情
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 类的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/509547.html
微信扫一扫 
支付宝扫一扫 
