I have been recently learning about trees and came across AVL trees. I referred Kunal Kushwaha from YouTube in learning these concepts. I have implemented the AVL tree in the code below i am pasting my full AVL java class
The problem is when I try to add 1000 elements(values) into the tree via the Main method, the height is supposed to be 3 because the height is log(n) -> log (1000) -> 3 but I am getting 12 as output instead of 3 but in Kunal’s video the code he implemented produced 3 whereas me who nearly implemented the same code gets a different output. I have spent 2hours in figuring out where is the mistake made but couldn’t find any mistake. I even referred ChatGPT but i was useless. Your help in finding out the mistake would be much appreciated.
I am posting 2 of the codes below
- My code:
public class AVL_Trees {
//i dont know why code when i insert 1000 elements
//expected height is 3 but i get 12 i tried via ChatGPT and cross checked my self but still can't find the solution on where the error is
//post on reddit or stackoverflow
private class Node{
private int value;
private Node left;
private Node right;
private int height;
public Node(int value){
this.value = value;
}
public int getValue() {
return value;
}
}
private Node root;
public AVL_Trees(){} //constructor
public int height() {
return height(root);
}
public int height(Node node) { //helper function
if (node == null) {
return -1;
}
return node.height;
}
public boolean isEmpty(Node node){
return node == null;
}
public void prettyDisplay(){
prettyDisplay(root,0);
System.out.println("Height "+height(root));
}
private void prettyDisplay(Node node,int level){
if(node == null){
return;
}
prettyDisplay(node.right,level+1);
if(level!=0){
for(int i=0;i<level;i++){
System.out.print("|tt");
}
System.out.println("|--->" + node.value);
}
else {
System.out.println("|--->" + node.value);
}
prettyDisplay(node.left,level+1);
}
public void insert(int value){
root = insert(root,value);
}
private Node insert(Node node, int value){
if(node==null){
return new Node(value);
}
if(value < node.value){
node.left = insert(node.left,value);
}
if(value > node.value){
node.right = insert(node.right,value);
}
node.height = Math.max(height(node.left),height(node.right)) + 1;
return rotate(node);
}
//for arrays as input
public void populate(int[] nums){
for(int i : nums){
insert(i);
}
}
public void populateSorted(int[] nums){ //incase if input array is sorted
populateSorted(nums,0, nums.length);
}
private void populateSorted(int[] nums,int start,int end){
if(start>=end){
return;
}
int mid = start + (end - start)/2;
insert(nums[mid]);
populateSorted(nums,0,mid);
populateSorted(nums,mid+1,end);
}
public boolean balanced(){
return balanced(this.root);
}
private boolean balanced(Node node){
if(node == null){
return true;
}
// condition for balance is both child node's height difference
//should be less than or equal to 1
return Math.abs(height(node.left) - height(node.right)) <=1 && balanced(node.left) && balanced(node.right);
}
public void display(){
display(root,"The root Node is ");
}
private void display(Node node , String details){ //just a way of representing
if(node == null){
return;
}
System.out.println(details + node.value);
display(node.left,"The left node of "+node.value+" is: ");
display(node.right,"The right node of "+node.value+" is: ");
}
private Node rotate(Node node){
if(height(node.left) - height(node.right) > 1){
//left heavy
if(height(node.left.left) - height(node.left.right) > 0 ){
//put 0, not 1 or -1 think about it!
//left-left case
return rightRotate(node);
}
if(height(node.left.left) - height(node.left.right) < 0){
//left-right case
node.left = leftRotate(node.left);
return rightRotate(node);
}
}
if(height(node.left) - height(node.right) < -1){
//right heavy
if(height(node.right.left) - height(node.right.right) < 0){
//right-right case
return leftRotate(node);
}
if(height(node.right.left) - height(node.right.right) > 0){
//right-left case
node.right = rightRotate(node.right);
return leftRotate(node);
}
}
return node;
}
private Node rightRotate(Node p){
Node c = p.left;
Node t = c.right;
c.right = p;
p.left = t;
//updating heights
p.height = Math.max(height(p.left),height(p.right))+1;
c.height = Math.max(height(c.left),height(c.right))+1;
return c;
}
private Node leftRotate(Node c){
Node p = c.right;
Node t = p.left;
p.left = c;
c.right = t;
//updating heights
p.height = Math.max(height(p.left),height(p.right))+1;
c.height = Math.max(height(c.left),height(c.right))+1;
return p;
}
}
2.Kunal’s correct code:
//this is the correct code for AVL tree where it can balance and height is 3 when adding 1000 elements
public class KunalAVL {
public class Node {
private int value;
private Node left;
private Node right;
private int height;
public Node(int value) {
this.value = value;
}
public int getValue() {
return value;
}
}
private Node root;
public KunalAVL() {
}
public int height() {
return height(root);
}
private int height(Node node) {
if (node == null) {
return -1;
}
return node.height;
}
public void insert(int value) {
root = insert(value, root);
}
private Node insert(int value, Node node) {
if (node == null) {
node = new Node(value);
return node;
}
if (value < node.value) {
node.left = insert(value, node.left);
}
if (value > node.value) {
node.right = insert(value, node.right);
}
node.height = Math.max(height(node.left), height(node.right)) + 1;
return rotate(node);
}
private Node rotate(Node node) {
if (height(node.left) - height(node.right) > 1) {
// left heavy
if(height(node.left.left) - height(node.left.right) > 0) {
// left left case
return rightRotate(node);
}
if(height(node.left.left) - height(node.left.right) < 0) {
// left right case
node.left = leftRotate(node.left);
return rightRotate(node);
}
}
if (height(node.left) - height(node.right) < -1) {
// right heavy
if(height(node.right.left) - height(node.right.right) < 0) {
// right right case
return leftRotate(node);
}
if(height(node.right.left) - height(node.right.right) > 0) {
// left right case
node.right = rightRotate(node.right);
return leftRotate(node);
}
}
return node;
}
public Node rightRotate(Node p) {
Node c = p.left;
Node t = c.right;
c.right = p;
p.left = t;
p.height = Math.max(height(p.left), height(p.right) + 1);
c.height = Math.max(height(c.left), height(c.right) + 1);
return c;
}
public Node leftRotate(Node c) {
Node p = c.right;
Node t = p.left;
p.left = c;
c.right = t;
p.height = Math.max(height(p.left), height(p.right) + 1);
c.height = Math.max(height(c.left), height(c.right) + 1);
return p;
}
public void populate(int[] nums) {
for (int i = 0; i < nums.length; i++) {
this.insert(nums[i]);
}
}
public void populatedSorted(int[] nums) {
populatedSorted(nums, 0, nums.length);
}
private void populatedSorted(int[] nums, int start, int end) {
if (start >= end) {
return;
}
int mid = (start + end) / 2;
this.insert(nums[mid]);
populatedSorted(nums, start, mid);
populatedSorted(nums, mid + 1, end);
}
public void display() {
display(this.root, "Root Node: ");
}
private void display(Node node, String details) {
if (node == null) {
return;
}
System.out.println(details + node.value);
display(node.left, "Left child of " + node.value + " : ");
display(node.right, "Right child of " + node.value + " : ");
}
public boolean isEmpty() {
return root == null;
}
public boolean balanced() {
return balanced(root);
}
private boolean balanced(Node node) {
if (node == null) {
return true;
}
return Math.abs(height(node.left) - height(node.right)) <= 1 && balanced(node.left) && balanced(node.right);
}
}
New contributor
Ajay Sai Ram is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.