数据结构与算法整理总结---二叉查找树

⼆叉查找树(Binary Search Tree)

⼆叉查找树是⼆叉树中最常⽤的⼀种类型,也叫⼆叉搜索树。顾名思义,⼆叉查找树是为了实现快速查找⽽⽣的。不过,它不仅仅⽀持快速查找⼀个数据,还⽀持快速插⼊、删除⼀个数据。

这些都依赖于⼆叉查找树的特殊结构。⼆叉查找树要求,在树中的任意⼀个节点,其左⼦树中的每个节点的值,都要⼩于这个节点的值,⽽右⼦树节点的值都⼤于这个节点的值。

数据结构与算法整理总结---二叉查找树

1.⼆叉查找树的查找操作

⾸先,我们看如何在⼆叉查找树中查找⼀个节点。我们先取根节点,如果它等于我们要查找的数据,那就返回。如果要查找的数据⽐根节点的值⼩,那就在左⼦树中递归查找;如果要查找的数据⽐根节点的值⼤,那就在右⼦树中递归查找。

数据结构与算法整理总结---二叉查找树

2.⼆叉查找树的插⼊操作

⼆叉查找树的插⼊过程有点类似查找操作。新插⼊的数据⼀般都是在叶⼦节点上,所以我们只需要从根节点开始,依次⽐较要插⼊的数据和节点的⼤⼩关系。

如果要插⼊的数据⽐节点的数据⼤,并且节点的右⼦树为空,就将新数据直接插到右⼦节点的位置;如果不为空,就再递归遍历右⼦树,查找插⼊位置。同理,如果要插⼊的数据⽐节点数值⼩,并且节点的左⼦树为空,就将新数据插⼊到左⼦节点的位置;如果不为空,就再递归遍历左⼦树,查找插⼊位置。

数据结构与算法整理总结---二叉查找树

3.⼆叉查找树的删除操作

⼆叉查找树的查找、插⼊操作都⽐较简单易懂,但是它的删除操作就⽐较复杂了 。针对要删除节点的⼦节点个数的不同,我们需要分三种情况来处理。

第⼀种情况是,如果要删除的节点没有⼦节点,我们只需要直接将⽗节点中,指向要删除节点的指针置为null。⽐如图中的删除节点55。

第⼆种情况是,如果要删除的节点只有⼀个⼦节点(只有左⼦节点或者右⼦节点),我们只需要更新⽗节点中,指向要删除节点的指针,让它指向要删除节点的⼦节点就可以了。⽐如图中的删除节点13。

第三种情况是,如果要删除的节点有两个⼦节点,这就⽐较复杂了。我们需要找到这个节点的右⼦树中的最⼩节点,把它替换到要删除的节点上。然后再删除掉这个最⼩节点,因为最⼩节点肯定没有左⼦节点(如果有左⼦结点,那就不是最⼩节点了),所以,我们可以应⽤上⾯两条规则来删除这个最⼩节点。⽐如图中的删除节点18。

数据结构与算法整理总结---二叉查找树

实际上,关于⼆叉查找树的删除操作,还有个⾮常简单、取巧的⽅法,就是单纯将要删除的节点标记为“已删除”,但是并不真正从树中将这个节点去掉。这样原本删除的节点还需要存储在内存中,⽐较浪费内存空间,但是删除操作就变得简单了很多。⽽且,这种处理⽅法也并没有增加插⼊、查找操作代码实现的难度。

4.⼆叉查找树的其他操作

除了插⼊、删除、查找操作之外,⼆叉查找树中还可以⽀持快速地查找最⼤节点和最⼩节点、前驱节点和后继节点。

⼆叉查找树除了⽀持上⾯⼏个操作之外,还有⼀个重要的特性,就是中序遍历⼆叉查找树,可以输出有序的数据序列,时间复杂度是O(n),⾮常⾼效。因此,⼆叉查找树也叫作⼆叉排序树。

⽀持重复数据的⼆叉查找树

前⾯讲⼆叉查找树的时候,我们默认树中节点存储的都是数字。很多时候,在实际的软件开发中,我们在⼆叉查找树中存储的,是⼀个包含很多字段的对象。我们利⽤对象的某个字段作为键值(key)来构建⼆叉查找树。我们把对象中的其他字段叫作卫星数据。

