Hi, I am trying to balance an AVL tree. I have the most code done, and the tree

Question

 Hi, I am trying to balance an AVL tree. I have the most code done, and the tree is proporly balanced, however, the Height and Balance are wrong when the program run.  My program output: 4 (H:2, B:0)   L:1 (H:1, B:0)     L:0 (H:0, B:0)     R:2 (H:0, B:0)   R:7 (H:1, B:0)     L:6 (H:0, B:0)     R:9 (H:0, B:0) The correct output: 4 (H:3, B:0)   L:1 (H:2, B:0)     L:0 (H:1, B:0)     R:2 (H:1, B:0)   R:7 (H:2, B:0)     L:6 (H:1, B:0)     R:9 (H:1, B:0)  Can you help me to debug the height? The following are my code. Thank you!  public interface Map {     public int size();     public void put(String key, String value);     public String get(String key); } 

  public class AVLTreeMap implements Map {      class Node {         String key;         String value;         int height;         Node left;         Node right;         private int size;          public Node(String key, String value) {             this.key = key;             this.value = value;             this.height = 1;             this.left = null;             this.right = null;         }          private int balanceVal;          public int balance() {             return balanceVal = balanceCheck(root);         }     }      private Node root;      public AVLTreeMap() {         root = null;     }      public void put(String key, String value) {         root = put(root, key, value);     }      private Node put(Node node, String key, String value) {         if (node == null) {             return new Node(key, value);         }         if (key.compareTo(node.key) < 0) {             node.left = put(node.left, key, value);         } else if (key.compareTo(node.key) > 0) {             node.right = put(node.right, key, value);         } else {             node.value = value;             return node;         }         node.size = 1 + size(node.left) + size(node.right);         node.height = 1 + Math.max(height(node.left), height(node.right));         return balance(node);     }      public int size() {         return size(root);     }      private int size(Node node) {         if (node == null) {             return 0;         }         return node.size;     }      private int height(Node node) {         if (node == null) {             return -1;         }         return node.height;     }      private int balanceCheck(Node x) {         return height(x.left) - height(x.right);     }      private Node balance(Node node) {         if (balanceCheck(node) < -1) {             if (balanceCheck(node.right) > 0) {                 node.right = rotateRight(node.right);             }             node = rotateLeft(node);         } else if (balanceCheck(node) > 1) {             if (balanceCheck(node.left) < 0) {                 node.left = rotateLeft(node.left);             }             node = rotateRight(node);         }         return node;     }      private Node rotateRight(Node x) {         Node y = x.left;         x.left = y.right;         y.right = x;         y.size = x.size;         x.size = 1 + size(x.left) + size(x.right);         x.height = 1 + Math.max(height(x.left), height(x.right));         y.height = 1 + Math.max(height(y.left), height(y.right));         return y;     }      private Node rotateLeft(Node x) {         Node y = x.right;         x.right = y.left;         y.left = x;         y.size = x.size;         x.size = 1 + size(x.left) + size(x.right);         x.height = 1 + Math.max(height(x.left), height(x.right));         y.height = 1 + Math.max(height(y.left), height(y.right));         return y;     }      public String get(String key) {         Node x = get(root, key);         if (x == null)             return null;         return x.value;     }      private Node get(Node node, String key) {         if (node == null) {             return null;         }         if (key.compareTo(node.key) < 0) {             return get(node.left, key);         } else if (key.compareTo(node.key) > 0) {             return get(node.right, key);         } else {             return node;         }     }      public void print() {         this.print(this.root, "", 0);     }      private void print(Node node, String prefix, int depth) {         if (node == null) {             return;         }         for (int i = 0; i < depth; i++) {             System.out.print("  ");         }         if (!prefix.equals("")) {             System.out.print(prefix);             System.out.print(":");         }         System.out.print(node.key);         System.out.print(" (");         System.out.print("H:");         System.out.print(node.height);         System.out.print(", B:");         System.out.print(node.balance());         System.out.println(")");         this.print(node.left, "L", depth + 1);         this.print(node.right, "R", depth + 1);     }      public static void main(String[] args) {         AVLTreeMap map = new AVLTreeMap();         String[] keys = {"7", "9", "6", "0", "4", "2", "1"};         String[] values = {"seven", "nine", "six", "zero", "four", "two", "one"};         for (int i = 0; i < keys.length; i++) {             map.put(keys[i], values[i]);             map.print();             System.out.println();         }         for (int i = 0; i < keys.length; i++) {             System.out.print(keys[i]);             System.out.print(" ");             System.out.println(map.get(keys[i]));         }     } } 

Explanation / Answer

public interface Map { public int size(); public void put(String key, String value); public String get(String key); } public class AVLTreeMap implements Map { class Node { String key; String value; int height; Node left; Node right; private int size; public Node(String key, String value) { this.key = key; this.value = value; this.height = 1; this.left = null; this.right = null; } private int balanceVal; public int balance() { return balanceVal = balanceCheck(root); } } private Node root; public AVLTreeMap() { root = null; } public void put(String key, String value) { root = put(root, key, value); } private Node put(Node node, String key, String value) { if (node == null) { return new Node(key, value); } if (key.compareTo(node.key) < 0) { node.left = put(node.left, key, value); } else if (key.compareTo(node.key) > 0) { node.right = put(node.right, key, value); } else { node.value = value; return node; } node.size = 1 + size(node.left) + size(node.right); node.height = 1 + Math.max(height(node.left), height(node.right)); return balance(node); } public int size() { return size(root); } private int size(Node node) { if (node == null) { return 0; } return node.size; } private int height(Node node) { if (node == null) { return -1; } return node.height; } private int balanceCheck(Node x) { return height(x.left) - height(x.right); } private Node balance(Node node) { if (balanceCheck(node) < -1) { if (balanceCheck(node.right) > 0) { node.right = rotateRight(node.right); } node = rotateLeft(node); } else if (balanceCheck(node) > 1) { if (balanceCheck(node.left) < 0) { node.left = rotateLeft(node.left); } node = rotateRight(node); } return node; } private Node rotateRight(Node x) { Node y = x.left; x.left = y.right; y.right = x; y.size = x.size; x.size = 1 + size(x.left) + size(x.right); x.height = 1 + Math.max(height(x.left), height(x.right)); y.height = 1 + Math.max(height(y.left), height(y.right)); return y; } private Node rotateLeft(Node x) { Node y = x.right; x.right = y.left; y.left = x; y.size = x.size; x.size = 1 + size(x.left) + size(x.right); x.height = 1 + Math.max(height(x.left), height(x.right)); y.height = 1 + Math.max(height(y.left), height(y.right)); return y; } public String get(String key) { Node x = get(root, key); if (x == null) return null; return x.value; } private Node get(Node node, String key) { if (node == null) { return null; } if (key.compareTo(node.key) < 0) { return get(node.left, key); } else if (key.compareTo(node.key) > 0) { return get(node.right, key); } else { return node; } } public void print() { this.print(this.root, "", 0); } private void print(Node node, String prefix, int depth) { if (node == null) { return; } for (int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.