二叉查找树BST

定义：一个二叉查找树是一颗二叉树，每个节点都含有一个Comparable的键以及关联的值且每个节点的键都大于其左子树的任意节点而小于其右子树的任意节点的键。

树的高度：树中任意节点的最大深度。

时间复杂度：对于一个二叉查找树，其运行的时间取决于树的形状，而树的形状又取决于节点被插入的先后顺序顺序，那么最好情况是，一棵含有N个节点的树完全平衡的，每条空链接和根据点的距离都为log2N（以2为底，N为对数，树的高度和节点总数的关系为 2^x = N,高度也即是节点的查找次数）；那么最坏的情况是全部被添加到一条搜索路径上去了，退化为链表，此时的查询的时间复杂度为0(n)

实现基本的api：get()二叉树查找和put()二叉树插入的实现。（直接使用int类型的key简单实现）

package com.company.tree;


/**
 * 一课二叉树：每个节点都含有一个Comparable的键（以及相关定义的值）且每个节点的键都大于其左子树的任意节点的键而小于右子树所有节点的键
 * api：get() 查找  以及 put() 插入
 */
public class BstTree {

    private Node root;

    /**
     * 查找
     */
    public Object get(int key) {
        return get(root, key);
    }

    public Object get(Node x, int key) {
        //找不到返回null;
        if (x == null) return null;

        if (key < x.key) {
            //左子树查找
            return get(x.left, key);
        } else if (key > x.key) {
            //右子树查找
            return get(x.right, key);
        } else {
            return x.value;
        }
    }

    /**
     * 插入一个节点
     *
     * @param key
     * @param value
     */
    public void put(int key, Object value) {
        root = put(root, key, value);

    }

    public Node put(Node x, int key, Object value) {

        if (x == null) {
            return new Node(key, value, 1);
        }
        if (key < x.key) {
            //放入左子树
            x.left = put(x.left, key, value);
        } else if (key > x.key) {
            //放入右子树
            x.right = put(x.right, key, value);
        } else {
            //相等
            x.value = value;
        }
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }


    /**
     * 获取节点数
     * @return
     */
    private int size() {
        return size(root);
    }

    public int size(Node node) {
        if (node == null) {
            return 0;
        }
        return node.N;
    }


    /**
     * 二叉树遍历
     */

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

    public void print(Node x) {
        if (x == null) return;
        print(x.left);
        System.err.print(x.key + " ");
        print(x.right);
    }


    private static class Node {
        private int key;

        private Object value;

        private Node left, right;

        private int N;//以该节点为根的子树种的节点总数

        public Node(int key, Object value, int n) {
            this.key = key;
            this.value = value;
            N = n;
        }
    }


    public static void main(String[] args) {
        BstTree bstTree = new BstTree();

        bstTree.put(9, "value 9");
        bstTree.put(1, "value 1");
        bstTree.put(0, "value 0");
        bstTree.put(18, "value 18");

        //查找key为18的value
        Object o = bstTree.get(18);
        System.err.println(o);

        //测试顺序打印所有的key
        bstTree.print();
        System.err.println();
    }


}

结构如图：

结构如图 2020-01-12 下午6.30.06.png

测试结果：

测试结果 2020-01-12 下午6.30.20.png