Java中的AVL树旋转

我想实现Java AVL树并左右旋转树。 我没有得到这个。

任何人都可以通过查看下面的代码告诉我如何可以左右旋转树然后使用这两个函数修复来平衡AVL树？

我希望这里有人可以指导我完成这件事。

import java.util.Random; import java.util.SortedSet; import java.util.TreeSet; public class AVLTree extends BinarySearchTree<AVLTree.Node, T> implements SSet { Random rand; public static class Node extends BSTNode<Node,T> { int h; // the height of the node } public AVLTree() { sampleNode = new Node(); rand = new Random(); c = new DefaultComparator(); } public int height(Node u) { return (u == null) ? 0 : uh; } public boolean add(T x) { Node u = new Node(); ux = x; if (super.add(u)) { for (Node w = u; w != nil; w = w.parent) { // walk back up to the root adjusting heights wh = Math.max(height(w.left), height(w.right)) + 1; } fixup(u); return true; } return false; } public void splice(Node u) { Node w = u.parent; super.splice(u); for (Node z = u; z != nil; z = z.parent) zh = Math.max(height(z.left), height(z.right)) + 1; fixup(w); } public void checkHeights(Node u) { if (u == nil) return; checkHeights(u.left); checkHeights(u.right); if (height(u) != 1 + Math.max(height(u.left), height(u.right))) throw new RuntimeException("Check heights shows incorrect heights"); int dif = height(u.left) - height(u.right); if (dif  1) throw new RuntimeException("Check heights found height difference of " + dif); } /** * TODO: finish writing this method * @param u */ public void fixup(Node u) { while (u != nil) { int dif = height(u.left) - height(u.right); if (dif > 1) { // TODO: add code here to fix AVL condition // on the path from u to the root, if necessary } else if (dif < -1) { // TODO: add code here to fix AVL condition // on the path from u to the root, if necessary } u = u.parent; } } public Node rotateLeft() { return rotateLeft(u.parent); } public void rotateLeft(Node u) { // TODO: Recompute height values at u and u.parent } public void rotateRight(Node u) { // TODO: Recompute height values at u and u.parent } public static  T find(SortedSet ss, T x) { SortedSet ts = ss.tailSet(x); if (!ts.isEmpty()) { return ts.first(); } return null; } /** * This just does some very basic correctness testing * @param args */ public static void main(String[] args) { AVLTree t = new AVLTree(); Random r = new Random(0); System.out.print("Running AVL tests..."); int n = 1000; for (int i = 0; i < n; i++) { t.add(r.nextInt(2*n)); t.checkHeights(tr); } for (int i = 0; i < n; i++) { t.remove(r.nextInt(2*n)); t.checkHeights(tr); } System.out.println("done"); t.clear(); System.out.print("Running correctness tests..."); n = 100000; SortedSet ss = new TreeSet(); Random rand = new Random(); for (int i = 0; i < n; i++) { Integer x = rand.nextInt(2*n); boolean b1 = t.add(x); boolean b2 = ss.add(x); if (b1 != b2) { throw new RuntimeException("Adding " + x + " gives " + b2 + " in SortedSet and " + b1 + " in AVL Tree"); } } for (int i = 0; i < n; i++) { Integer x = rand.nextInt(2*n); Integer x1 = t.find(x); Integer x2 = find(ss, x); if (x1 != x2) { throw new RuntimeException("Searching " + x + " gives " + x2 + " in SortedSet and " + x1 + " in AVL Tree"); } ss.headSet(x); } for (int i = 0; i < n; i++) { Integer x = rand.nextInt(2*n); boolean b1 = t.remove(x); boolean b2 = ss.remove(x); if (b1 != b2) { throw new RuntimeException("Error (2): Removing " + x + " gives " + b2 + " in SortedSet and " + b1 + " in AVL Tree"); } } for (int i = 0; i < n; i++) { Integer x = rand.nextInt(2*n); Integer x1 = t.find(x); Integer x2 = find(ss, x); if (x1 != x2) { throw new RuntimeException("Error (3): Searching " + x + " gives " + x2 + " in SortedSet and " + x1 + " in AVL Tree"); } ss.headSet(x); } System.out.println("done"); } } 

Answer 1

完整的AVL树实现：

 public class AVLTree { private AVLNode root; private static class AVLNode { private T t; private int height; private AVLNode left; private AVLNode right; private AVLNode(T t) { this.t = t; height = 1; } } public void insert(T value) { root = insert(root, value); } private AVLNode insert(AVLNode n, T v) { if (n == null) { n = new AVLNode(v); return n; } else { int k = ((Comparable) nt).compareTo(v); if (k > 0) { n.left = insert(n.left, v); } else { n.right = insert(n.right, v); } n.height = Math.max(height(n.left), height(n.right)) + 1; int heightDiff = heightDiff(n); if (heightDiff < -1) { if (heightDiff(n.right) > 0) { n.right = rightRotate(n.right); return leftRotate(n); } else { return leftRotate(n); } } else if (heightDiff > 1) { if (heightDiff(n.left) < 0) { n.left = leftRotate(n.left); return rightRotate(n); } else { return rightRotate(n); } } else; } return n; } private AVLNode leftRotate(AVLNode n) { AVLNode r = n.right; n.right = r.left; r.left = n; n.height = Math.max(height(n.left), height(n.right)) + 1; r.height = Math.max(height(r.left), height(r.right)) + 1; return r; } private AVLNode rightRotate(AVLNode n) { AVLNode r = n.left; n.left = r.right; r.right = n; n.height = Math.max(height(n.left), height(n.right)) + 1; r.height = Math.max(height(r.left), height(r.right)) + 1; return r; } private int heightDiff(AVLNode a) { if (a == null) { return 0; } return height(a.left) - height(a.right); } private int height(AVLNode a) { if (a == null) { return 0; } return a.height; } } 

Answer 2

这是Java中AVL树的完整实现

 class Node { int key; Node left; Node right; int height; Node(int value) { key = value; left = null; right = null; height = 1; } } class AVLTree { Node root; int height(Node root) { if (root == null) return 0; return root.height; } int findHeight() { return height(root); } int findHeightFrom(int value) { Node node = search(root, value); if (node == null) return -1; return node.height; } Node search(Node root, int value) { if (root == null) return null; else { if (value == root.key) return root; else if (value < root.key) return search(root.left, value); else return search(root.right, value); } } boolean find(int value) { Node node = search(root,value); if (node == null) return false; return true; } int max(int one, int two) { return (one > two) ? one : two; } Node rightRotate(Node root) { Node rootLeftChild = root.left; root.left = rootLeftChild.right; rootLeftChild.right = root; root.height = max(height(root.left), height(root.right)) + 1; rootLeftChild.height = max(height(rootLeftChild.left), height(rootLeftChild.right)) + 1; return rootLeftChild; } Node leftRotate(Node root) { Node rootRightChild = root.right; root.right = rootRightChild.left; rootRightChild.left = root; root.height = max(height(root.left), height(root.right)) + 1; rootRightChild.height = max(height(rootRightChild.left), height(rootRightChild.right)) + 1; return rootRightChild; } Node insertNode(Node root, int value) { if (root == null) root = new Node(value); else { if (value < root.key) root.left = insertNode(root.left, value); else root.right = insertNode(root.right, value); } root.height = max(height(root.left), height(root.right)) + 1; int balanceFactor = height(root.left) - height(root.right); if (balanceFactor > 1) { // either left-left case or left-right case if (value < root.left.key) { // left-left case root = rightRotate(root); } else { // left-right case root.left = leftRotate(root.left); root = rightRotate(root); } } else if (balanceFactor < -1) { // either right-right case or right-left case if (value > root.right.key) { // right-right case root = leftRotate(root); } else { // right-left case root.right = rightRotate(root.right); root = leftRotate(root); } } return root; } void insert(int value) { root = insertNode(root, value); } void inorder(Node root) { if (root != null) { inorder(root.left); System.out.print(root.key + " "); inorder(root.right); } } void inorderTraversal() { inorder(root); System.out.println(); } void preorder(Node root) { if (root != null) { System.out.print(root.key + " "); preorder(root.left); preorder(root.right); } } void preorderTraversal() { preorder(root); System.out.println(); } } public class AVLTreeExample { public static void main(String[] args) { AVLTree avl = new AVLTree(); avl.insert(10); avl.insert(20); avl.insert(30); avl.insert(40); avl.insert(50); avl.insert(25); System.out.print("Inorder Traversal : "); avl.inorderTraversal(); System.out.print("Preorder Traversal : "); avl.preorderTraversal(); System.out.println("Searching for 10 : " + avl.find(10)); System.out.println("Searching for 11 : " + avl.find(11)); System.out.println("Searching for 20 : " + avl.find(20)); System.out.println("Height of the tree : " + avl.findHeight()); System.out.println("Finding height from 10 : " + avl.findHeightFrom(10)); System.out.println("Finding height from 20 : " + avl.findHeightFrom(20)); System.out.println("Finding height from 25 : " + avl.findHeightFrom(25)); } } 

Answer 3

为了正确旋转你需要首先检查父项是否不是root，如果父项是父项的权利，如果是，则将父项的右侧设置为其他项，设置gran父项的左侧给孩子

否则，root就是孩子