二叉查找树

转载请注明出处!https://www.jianshu.com/p/89e5b811cf9c

Github源码地址

注:此篇需要链表的构成与数组基础排序相关知识


对于一般的链表或无序数组,灵活性和高效性无法得到很好的统一。于是这里介绍一种能将链表插入的灵活性和有序数组查找的高效性结合起来的符号表实现。

二叉查找树的性能在 logN ~ N 之间

  • 二叉查找树是每个结点都含有两个链接的链表数据结构。

定义:二叉查找树是一颗二叉树,其每个结点都含有一个Comparable(可比较)键。

二叉树结构

每个结点的键都大于任意子节点而小于任意子节点。
二叉树结构

    private class Node {
        private Key key;
        private Value value;
        private Node left, right;
        private int size;

        public Node(Key key, Value value, int size) {
            this.key = key;
            this.value = value;
            this.size = size;
        }
    }

大小 size:

    private int size(Node x) {
        if (x == null) return 0;
        return x.size;
    }

    public int size() {
        return size(root);
    }
  • 假设结点为 x :size(x) = size(x.left) + size(x.right) + 1

查找 get:

设查找的键值为key,根节点为root:

  • 如果树是空的,则查找未命中(null)
  • 如果key == root,则查找命中
  • 如果key < root ,则在root.left中继续查找
  • 如果key > root ,则在root.right中继续查找
    public Value get(Key key) {
        return get(root, key);
    }

    private Value get(Node x, Key key) {
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if (cmp < 0) return get(x.left, key);
        else if (cmp > 0) return get(x.right, key);
        else return x.value;
    }

插入 put:

  • 如果树是空的,就返回一个含有新键值对的新结点
  • 如果key < root ,则继续在左子树进行插入
  • 如果key > root ,则继续在右子树进行插入
    public void put(Key key, Value value) {
        root = 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.left = put(x.left, key, value);
        else if (cmp > 0) x.right = put(x.right, key, value);
        else x.value = value;
        x.size = size(x.left) + size(x.right) + 1;
        return x;
    }

最小值 min:

由于我们二叉树的性质,x.left < x < x.right,故最小值一定是整个树的最左边的子结点。

    public Key min() {
        return min(root).key;
    }

    private Node min(Node x) {
        if (x.left == null) return x;
        return min(x.left);
    }

最大值 max:

理由同上,直接上代码:

    public Key max() {
        return max(root).key;
    }

    private Node max(Node x) {
        if (x.right == null) return x;
        return max(x.right);
    }

删除最小(大)值 deleteMin/deleteMax:

在我们讨论如何删除任意结点前,我们先讨论如何删除最小(大)值。
假设结点为x,以删除最小值为例:

  • 如果x的左子结点存在,则删除即可。
  • 如果x的左子结点不存在,则删除x,此时只剩下x的右子结点返回。
  • 进行删除操作会改变大小,需要更新树的大小。


    删除最小值
    public void deleteMin() {
        root = deleteMin(root);
    }

    private Node deleteMin(Node x) {
        if (x.left == null) return x.right;
        x.left = deleteMin(x.left);
        x.size = size(x.left) + size(x.right) + 1;
        return x;
    }

删除最大值则是将操作对象翻转一下,变为x.right即可:

    public void deleteMax() {
        root = deleteMax(root);
    }

    private Node deleteMax(Node x) {
        if (x.right == null) return x.left;
        x.right = deleteMax(x.right);
        x.size = size(x.left) + size(x.right) + 1;
        return x;
    }

删除 delete:

