3.2 二叉查找树

各种符号表预览

使用的数据结构 实现 优点 缺点
链表(顺序查找) SequenceSearchST 适用于小型数组 大型数组慢
有序数组(二分查找) BinarySearchST 最优的查找效率 插入比较慢
二叉查找树 BST 实现简单,能进行有序性相关操作 没有性能上界,链接需要额外空间
平衡二叉查找树 RedBlackBST 最优的查找和插入效率,能进行有序性相关操作 链接需要额外的空间
散列表 SeparateChainHashST LinearProbingHashST 能快速的查找和插入常见类型的数据 需要计算每种类型的hashcode,无法有序,链接和空节点需要额外空间
定义:

一颗二叉查找数(BST)是一棵二叉树,每个节点都有一个Comparable键(以及相关的键值),每一个结点的键都大于其左子树任意结点的键值,小于其右子树任意结点的键值.


image.png

3.2.1数据表示

每个结点都会有一个 :键,一个值,一个左链接,一个右链接,一个结点计数器 .size(x)=size(x.left)+size(x.right)+1 ;// 表示结点计数器,从下面到这个结点一共有几个结点.

同一个集合可以用不同的二叉查找树表示.

例如下图3.2.3.
image.png

代码如下 :

package algorithm.sortAlgorithm.search;
/**
 * Created by leon on 18-1-28.
 * 查找二叉树
 */
public class BST<Key extends Comparable<Key>, Value> {
    private Node root;
    private class Node {
        private Node left;
        private Node right;
        private Value value;
        private Key key;
        private int N;//当前的结点数
        public Node(Key key, Value value, int N) {
            this.key = key;
            this.value = value;
            this.N = N;
        }
    }
    public int size() {
        return size(root);
    }
    private int size(Node node) {
        if (node == null) {
            return 0;
        }
        return node.N;
    }
    public void put(Key key, Value value) {
        put(root, key, value);
    }
    private Node put(Node x, Key key, Value value) {
        //这里是到了叶子了.
        if (x == null) {
            return new Node(key, value, 1);
        }
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            x.right = put(x.right, key, value);
        } else if (cmp < 0) {
            x.left = put(x.left, key, value);
        } else {
            put(x, key, value);
        }
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }
    public Value get(Key key) {
        return get(root, key);
    }
    private Value get(Node node, Key key) {
        if (node == null) {
            return null;
        }
        int cmp = key.compareTo(node.key);
        if (cmp > 0) {
            return get(node.right, key);
        } else if (cmp < 0) {
            return get(node.left, key);
        } else {
            return node.value;
        }
    }
}

分析:
二叉查找树的最好的情况是 ,一颗含有N结点的完全平衡树,查找的时间为~lgN,而最坏的情况是搜索路径上有N个结点,查找的时间复杂度为N.但是一般情况下实际和最好情况接近.
二叉查找树和快速排序几乎是双胞胎.因为树的根节点就是树中第一个切分点,得到一下性质:

命题C:

在由N个结点构造的二叉查找树中,查找命中所需要的平均时间为~2lnN 约1.39lgN.

命题D:

在由N个结点构成的二叉查找树中,插入操作和查找未命中平均需要时间为~2lnN 约1.39lgN

3.2.3 有序性相关方法与删除操作:

删除最大键和最小键,这是二叉查找树中最难实现的部分.
删除最小键 :deleteMin().先遍历左子树节点,直到遇到一个左节点是空的.把指向当前节点链接指向其右子树,删除当前的节点.
如何删除拥有两个子结点的结点呢?
在删除结点x后,用x的右子树的后继结点(最左结点)填补它的位置.

image.png
image.png

二叉查找树代码:

package algorithm.sortAlgorithm.search;
/**
 * Created by leon on 18-1-28.
 * 二叉树查找
 */
public class BST<Key extends Comparable<Key>, Value> {
    private Node root;
    private class Node {
        private Node left;
        private Node right;
        private Value value;
        private Key key;
        private int N;//当前的结点数
        public Node(Key key, Value value, int N) {
            this.key = key;
            this.value = value;
            this.N = N;
        }
    }
    public int size() {
        return size(root);
    }
    private int size(Node node) {
        if (node == null) {
            return 0;
        }
        return node.N;
    }
    public void put(Key key, Value value) {
        put(root, key, value);
    }
    private Node put(Node x, Key key, Value value) {
        //这里是到了叶子了.
        if (x == null) {
            return new Node(key, value, 1);
        }
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            x.right = put(x.right, key, value);
        } else if (cmp < 0) {
            x.left = put(x.left, key, value);
        } else {
            put(x, key, value);
        }
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }
    public Value get(Key key) {
        return get(root, key);
    }
    private Value get(Node node, Key key) {
        if (node == null) {
            return null;
        }
        int cmp = key.compareTo(node.key);
        if (cmp > 0) {
            return get(node.right, key);
        } else if (cmp < 0) {
            return get(node.left, key);
        } else {
            return node.value;
        }
    }
    public void deleteMin() {
        root = deleteMin(root);
    }
    /**
     * 递归x.left ,直到 node 没有左结点 ,还是返回当前的树
     *
     * @param x
     * @return 最终返回替换被删除的结点的 链
     */
    private Node deleteMin(Node x) {
        if (x.left == null) {
            return x.right;
        } else {
            x.left = deleteMin(x.left);
            x.N = size(x.left) + size(x.right) + 1;
            return x;
        }
    }
    public void delete(Key key) {
        root = delete(root, key);
    }
    private Node delete(Node x, Key key) {
        if (x == null) {
            return null;
        }
        //接下来 左,右结点都存在,需要比较下,这个key 在左右那个子节点下
        int cmp = key.compareTo(x.key);
        //right
        if (cmp > 0) {
            //遍历右子树,删除
            x.right = delete(x.right, key);
        } else if (cmp < 0) {
            x.left = delete(x.left, key);
        } else {
            //就是当前的结点 需要删除.
            if (x.left == null) {
                return x.right;
            } else if (x.right == null) {
                return x.left;
            } else {
                Node t = x;
                x = min(t.right);
                x.right = deleteMin(t.right);
                x.left = t.left;
            }
        }
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }
    private Node min(Node x) {
        if (x.left == null) {
            return x;
        } else {
            return min(x.left);
        }
    }
}
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 204,053评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,527评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,779评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,685评论 1 276
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,699评论 5 366
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,609评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,989评论 3 396
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,654评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,890评论 1 298
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,634评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,716评论 1 330
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,394评论 4 319
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,976评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,950评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,191评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 44,849评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,458评论 2 342

推荐阅读更多精彩内容