前⾯我们讲的⼆叉查找树的操作,针对的都是不存在键值相同的情况。那如果存储的两个对象键值相同,这种情况该怎么处理呢?

第⼀种⽅法⽐较容易。⼆叉查找树中每⼀个节点不仅会存储⼀个数据,因此我们通过链表和⽀持动态扩容的数组等数据结构,把值相同的数据都存储在同⼀个节点上。

第⼆种⽅法⽐较不好理解,不过更加优雅。

每个节点仍然只存储⼀个数据。在查找插⼊位置的过程中,如果碰到⼀个节点的值,与要插⼊数据的值相同,我们就将这个要插⼊的数据放到这个节点的右⼦树,也就是说,把这个新插⼊的数据当作⼤于这个节点的值来处理。

数据结构与算法整理总结---二叉查找树

当要查找数据的时候,遇到值相同的节点,我们并不停⽌查找操作,⽽是继续在右⼦树中查找,直到遇到叶⼦节点,才停⽌。这样就可以把键值等于要查找值的所有节点都找出来。

数据结构与算法整理总结---二叉查找树

对于删除操作,我们也需要先查找到每个要删除的节点,然后再按前⾯讲的删除操作的⽅法,依次删除。

数据结构与算法整理总结---二叉查找树

⼆叉查找树的时间复杂度分析

对于⼆叉查找树常⽤操作的实现⽅式,你应该掌握得差不多了。现在,我们来分析⼀下,⼆叉查找树的插⼊、删除、查找操作的时间复杂度。

实际上,⼆叉查找树的形态各式各样。⽐如这个图中,对于同⼀组数据,我们构造了三种⼆叉查找树。它们的查找、插⼊、删除操作的执⾏效率都是不⼀样的。图中第⼀种⼆叉查找树,根节点的左右⼦树极度不平衡,已经退化成了链表,所以查找的时间复杂度就变成了O(n)。

数据结构与算法整理总结---二叉查找树

我刚刚其实分析了⼀种最糟糕的情况,我们现在来分析⼀个最理想的情况,⼆叉查找树是⼀棵完全⼆叉树(或满⼆叉树)。这个时候,插⼊、删除、查找的时间复杂度是多少呢?

从前⾯的例⼦、图,不管操作是插⼊、删除还是查找,时间复杂度其实都跟树的⾼度成正⽐,也就是O(height)。

散列表的插⼊、删除、查找操作的时间复杂度可以做到常量级的O(1),⾮常⾼效。⽽⼆叉查找树在⽐较平衡的情况下,插⼊、删除、查找操作时间复杂度才是O(logn),相对散列表,好像并没有什么优势,那我们为什么还要⽤⼆叉查找树呢?

第⼀,散列表中的数据是⽆序存储的,如果要输出有序的数据,需要先进⾏排序。⽽对于⼆叉查找树来说,我们只需要中序遍历,就可以在O(n)的时间复杂度内,输出有序的数据序列。

第⼆,散列表扩容耗时很多,⽽且当遇到散列冲突时,性能不稳定,尽管⼆叉查找树的性能不稳定,但是在⼯程中,我们最常⽤的平衡⼆叉查找树的性能⾮常稳定,时间复杂度稳定在O(logn)。

第三,笼统地来说,尽管散列表的查找等操作的时间复杂度是常量级的,但因为哈希冲突的存在,这个常量不⼀定⽐logn⼩,所以实际的查找速度可能不⼀定⽐O(logn)快。加上哈希函数的耗时,也不⼀定就⽐平衡⼆叉查找树的效率⾼。

第四,散列表的构造⽐⼆叉查找树要复杂,需要考虑的东⻄很多。⽐如散列函数的设计、冲突解决办法、扩容、缩容等。平衡⼆叉查找树只需要考虑平衡性这⼀个问题,⽽且这个问题的解决⽅案⽐较成熟、固定。

最后,为了避免过多的散列冲突,散列表装载因⼦不能太⼤,特别是基于开放寻址法解决冲突的散列表,不然会浪费⼀定的存储空间。

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!