二叉排序树

一、基本数据结构

public class Node<T extends Comparable<T>>{
    private T value;
    private int height;
    private Node<T> left;
    private Node<T> right;
    public Node(T value) {
        this.value = value;
        this.height = 1;
        this.left = null;
        this.right = null;
    }
    public T getValue() {
        return value;
    }
    public void setValue(T value) {
        this.value = value;
    }
    public int getHeight() {
        return height;
    }
    public void setHeight(int height) {
        this.height = height;
    }
    public Node<T> getLeft() {
        return left;
    }
    public void setLeft(Node<T> left) {
        this.left = left;
    }
    public Node<T> getRight() {
        return right;
    }
    public void setRight(Node<T> right) {
        this.right = right;
    }
    @Override
    public String toString() {
        // TODO Auto-generated method stub
        return this.value.toString();
    }
}

工具类函数

    public static <T extends Comparable<T>> Node<T> maximumNode(Node<T> root) {
        //求左子树最大值的前驱节点
        if(root == null) {
            return null;
        }
        Node<T> prev = root;
        Node<T> post = null;
        while(prev.getRight()!=null) {
            post = prev;
            prev = prev.getRight();
        }
        return post;
    }
    public static <T extends Comparable<T>> Node<T> minimumNode(Node<T> root) {
        //求右子树最小值的前驱节点
        if(root == null) {
            return null;
        }
        Node<T> prev = root;
        Node<T> post = null;
        while(prev.getLeft()!=null) {
            post = prev;
            prev = prev.getLeft();
        }
        return post;
    }
    public static <T extends Comparable<T>> T maximum(Node<T> root) {
        //求左子树最大值
        if(root == null) {
            return null;
        }
        Node<T> prev = root;
        Node<T> post = null;
        while(prev.getRight()!=null) {
            post = prev;
            prev = prev.getRight();
        }
        return prev.getValue();
    }
    public static <T extends Comparable<T>> T minimum(Node<T> root) {
        //求右子树最小值
        if(root == null) {
            return null;
        }
        Node<T> prev = root;
        Node<T> post = null;
        while(prev.getLeft()!=null) {
            post = prev;
            prev = prev.getLeft();
        }
        return prev.getValue();
    }
    public static <T extends Comparable<T>> int height(Node<T> node) {
        //求高度
        if(node == null) {
            return 0;
        }else {
            return node.getHeight();
        }
    }
    public static <T extends Comparable<T>> int maxHeight(Node<T> n1, Node<T> n2) {
        //求最大高度
        return height(n1)>height(n2)?height(n1):height(n2);
    }
    public static <T extends Comparable<T>> Node<T> rightRightRotation(Node<T> root){
        //左旋操作
        Node<T> node = root.getRight();
        root.setRight(node.getLeft());
        node.setLeft(root);
        root.setHeight(maxHeight(root.getLeft(),root.getRight())+1);
        node.setHeight(maxHeight(node.getLeft(),node.getRight())+1);
        return node;
    }
    public static <T extends Comparable<T>> Node<T> leftLeftRotation(Node<T> root){
        //右旋操作
        Node<T> node = root.getLeft();
        root.setLeft(node.getRight());
        node.setRight(root);
        root.setHeight(maxHeight(root.getLeft(),root.getRight())+1);
        node.setHeight(maxHeight(node.getLeft(),node.getRight())+1);
        return node;
    }
    public static <T extends Comparable<T>> Node<T> rightLeftRotation(Node<T> root){
        //先右旋再左旋
        root.setRight(leftLeftRotation(root.getRight()));
        return rightRightRotation(root);
    }
    public static <T extends Comparable<T>> Node<T> leftRightRotation(Node<T> root){
        //先左旋再右旋
        root.setLeft(rightRightRotation(root.getLeft()));
        return leftLeftRotation(root);
    }

二、普通二叉排序树

1、二叉排序树的insert（非递归）

    public static <T extends Comparable<T>> Node<T> insert(Node<T> root, T value){
        Node<T> node = new Node<T>(value);
        if(root == null) {
            return node;
        }
        int temp = 0;
        Node<T> prev = root;
        while(prev!=null) {
            temp = prev.getValue().compareTo(value);
            if(temp == 0) {
                return root;
            }else if(temp == 1) {
                if(prev.getLeft()==null) {
                    prev.setLeft(node);
                }
                prev = prev.getLeft();
            }else {
                if(prev.getRight()==null) {
                    prev.setRight(node);
                }
                prev = prev.getRight();
            }
        }
        return root;
    }

2、二叉排序树的insert（递归）

public static <T extends Comparable<T>> Node<T> insert(Node<T> root, T value){
        if(root == null) {
            Node<T> node = new Node<T>(value);
            return node;
        }
        int temp = root.getValue().compareTo(value);
        if(temp == 0) {
            return root;
        }else if(temp == 1) {
            root.setLeft(insert(root.getLeft(), value));
        }else {
            root.setRight(insert(root.getRight(), value));
        }
        return root;
    }

