package treeplay.tree;
import java.util.LinkedList;
import java.util.List;
import static java.lang.Math.max;
public class AVLTree implements Tree {
@Override
public void add(int value) {
root = insert(root, value);
}
@Override
public boolean contains(int value) {
return find(value);
}
private static class AVLNode {
private int value;
private int height;
private AVLNode leftChild;
private AVLNode rightChild;
public AVLNode(int v) {
this.value = v;
}
@Override
public String toString() {
return "Node={" + this.value + "}";
}
}
@Override
public String toString() {
return this.root.toString();
}
private AVLNode root;
private boolean isEmpty() {
return this.root == null;
}
private AVLNode newNode(int v) {
return new AVLNode(v);
}
public AVLNode insert(AVLNode root, int value) {
if (root == null) {
return newNode(value);
}
if (value < root.value) {
root.leftChild = insert(root.leftChild, value);
} else {
root.rightChild = insert(root.rightChild, value);
}
resetHeight(root);
return balance(root);
}
private AVLNode balance(AVLNode root) {
if(isLeftHeavy(root)) {
if(balanceFactor(root.leftChild)<0) {
root.leftChild = rotateLeft(root.leftChild);
}
return rotateRight(root);
}else if(isRightHeavy(root)) {
if(balanceFactor(root.rightChild)>0) {
root.rightChild = rotateRight(root.rightChild);
}
return rotateLeft(root);
}
return root;
}
private AVLNode rotateLeft(AVLNode node) {
var newRoot = node.rightChild;
node.rightChild = newRoot.leftChild;
newRoot.leftChild = node;
resetHeight(node);
resetHeight(newRoot);
return newRoot;
}
private AVLNode rotateRight(AVLNode node) {
var newRoot = node.leftChild;
node.leftChild = newRoot.rightChild;
newRoot.rightChild = node;
resetHeight(node);
resetHeight(newRoot);
return newRoot;
}
private void resetHeight(AVLNode node) {
node.height = max(height(node.leftChild),height(node.rightChild))+1;
}
private int balanceFactor(AVLNode node) {
return (node==null)?0:height(node.leftChild)-height(node.rightChild);
}
private boolean isLeftHeavy(AVLNode node) {
return balanceFactor(node) > 1;
}
private boolean isRightHeavy(AVLNode node) {
return balanceFactor(node) < -1;
}
public boolean find(int value) {
var current = root;
while (current != null) {
if (value < current.value) {
current = current.leftChild;
} else if (value > current.value) {
current = current.rightChild;
} else {
return true;
}
}
return false;
}
private void traversePreOrder(AVLNode root) {
if (root == null) {
return;
}
System.out.print(root.value + " -> ");
traversePreOrder(root.leftChild);
traversePreOrder(root.rightChild);
}
private void traverseInOrder(AVLNode root) {
if (root == null) {
return;
}
traverseInOrder(root.leftChild);
System.out.print(root.value + " -> ");
traverseInOrder(root.rightChild);
}
public void traversePreOrderPrint() {
traversePreOrder(root);
System.out.println();
}
public void traverseInOrderPrint() {
traverseInOrder(root);
System.out.println();
}
@Override
public int height() {
return height(root);
}
private int height(AVLNode root) {
return (root == null) ? -1 : root.height;
}
public int minimum() {
if (root == null) {
throw new IllegalStateException();
}
var current = root;
while (current != null) {
if (current.leftChild == null) {
return current.value;
}
current = current.leftChild;
}
return Integer.MIN_VALUE;
}
private boolean isLeaf(AVLNode node) {
return node.leftChild == null && node.rightChild == null;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) return false;
if (obj instanceof SimpleBstTree) {
return equals(((AVLTree) obj).root, this.root);
}
return false;
}
private boolean equals(AVLNode first, AVLNode second) {
if (first == null && second == null) return true;
if (first != null && second != null) {
return first.value == second.value
&& first.leftChild == second.leftChild
&& first.rightChild == second.rightChild;
}
return false;
}
public boolean isBinarySearchTree() {
return isBinarySearchTree(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private boolean isBinarySearchTree(AVLNode root, int min, int max) {
if (root == null) return true;
if (root.value < min || root.value > max) {
return false;
}
return isBinarySearchTree(root.leftChild, min, root.value - 1)
&& isBinarySearchTree(root.rightChild, root.value, max);
}
private List<Integer> getNodesAtDistance(int distance) {
var list = new LinkedList<Integer>();
printNodesAtDistance(root, distance, list);
return list;
}
public void printNodesAtDistance(AVLNode root, int distance, List<Integer> list) {
if (root == null) return;
if (distance == 0) {
list.add(root.value);
return;
}
printNodesAtDistance(root.leftChild, distance - 1, list);
printNodesAtDistance(root.rightChild, distance - 1, list);
}
public void levelOrderTraversePrint() {
var h = height();
for (int i = 0; i <= h; ++i) {
var list = getNodesAtDistance(i);
int jj=0;
for (var value : list) {
String res = String.format("= ",value);
System.out.print(res);
if(jj++<list.size()) {
System.out.print("->");
}
}
System.out.println();
}
}
}
Processed:
0.011, SQL:
9
