为什么使用我的AVL树数据结构无法得到正确的中位数?

huangapple 未分类评论46阅读模式
英文:

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

问题

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();
 */
英文:

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:

&#39;&#39;&#39;
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 &lt; num){
            root.right = insert(root.right, num);
        }
        else if(root.data &gt; 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 &gt; 2 &amp;&amp; num &lt; root.left.data){
            return rightRotation(root);
        }
        // left right case
        if(balance &gt; 2 &amp;&amp; num &gt; root.left.data){
            leftRotation(root.left);
            return rightRotation(root);
        }
        // right right case
        if(balance &lt; -1 &amp;&amp; num &gt; root.right.data)
            return leftRotation(root);
        
        // right left case
        if(balance &lt; -1 &amp;&amp; num &lt; 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&gt;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();
 */

&#39;&#39;&#39;

huangapple
  • 本文由 发表于 2020年4月11日 03:55:40
  • 转载请务必保留本文链接:https://java.coder-hub.com/61147755.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定