二叉排序树

二叉排序树，二叉查找树

• 若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
• 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
• 左、右子树也分别为二叉排序树；

public class Node {

    int value;
    Node left;
    Node right;

    public Node(int value){
        this.value= value;
    }

    /**
     * 向子树中添加节点
     */
    public void add(Node node){
        if(node==null){
            return;
        }
        //判断传入的节点的值比当前子树的根及诶单的值大还是小
        //添加的节点比当前节点的值更小
        if(node.value<this.value){
            //如果左节点为空
            if(this.left==null){
                this.left=node;
            }else{
                this.left.add(node);
            }
        }else{
            //如果右节点为空
            if(this.right==null){
                this.right=node;
            }else{
                this.right.add(node);
            }
        }
    }

    /**
     * 查找节点
     */
    public Node search(int value){
        if(this.value==value){
            return this;
        }else if(value<this.value){
            if(left==null){
                return null;
            }
            return left.search(value);
        }else{
            if(right==null){
                return null;
            }
            return right.search(value);
        }
    }

    /**
     * 搜索父节点
     */
    public Node searchParent(int value){
        if((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)){
            return this;
        }else{
            if(this.value>value&&this.left!=null){
                return this.left.searchParent(value);
            }else if(this.value<value&&this.right!=null){
                return this.right.searchParent(value);
            }
            return null;
        }
    }
}

public class BinarySortTree {

    Node root;

    /**'
     * 向二叉排序树中添加节点
     * @Param node
     */
    public void add(Node node){
        //如果是一棵空树
        if(root==null){
            root = node;
        }else{
            root.add(node);
        }
    }

    /**
     * 查找节点
     */
    public Node search(int value){
        Node result = root.search(value);
        return result;
    }

    /**
     * 删除节点
     */
    public void delete(int value){
        if(root==null){
            return;
        }else{
            //找到这个节点
            Node target = search(value);
            //如果没有这个节点
            if(target==null){
                return;
            }
            //找到他的父节点
            Node parent = searchParent(value);
            //要删除的节点是叶子节点
            if(target.left==null&&target.right==null){
                //要删除的节点是父节点的左子节点
                if(parent.left.value==value){
                    parent.left=null;
                }else{
                    parent.right=null;
                }
            //要删除的节点有两个子节点的情况
            }else if(target.left!=null&&target.right!=null){
                //删除右子树中值最小的节点，取获取到该节点的值
                int min = deleteMin(target.right);
                //替换目标节点中的值
                target.value=min;

            //要删除的节点有一个左子节点或右子节点
            }else{
                //有左子节点
                if(target.left!=null){
                    //要删除的节点是父节点的左子节点
                    if(parent.left.value==value){
                        parent.left=target.left;
                    }else{
                        //要删除的节点是父节点的左子节点
                        parent.right=target.left;
                    }
                //有右子节点
                }else{
                    //要删除的节点是父节点的左子节点
                    if(parent.left.value==value){
                        parent.left=target.right;
                    }else{
                        //要删除的节点是父节点的左子节点
                        parent.right=target.right;
                    }
                }
            }

        }
    }

    /**
     * 删除一棵树中最小的节点
     * @param right
     * @return
     */
    private int deleteMin(Node node) {
        Node target = node;
        //递归向左找
        while(target.left!=null){
            target = target.left;
        }
        //删除最小的这个节点
        delete(target.value);
        return target.value;
    }

    /**
     * 搜索父节点
     */
    public Node searchParent(int value){
        if(root==null){
            return null;
        }else{
            return root.searchParent(value);
        }
    }

}

平衡二叉树（AVL树）

任何 左子树和右子树的高度差的绝对值不超过1

B树中所有的叶节点都在同一层

2-3树

有两个子节点的节点叫二节点 二节点要么有两个子节点，要么没有子节点

B+树

非叶节点只存储索引信息，不存储数据
叶子节点最右边的指针指向下一个相邻的叶节点
所有的叶节点组成了一个有序链表