using System;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        Test2();

    }

    public static void Test1()

    {

        AVLTree tree = new AVLTree();

        tree.Add(12);

        tree.Add(17);

        tree.Add(23);

        tree.Add(50); // BST退化成链表, AVL TREE 仍然是二叉链表  https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

        tree.printInorder();

    }

    public static void Test2()

    {

        AVLTree tree = new AVLTree();

        tree.Add(12);

        tree.Add(17);

        tree.Add(23);

        tree.Add(50); // BST退化成链表，self-balance BST 会发生 rotate ，让树高保持最小 

​

        tree.Add(332);

        tree.Add(132);

        tree.Add(81);

        tree.Add(1);

        tree.Add(201);

        tree.Add(43);

        tree.Add(307);

        tree.printInorder();

    }

}

public class Node // 二叉链表的节点

{

    public Node left, right;

    public Object data;

    public int height;

    // 构造函数

    public Node(Object data){

        this.data = data;

        this.left = this.right = null;

        this.height = 1;

    }

}

public class AVLTree

{

    public Node root;

    // const function, won't modify the object

    public void printInorder(){ printInorder(root); }

    public void printInorder(Node n) // printNodes, inOrderDisplayTree

    {

        if (n != null){

            printInorder(n.left);

            Console.Write(n.data + "(h_" + n.height + ")" + " ");

            printInorder(n.right);

        }

    }

    public void Add(Object data){ root = Add(root, data); }

    // insert recursively   https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion 

    public Node Add(Node root, Object data)

    {

        if (root == null){

            root = new Node(data);

            return root;

        }

        if ((int)data < (int)root.data){

            root.left = Add(root.left, data);

        } else if ((int)data > (int)root.data){

            root.right = Add(root.right, data);

        } else {

            // (int)data == (int)root.data

            Console.WriteLine($"invalid data {(int)data}");

            return root;

        }

​

        calHeight(root);

        // return root;

        int balance = getBalance(root);

        // If this node becomes unbalanced, then there

        // are 4 cases

        // https://www.geeksforgeeks.org/avl-tree-set-1-insertion/

        // https://zhuanlan.zhihu.com/p/94130997

        // Left Left Case 第一个图，data 是左下角的红球的值，root 是顶层的球 

        if (balance > 1 && (int)data < (int)root.left.data)

            return rightRotate(root); // not root = rightRotate(root);

        // Right Right Case

        if (balance < -1 && (int)data > (int)root.right.data)

            return leftRotate(root);

​

        // Left Right Case 第三个图，data 是左下角的红球的值，root 是顶层的球 

        if (balance > 1 && (int)data > (int)root.left.data){

            root.left = leftRotate(root.left);

            return rightRotate(root);

        }

        // Right Left Case

        if (balance < -1 && (int)data < (int)root.right.data){

            root.right = rightRotate(root.right);

            return leftRotate(root);

        }

        // return the (unchanged) node pointer 

        return root;

    }

​

    void calHeight(Node n)

    {

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

    }

​

    int max(int a, int b){ return (a > b) ? a : b; }

    int getHeight(Node n){ if (n == null){ return 0; } else { return n.height; } }

​

    // Get Balance factor of node

    int getBalance(Node n){ if (n == null) { return 0;} else { return getHeight(n.left) - getHeight(n.right); } }

​

    // See the diagram given above. https://www.geeksforgeeks.org/avl-tree-set-1-insertion

    Node rightRotate(Node y)

    {

        Node x = y.left;

        Node T2 = x.right;

        // perform rotation

        x.right = y;

        y.left = T2;

        // update height and return new root 

        calHeight(y);

        calHeight(x);

        return x;

    }

    Node leftRotate(Node x)

    {

        Node y = x.right;

        Node T2 = y.left;

        // perform rotation

        y.left = x;

        x.right = T2;

        // update height and return new root 

        calHeight(x);

        calHeight(y);

        return y;

    }

​

}

​

​

​