3、二叉排序树的insert(包含有height)

    public static <T extends Comparable<T>> Node<T> insert(Node<T> root, T value){
        if(root == null) {
            Node<T> node = new Node<T>(value);
            return node;
        }
        int temp = root.getValue().compareTo(value);
        if(temp == 0) {
            return root;
        }else if(temp == 1) {
            root.setLeft(insert(root.getLeft(),value));
            root.setHeight(maxHeight(root.getLeft(), root.getRight())+1);
        }else {
            root.setRight(insert(root.getRight(),value));
            root.setHeight(maxHeight(root.getLeft(), root.getRight())+1);
        }
        return root;
    }

4、二叉排序树的删除(递归)

    public static <T extends Comparable<T>> Node<T> delete(Node<T> root, T value){
        if(root == null) {
            return null;
        }
        int temp = root.getValue().compareTo(value);
        if(temp == 0) {//这里取的是root左子树最右边的节点（即最大的节点）；也可以取root右子树最左边的节点（即最小的节点）
            if(root.getLeft()==null||root.getRight()==null) {
                return root.getLeft()==null?root.getRight():root.getLeft();
            }else {
                Node<T> left = root.getLeft();
                Node<T> post = maximumNode(left);
                if(post == null) {
                    root.setValue(left.getValue());
                    root.setLeft(left.getLeft());
                }else {
                    root.setValue(post.getRight().getValue());
                    post.setRight(post.getRight().getLeft());
                }
            }
        }else if(temp == 1) {
            root.setLeft(delete(root.getLeft(), value));
        }else {
            root.setRight(delete(root.getRight(), value));
        }
        return root;
    }

三、AVL树(AVL树的根节点会随着insert和delete操作而改变，这一点测试的时候要注意，要随时更新根节点)

1、AVL树的insert操作

    public static <T extends Comparable<T>> Node<T> insertAvl(Node<T> root, T value){
        if(root == null) {
            Node<T> node = new Node<T>(value);
            return node;
        }
        int temp = root.getValue().compareTo(value);
        if(temp == 0) {
            return root;
        }else if(temp == 1) {
            root.setLeft(insertAvl(root.getLeft(),value));
            if(height(root.getLeft())-height(root.getRight())==2) {
                Node<T> node = root.getLeft();
                if(height(node.getRight())>height(node.getLeft())) {
                    root = leftRightRotation(root);
                }else {
                    root = leftLeftRotation(root);
                }
            }
            
        }else {
            root.setRight(insertAvl(root.getRight(),value));
            if(height(root.getRight())-height(root.getLeft())==2) {
                Node<T> node = root.getRight();
                if(height(node.getLeft())>height(node.getRight())) {
                    root = rightLeftRotation(root);
                }else {
                    root = rightRightRotation(root);
                }
            }
        }
        root.setHeight(maxHeight(root.getLeft(), root.getRight())+1);
        return root;
    }

2、AVL树的delete操作

    public static <T extends Comparable<T>> Node<T> avlDelete(Node<T> root, T value){
        if(root == null) {
            return null;
        }
        int temp = root.getValue().compareTo(value);
        if(temp == 0) {//这里取的是root左子树最右边的节点（即最大的节点）；也可以取root右子树最左边的节点（即最小的节点）
            if(root.getLeft()==null||root.getRight()==null) {
                return root.getLeft()==null?root.getRight():root.getLeft();
            }else {
                if(height(root.getLeft())>height(root.getRight())) {
                    Node<T> left = root.getLeft();
                    T max = maximum(left);
                    root.setValue(max);
                    root.setLeft(avlDelete(root.getLeft(), max));
                }else {
                    Node<T> right = root.getRight();
                    T min = minimum(right);
                    root.setValue(min);
                    root.setRight(avlDelete(root.getRight(), min));
                }
            }
        }else if(temp == 1) {
            root.setLeft(avlDelete(root.getLeft(), value));
            if(height(root.getRight())-height(root.getLeft())==2) {
                Node<T> node = root.getRight();
                if(height(node.getLeft())>height(node.getRight())) {
                    root = rightLeftRotation(root);
                }else {
                    root = rightRightRotation(root);
                }
            }
        }else {
            root.setRight(avlDelete(root.getRight(), value));
            if(height(root.getLeft())-height(root.getRight())==2) {
                Node<T> node = root.getLeft();
                if(height(node.getRight())>height(node.getLeft())) {
                    root = leftRightRotation(root);
                }else {
                    root = leftLeftRotation(root);
                }
            }
        }
        root.setHeight(maxHeight(root.getLeft(), root.getRight())+1);
        return root;
    }

参考文献

AVL树漫画：http://www.sohu.com/a/270452030_478315

AVL树代码：https://www.cnblogs.com/skywang12345/p/3577479.html