• Skip to main content
  • Skip to primary sidebar
  • Skip to footer
  • About
  • Life
  • Tech
  • Travel
  • Work
  • Questions
  • Contact

Welcome

.

Why the correct median is not obtained using my AVL tree data structure?

April 10, 2020 by

Questions › Why the correct median is not obtained using my AVL tree data structure?
0
Vote Up
Vote Down
Garmaine asked 4 years ago

The question is to obtain median of given elements. If odd then simply return the middle element else return the mean of the n/2 and n/2 + 1 element.

The problem is that it is always returning 1 as the median, which probably means that rotation is not happening as 1 was my first input.

I know it is a famous leet code question, but i have written all my code by myself and there is no one else in the discussion panel whose code is written on avl tree from scratch. Code:

'''
class Node{
    int data;
    Node left, right;
    int height;
    Node(int d){
        this.data = d;
        this.left = this.right = null;
        this.height = 1;
    }
    Node(){
        this.left = this.right = null;
    }
}

class MedianFinder {
    static Node root;
    MedianFinder(){
        root = new Node();
    }
    public void addNum(int num) {

        insert(root, num);
    }


    public static Node insert(Node root, int num){
        if(root == null)
            return (new Node(num));

        if(root.data < num){
            root.right = insert(root.right, num);
        }
        else if(root.data > num)
            root.left = insert(root.left, num);


        root.height = max(height(root.left) , height(root.right)) + 1;

        int balance = get_balance(root);
        // if left left
        if(balance > 2 && num < root.left.data){
            return rightRotation(root);
        }
        // left right case
        if(balance > 2 && num > root.left.data){
            leftRotation(root.left);
            return rightRotation(root);
        }
        // right right case
        if(balance < -1 && num > root.right.data)
            return leftRotation(root);

        // right left case
        if(balance < -1 && num < root.right.data){
            rightRotation(root.right);
            return leftRotation(root);
        }
        return root;

    }

    public static Node rightRotation(Node node){
        Node temp = node.left;
        Node tempright = temp.right;
        temp.right = node;
        node.left = tempright;

        node.height = max(height(node.left), height(node.right)) + 1;
        temp.height = max(height(temp.left), height(temp.right)) + 1;

        return temp;
    }

    public static Node leftRotation(Node node){
        Node temp = node.right;
        Node templeft = temp.left;
        temp.left = node;
        node.right = templeft;

        node.height = max(height(node.left), height(node.right)) + 1;
        temp.height = max(height(temp.left), height(temp.right)) + 1;

        return temp;
    }

    public static int get_balance(Node node){
        if(node == null)
            return 0;
        return height(node.left) - height(node.right);
    }

    public static int height(Node node){
        if(node == null)
            return 0;
        return node.height;
    }
    public static int max(int a, int b){
        return a>b?a:b;
    }

    public double findMedian() {

        if(height(root.left) == height(root.right))
            return root.data;
        return (root.data + root.right.data) / 2;

    }

    public static int count(Node node){
        if(node == null)
            return 0;
        return 1 + count(node.left) + count(node.right);
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

'''
Are you looking for the answer?
Original Question and Possible Answers can be found on `http://stackoverflow.com`

Question Tags: avl-tree, java, tree

Please login or Register to submit your answer




Primary Sidebar

Tags

Advancements best Business strategies commercial convenience economic Finances Cognitive decline Financial growth firm Future Hidden Gems Home hydration Impact Innovations lighting line of work Mental health Must-See New York City office patronage Productivity profession Profitability tips Profit optimization pursuit recreation Revenue enhancement romance sippy cups social station Technological breakthroughs technology toddlers trading transaction Treasures Uncover undertaking Well-being Wonders Work Young onset dementia

Newsletter

Complete the form below, and we'll send you all the latest news.

Footer

Footer Funnies

Who knew that reading the footer could be such a hilarious adventure? As we navigate websites, books, and documents, we often stumble upon the unassuming space at the bottom, only to discover a treasure trove of amusement. In this side-splitting compilation, we present 100 jokes that celebrate the unsung hero of content – the footer. Get ready to chuckle, giggle, and maybe even snort as we dive into the world of footnotes, disclaimers, and hidden comedic gems. Brace yourself for a wild ride through the footer!

Recent

  • Unveiling the Enigma: Almost-Magical Lamp Lights Highway Turns
  • The Impact of Young Onset Dementia on Employment and Finances: Optimizing Post-Diagnostic Approaches
  • 11 Wonders of 2023 Technological Breakthrough – Unveiling the Future
  • Work from Home and Stay Mentally Sane – Achieve Productivity and Well-being
  • Hidden Gems of New York City – Uncover the Must-See Treasures!

Search

Tags

Advancements best Business strategies commercial convenience economic Finances Cognitive decline Financial growth firm Future Hidden Gems Home hydration Impact Innovations lighting line of work Mental health Must-See New York City office patronage Productivity profession Profitability tips Profit optimization pursuit recreation Revenue enhancement romance sippy cups social station Technological breakthroughs technology toddlers trading transaction Treasures Uncover undertaking Well-being Wonders Work Young onset dementia

Copyright © 2023