二叉树基础(下)

Sunday, May 5, 2019

二叉查找树

二叉查找树最大的特点就是支持动态数据集合的快速插入,删除,查找操作。

二叉查找树是为了实现快速查找而生的,不仅仅支持快速查找数据,还支持快速插入,删除一个数据。

二叉查找树要求在树中的任意一个节点,左子树的每个节点的值,都要小于这个节点的值,而右子树节点的值都大于这个节点的值。

file

二叉查找树的查找操作

从根节点开始查找,如果相等,就返回,如果比根节点小,就去左子树递归查找,否则就去右子树递归查找。

file

二叉查找树的插入操作

从根节点开始,如果插入的数据比节点的数据大,并且节点的右子树为空,则插入到右子节点的位置,如果不为空,就再递归遍历右子树,查找插入位置。反之同理。

file

二叉查找树的删除操作

三种情况

  • 如果删除的节点没有子节点,只需将父节点指向要删除的节点为null。
  • 如果删除的节点只有一个子节点,我们需要更新父节点中,指向要删除节点的指针,让它指向要删除的节点的子节点就可以了。
  • 如果有两个子节点,我们需要找到这个节点的右子树中的最小节点,把它替换到要删除的节点上。然后再删除这个最小节点。

file

还有一个非常简单的方法,就是单纯将要删除的节点标记为已删除,这样比较浪费内存空间,但是删除操作变得简单很多。

二叉查找树的其他操作

用中序遍历二叉查找树,可以输出有序的数据序列,时间复杂度是O(n),非常高效。

支持重复数据的二叉查找树

两种方法

二叉查找树的每一个节点不仅会存储一个数据,因此我们通过链表和支持动态扩容的数组等数据结构,把值相同的数据存储在同一个节点上。

每个节点只存储一个数据。在查找插入位置的过程中,如果遇到相同,就将要插入的数据放到右子树。也就是说当作大于这个节点的值来处理。

file

当查找时,遇到相同的点,不停止查找,继续在右子树查找,直到遇到叶子结点才停止。

file

对于删除操作也是如此。

file

从上面的过程来看,无论是插入,删除,查找,时间复杂度都跟高度成正比,也就是O(height)。平衡二叉查找树的时间复杂度度是O(logn)

散列表很高效,为什么要用二叉查找树

散列表中的数据是无序存储的,如果要输出有序的数据,要先进行排序。对于二叉查找树,只需要使用中序遍历,就可以在O(n)时间复杂度输出有序序列。

散列表扩容耗时很多,遇到散列冲突时,性能不稳定,常用的平衡二叉树的性能非常稳定,时间复杂度在O(logn)

尽管散列表的查找操作的时间复杂度是常量级,但因为哈希冲突的存在,这个常量不一定比logn小,加上哈希函数的耗时,也不一定比平衡二叉查找树的效率高。

散列表的构造比二叉查找树复杂。

散列表装载因子不能太大,特别是基于开放寻址法解决冲突的散列表。

数据结构-算法

堆排序(上)

二叉树基础(上)