删除是二叉树中比较复杂的操作之一,主要在于删除会碰到几种情况,这里我们分情况讨论。

  • 如果key < x.key ,则继续在x.left中寻找删除的结点。
  • 如果key > x.key ,则继续在x.right中寻找删除的结点。
  • 如果key == x.key ,则删除当前x的结点。但是,重点来了!!!
  1. x为树的末结点,则直接删除即可。
  2. x不是树的末结点,若直接删除会造成空缺,树不连续,我们需要变换一下。
    (1). 如果x只有一个子结点,则删除x,x的位置用子结点代替即可。
    (2). 如果x含有两个子结点,则我们删除x后,需要寻找x的右子结点中最小的(或者x的左子结点中最大的)来代替x的位置,保证二叉树的性质“每个结点的键都大于任意左子节点而小于任意右子节点”
  • 最后,删除会影响树的大小,需要更新大小。


    删除
    public void delete(Key key) {
        root = delete(root, key);
    }

    private Node delete(Node x, Key key) {
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if (cmp < 0) x.left = delete(x.left, key);
        else if (cmp > 0) x.right = delete(x.right, key);
        else {
            if (x.right == null) return x.left;
            if (x.left == null) return x.right;
            Node t = x;
            x = min(t.right);
            x.left = t.left;
            x.right = delete(t.right, key);
        }
        x.size = size(x.left) + size(x.right) + 1;
        return x;
    }

返回有序的键 keys():

二叉树看起来不像是一个有序线性数列,我们需要稍微换个视角来看。如果把二叉树压扁,从高到低一脚踩扁的那种,则此时二叉树就有那么点像了。(发挥你的想象力)
对于代码里则需要进行中序遍历:

    public Iterable<Key> keys() {
        return keys(min(), max());
    }

    public Iterable<Key> keys(Key lo, Key hi) {
        Queue<Key> queue = new Queue<>();
        keys(root, queue, lo, hi);
        return queue;
    }
    
    private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
        if (x == null) return;
        int cmplo = lo.compareTo(x.key);
        int cmphi = hi.compareTo(x.key);
        if (cmplo < 0) keys(x.left, queue, lo, hi);
        if (cmplo <= 0 && cmphi >= 0) queue.enqueue(x.key);
        if (cmphi > 0) keys(x.right, queue, lo, hi);
    }

返回出来的队列则可以用于进行有序操作,比如遍历等:

    Iterator it = keys().iterator();
    while(it.hasNext()) {
        ...
    }

性能:

  • 在一般情况下,假设我们输入的数据是随机的,随机组成一个二叉树耗时接近O(logN)
    一般情况
  • 在最好的情况下,形成完全对称的二叉树,我们称之为平衡二叉树,此时树的高度h最小,h=logN,此时性能为 O(logN)
    最好情况
  • 在最坏的情况下,形成单边高度h为N的二叉树,此时耗时O(N)
    最差情况
  • 查找、插入、删除操作的耗时均与h正相关,故树的高度直接影响整体的性能。

结束语:

如何维持树的高度 h 始终不超过 logN ,成为提高性能的直接途径。

在我的后续文章中会带来一种自平衡的二叉树——红黑树,在红黑树的所有操作中,不论什么情况,均可以在 logN 的时间内完成战斗,这是多么高效且激动人心的发现!这种伟大的数据结构也被直接用于JAVA底层 Set 和 Map 的实现中!


参考出处:《算法导论》 《Algorithm, 4th Edition》

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,552评论 5 474
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,666评论 2 377
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,519评论 0 334
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,180评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,205评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,344评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,781评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,449评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,635评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,467评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,515评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,217评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,775评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,851评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,084评论 1 258
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,637评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,204评论 2 341

推荐阅读更多精彩内容

  • 数据结构与算法--二叉查找树 上节中学习了基于链表的顺序查找和有序数组的二分查找,其中前者在插入删除时更有优势,而...
    sunhaiyu阅读 1,818评论 0 9
  • 最近在闲看博客时看到一篇专门写红黑树的实现原理,以Java的TreeMap为例讲解,写的很不错,仔细看下来发现很多...
    locoder阅读 3,787评论 0 11
  • 定义: 一棵二叉查找树是一棵二叉树,其中每个结点都含有一个Comparable的键(以及相关联的值)且每个结点的键...
    sleepyjoker阅读 233评论 0 0
  • 生生 你是踽踽独行七年的斑驳树影 我是酉时缄默涣散的流亡日禺 任你绕树根兜转出疮痍满目的年轮 才奉劝自己审视故日已...
    半角花鹿阅读 254评论 0 4
  • 恬静的夜空,闪烁着她的小心思。不时传来的鸟儿声,像是她心底里的话,默默自唱,空空回响。 她也并非全然是清淡,也有浓...
    章魚姬阅读 246评论 0 0