I wrote a program for building and initializing AVL tree.

The task is to find the minimum value of the tree (not the key). Wrote a method, but it returns a reference to the operation, not the value itself. I spent 2 hours did not understand, here is the code:

package lab6_TA; class AVL <Key extends Comparable<Key>, Value> { public class Node { private int h; private int balance; Key key; Value value; private Node left, right, father; public Node (Key key, Value value, Node father) { this.key = key; this.value = value; this.left = this.right = null; this.father = father; this.h = 1; this.balance = 0; } public Node next(){ return getHigherNode(this.key); } public Node previus(){ return getLowerNode(this.key); } } private Node root; private Node getHigherNode(Key key) { Node p = root; while (p != null) { int cmp = key.compareTo(p.key); if (cmp < 0) { if (p.left != null) p = p.left; else return p; } else { if (p.right != null) { p = p.right; } else { Node father = p.father; Node ch = p; while (father != null && ch == father.right) { ch = father; father = father.father; } return father; } } } return null; } private Node getLowerNode(Key key) { Node p = root; while (p != null) { int cmp = key.compareTo(p.key); if (cmp > 0) { if (p.right != null) p = p.right; else return p; } else { if (p.left != null) { p = p.left; } else { Node father = p.father; Node ch = p; while (father != null && ch == father.left) { ch = father; father = father.father; } return father; } } } return null; } public Node getFirstNode(){ return min(root); } public Node getLastNode(){ return max(root); } private int height(Node x, Node y){ if(x == null && y == null) return 0; else if(x == null) return yh; else if(y == null) return xh; else return Math.max(xh, yh); } private int balance(Node x, Node y){ if(x == null && y == null) return 0; else if(x == null) return - yh; else if(y == null) return xh; else return xh - yh; } private Node add (Node node,Key key, Value value, Node father){ if (node == null){ Node newnode = new Node(key,value, father); return newnode; } int compareResult = key.compareTo(node.key); if (compareResult > 0){node.right = add(node.right, key, value, node); node.h = height(node.left, node.right) + 1;} else if(compareResult < 0){node.left = add(node.left, key, value, node); node.h = height(node.left, node.right) + 1;} else{ node.value = value; } node.balance = balance(node.left, node.right); if(node.balance == -2){ node = leftRotation(node); }else if(node.balance == 2){ node = rightRotation(node); } return node; } private Node leftRotation(Node node) { if(node.right.right == null && node.right.left != null){ node.right = rightRotation(node.right); node = leftRotation(node); }else if(node.right.left == null || node.right.left.h <= node.right.right.h){ Node newnode = node.right; newnode.father = node.father; node.right = newnode.left; if(node.right != null) node.right.father = node; node.h = height(node.left, node.right)+1; node.father = newnode; node.balance = balance(node.left, node.right); newnode.left = node; node = newnode; node.balance = balance(node.left, node.right); node.h = height(node.left, node.right)+1; }else{ node.right = rightRotation(node.right); node = leftRotation(node); } return node; } private Node rightRotation(Node node){ if(node.left.right != null && node.left.left == null){ node.left = leftRotation(node.left); node = rightRotation(node); }else if(node.left.right == null || node.left.right.h <= node.left.left.h){ Node newnode = node.left; newnode.father = node.father; node.left = newnode.right; if(node.left != null) node.left.father = node; node.h = height(node.left, node.right)+1; node.father = newnode; node.balance = balance(node.left, node.right); newnode.right = node; node = newnode; node.balance = balance(node.left, node.right); node.h = height(node.left, node.right)+1; }else{ node.left = leftRotation(node.left); node = rightRotation(node); } return node; } public void add(Key key, Value value) { root = add(root, key, value, null); } private Node delete(Node node, Key key){ if(node == null) return null; int compareResult = key.compareTo(node.key); if(compareResult > 0){ node.right = delete(node.right, key); }else if(compareResult < 0){ node.left = delete(node.left, key); }else{ if(node.right == null && node.left == null){ node = null; }else if(node.right == null){ node.left.father = node.father; node = node.left; }else if(node.left == null){ node.right.father = node.father; node = node.right; }else{ if(node.right.left == null){ node.right.left = node.left; node.right.father = node.father; node.right.father = node.father; node.left.father = node.right; node = node.right; }else{ Node res = min(node.right); node.key = res.key; node.value = res.value; delete(node.right, node.key); } } } if(node != null) { node.h = height(node.left, node.right) + 1; node.balance = balance(node.left, node.right); if (node.balance == -2) { node = leftRotation(node); } else if (node.balance == 2) { node = rightRotation(node); } } return node; } public void delete(Key key) { root = delete(root, key); } public Key minKey(){ return min(root).key; } public Key maxKey(){ return max(root).key; } public Node min(Node node){ if(node.left == null) return node; return min(node.left); } private Node max(Node node){ if(node.right == null) return node; return min(node.right); } private Value get(Node node, Key key){ if(node == null) return null; int compareResult = key.compareTo(node.key); if(compareResult == 0){ return node.value; }else if(compareResult > 0){ return get(node.right, key); }else{ return get(node.left, key); } } public Value get(Key key) { return get(root, key); } private void print(Node node, int level) { if (node != null) { print(node.right,level+1); for (int i=0;i<level;i++) { System.out.print("\t"); } } } public void print() { print(root,0); } public static void main(String[] args){ AVL<Integer, Integer> tree = new AVL<>(); tree.add(10,10); tree.print(); tree.add(11,11); tree.print(); tree.add(15,12); tree.print(); tree.add(13,12); tree.print(); tree.add(16,12); tree.print(); tree.add(12,12); tree.print(); tree.add(3,2); tree.print(); tree.add(1,1); tree.print(); tree.add(0,1); tree.print(); tree.add(2,1); tree.print(); tree.delete(13); tree.print(); tree.delete(10); tree.print(); for(AVL.Node e = tree.getFirstNode(); e != null; e = e.next()){ System.out.println(e.key); System.out.println(); } } }
  • one
    1. See How to create a minimal, self-contained, and reproducible example . I do not think that people will sit and understand your code. 2. A little bombolayo - do you read yourself when you write messages without any punctuation marks, without separating them? Wrote the program for building and initializing the AVL tree. The task is to find the minimum value of the tree (not the key). I wrote a method, but it returns a reference to the operator, but it’s not the value that I spent 2 hours
  • If you insert only the method in which I get the minimum value of the element, then it is unclear how I build the tree, how to add values ​​and keys, etc. And everything is a problem at the command level - Identin

0