Skip to content
Snippets Groups Projects

Update VerifyAVL.java

Open Isaac Xu requested to merge sxu4/ex08-verifyavl-public:sxu4-master-patch-90741 into master
1 file
+ 50
3
Compare changes
  • Side-by-side
  • Inline
@@ -2,8 +2,55 @@ package verifyavl;
public class VerifyAVL {
public static boolean verifyAVL(AVLNode root) {
/* TODO: Edit this with your code */
throw new IllegalStateException();
if(root == null) {
return true;
}
boolean isBst = verifyBst(root.left, root.right, root);
int hDiff = verifyBalance(root);
boolean isBalanced = true;
if (hDiff > 1) {
isBalanced = false;
}
if ((!isBst || !isBalanced) || (!verifyAVL(root.left) || !verifyAVL(root.right))) {
return false;
}
return true;
}
/* TODO: Add private methods if you want (recommended) */
}
\ No newline at end of file
private static boolean verifyBst(AVLNode left, AVLNode right, AVLNode root) {
if (left != null && left.key > root.key) {
return false;
} else if (right != null && right.key < root.key) {
return false;
}
return true;
}
private static int verifyBalance(AVLNode root) {
int leftH = getLeftTotalH(root.left);
int rightH = getRightTotalH(root.right);
if (root.left != null) {
leftH += root.left.height;
}
if (root.right != null) {
rightH += root.right.height;
}
return Math.abs(leftH - rightH);
}
private static int getLeftTotalH(AVLNode root) {
if (root == null) {
return 0;
}
return root.height + getLeftTotalH(root.left);
}
private static int getRightTotalH(AVLNode root) {
if (root == null) {
return 0;
}
return root.height + getRightTotalH(root.right);
}
}
Loading