6-二叉查找树

参考链接

二叉查找树(BST)是二叉树的一个重要的应用,它在二叉树的基础上加上了这样的一个性质:对于树中的每一个节点来说,如果有左儿子的话,它的左儿子的值一定小于它本身的值,如果有右儿子的话,它的右儿子的值一定大于它本身的值。

二叉查找树的操作一般有插入、删除和查找,这几个操作的平均时间复杂度都为O(logn),插入和查找操作很简单,删除操作会复杂一点,除此之外,因为二叉树的中序遍历是一个有序序列,就额外加上了一个中序遍历操作。

二叉查找树的应用不是很多,因为它最坏的时候跟线性表差不多,大部分会应用到它的升级版,平衡二叉树和红黑树,这两棵树都能把时间复杂度稳定在O(logn)左右。虽然不会用到,但是二叉查找树是一定要学好的,毕竟它是平衡二叉树和红黑树的基础。

接下来一步一步写一个二叉查找树模板。

第一步:节点信息

二叉查找树的节点和二叉树的节点大部分是一样的,不同的是,二叉查找树多了一个值出现的次数。如图1显示了二叉查找树的节点信息。


img
extension YYBSTree {
    public class Node {
        public var value: T
        public var left: Node?
        public var right: Node?
        
        public init(value: T) {
            self.value = value
        }
        
        public func unbind() {
            left = nil
            right = nil
        }
        
        public func cleanup() {
            unbind()
        }
    }
}

第二步:二叉查找树类的声明

public struct YYBSTree<T: Comparable> {
    public private(set) var root: Node?
    public private(set) var length = 0
    public var isEmpty: Bool { length == 0 }
}

第三步:插入

根据二叉查找树的性质,插入一个节点的时候,如果根节点为空,就此节点作为根节点,如果根节点不为空,就要先和根节点比较,如果比根节点的值小,就插入到根节点的左子树中,如果比根节点的值大就插入到根节点的右子树中,如此递归下去,找到插入的位置。重复节点的插入用值域中的freq标记。如图2是一个插入的过程。

image

二叉查找树的时间复杂度要看这棵树的形态,如果比较接近一一棵完全二叉树,那么时间复杂度在O(logn)左右,如果遇到如图3这样的二叉树的话,那么时间复杂度就会恢复到线性的O(n)了。

img

平衡二叉树会很好的解决如图3这种情况。

插入函数的代码如下:

mutating func insert(node: Node) {
    node.unbind()
    guard root != nil else {
        root = node
        return
    }

    var tmp = root
    while let cur = tmp {
        if cur.value == node.value {
            return
        } else {
            if node.value < cur.value {
                if cur.left == nil {
                    cur.left = node
                    break
                } else {
                    tmp = cur.left
                }
            } else {
                if cur.right == nil {
                    cur.right = node
                    break
                } else {
                    tmp = cur.right
                }
            }
        }
    }

    length += 1
}

第四步:查找

查找的功能和插入差不多一样,按照插入那样的方式递归下去,如果找到了,就返回这个节点的地址,如果没有找到,就返回nil。

代码如下:

func search(_ value: T) -> Node? {
    var tmp = root
    while let cur = tmp {
        if cur.value == value {
            return cur
        } else {
            if value < cur.value {
                tmp = cur.left
            } else {
                tmp = cur.right
            }
        }
    }

    return nil
}

第五步:删除

删除会麻烦一点,如果是叶子节点的话,直接删除就可以了。如果只有一个孩子的话,就让它的父亲指向它的儿子,然后删除这个节点。图4显示了一棵初始树和4节点被删除后的结果。先用一个临时指针指向4节点,再让4节点的地址指向它的孩子,这个时候2节点的右儿子就变成了3节点,最后删除临时节点指向的空间,也就是4节点。

img

删除有两个儿子的节点会比较复杂一些。一般的删除策略是用其右子树最小的数据代替该节点的数据并递归的删除掉右子树中最小数据的节点。因为右子树中数据最小的节点肯定没有左儿子,所以删除的时候容易一些。图5显示了一棵初始树和2节点被删除后的结果。首先在2节点的右子树中找到最小的节点3,然后把3的数据赋值给2节点,这个时候2节点的数据变为3,然后的工作就是删除右子树中的3节点了,采用递归删除。

img

我们发现对2节点右子树的查找进行了两遍,第一遍找到最小节点并赋值,第二遍删除这个最小的节点,这样的效率并不是很高。能不能写出只查找一次就可以实现赋值和删除两个功能的函数呢?

如果删除的次数不是很多的话,有一种删除的方法会比较快一点,名字叫懒惰删除法:当一个元素要被删除时,它仍留在树中,只是多了一个删除的标记。这种方法的优点是删除那一步的时间开销就可以避免了,如果重新插入删除的节点的话,插入时也避免了分配空间的时间开销。缺点是树的深度会增加,查找的时间复杂度会增加,插入的时间可能会增加。

删除函数代码如下:

@discardableResult
mutating func delete(_ value: T) -> Bool {
    var delete = root
    var parent = root
    while let cur = delete {
        if cur.value == value {
            delete = cur
            break
        } else {
            delete = value < cur.value ? cur.left : cur.right
        }

        parent = cur
    }

    guard delete != nil else {
        return false
    }

    /// 3,不删除,值替换
    if delete?.left != nil, delete?.right != nil {
        parent = delete
        var min = delete?.right
        while min?.left != nil {
            parent = min
            min = min?.left
        }
        /// 用最小节点替换待删除的
        delete?.value = min!.value

        /// 最小节点肯定没有左子树
        /// 转换成删除只有一个节点的情况,parent和delete都变了
        delete = min
    }

    /// 1,2同一种方式处理
    if parent?.left === delete {
        parent?.left = delete?.left ?? delete?.right
    }

    if parent?.right === delete {
        parent?.right = delete?.left ?? delete?.right
    }

    /// 如果最后要删除的是root节点,root调整为左右非空子树
    if delete === root {
        root = parent?.left ?? parent?.right
    }

    delete?.unbind()
    length -= 1

    return true
}

第六步:中序遍历

写这个方法的目的是输出这个二叉查找树的有序序列。代码如下:

func travelInorder(_ node: Node?) {
    guard let node = node else { return }
    travelPreorder(node.left)
    print(node.value)
    travelPreorder(node.right)
}

对于二叉查找树不稳定的时间复杂度的解决方案有不少,平衡二叉树、伸展树和红黑树都可以解决这个问题,但效果是不一样的。

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

推荐阅读更多精彩内容

  • 树的概述 树是一种非常常用的数据结构,树与前面介绍的线性表,栈,队列等线性结构不同,树是一种非线性结构 1.树的定...
    Jack921阅读 4,434评论 1 31
  • 一直以来,我都很少使用也避免使用到树和图,总觉得它们神秘而又复杂,但是树在一些运算和查找中也不可避免的要使用到,那...
    24K男阅读 6,727评论 5 14
  • 基于树实现的数据结构,具有两个核心特征: 逻辑结构:数据元素之间具有层次关系; 数据运算:操作方法具有Log级的平...
    yhthu阅读 4,247评论 1 5
  • 1 序 2016年6月25日夜,帝都,天下着大雨,拖着行李箱和同学在校门口照了最后一张合照,搬离寝室打车去了提前租...
    RichardJieChen阅读 5,074评论 0 12
  • 二叉树 在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”,左子树和右子...
    静默加载阅读 1,929评论 0 3