数据结构与算法学习之搜索二叉树
2022-06-16 09:46:49
思考
如何在 n 个动态的整数中搜索某个整数?(检测其是否存在)
Ⅰ. 考虑使用动态数组存放元素,从第 0 个位置开始遍历搜索,平均时间复杂度:O(n)
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
33 | 66 | 18 | 28 | 16 | 52 | 95 | 45 | 86 | 71 |
Ⅱ. 如果是一个有序的动态数组,使用二分搜索,最坏的时间复杂度:**O(logn);添加和删除的平均时间复杂度是O(n)**;
数据规模不断减半,时间复杂度一般为 O(logn);
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
15 | 17 | 20 | 28 | 31 | 46 | 57 | 68 | 85 | 94 |
针对这个需求是否有更好的办法?
使用二叉搜索树,添加、删除、搜索额最坏时间复杂度均可优化至:O(logn);
二叉搜索树
二叉搜索树是二叉树的一种,是应用非常广泛的一种二叉树,英文简称为BST,又被称为二叉查找树、二叉排序;
- 树任意一个节点的值都大于其左子树所有节点的值;
- 任意一个节点的值都小于其右子树所有节点的值;
- 它的左右子树也是一棵二叉搜索树;
- 二叉搜索树存储的元素必须具有可比较性;
接口设计
1 | int size() // 元素的数量 |
通过接口可以看出,对于目前这个二叉树来说,元素是没有索引的概念的;
代码逻辑
首先,新建的二叉搜索树 BinarySearchTree
类,在其中需要有几个基础的属性:
size
:保存节点的变量;root
:根节点的变量,二叉搜索树的操作都需要从根节点开始;elementNotNullCheck
:检查节点元素是否为空的方法;
1 | private int size; |
节点设计
在 BinarySearchTree
类中,需要创建一个内部类进行节点的维护,内部包括左右节点和父节点,以及存储的元素,在构造时只需传入元素值和父节点即可:
1 | private static class Node<E>{ |
比较逻辑
Comparable 接口
所有传入二叉搜索树的元素都必须实现 Comparable 接口:
1 | public interface Comparable<E> { |
但是传入的对象实现了 Comparable 接口后,其比较逻辑其实是被限制无法改变了,如需要针对同一个对象根据其他属性进行比较是无法实现的;
Comparator 接口
要求在构造二叉搜索树时,必须传入一个 Comparator 比较器,
1 | public interface Comparator<E> { |
通过比较器虽然可以自定义比较逻辑,但是这样未免过于激进,不应该强制传入比较器,而应有其默认的比较逻辑;综上,结合二者的方法即是比较合理的实现:
1 | public class BinarySearchTree<E> { |
需要注意的是,上述代码中没有要求传入的元素必须实现 Comparable 接口,因为 BinarySearchTree 类默认当作元素已经实现了该接口;
添加逻辑
基本思路:
- 先判断是否存在根节点,无则赋值为根节点;
- 根据根节点,通过与插入元素比较,找到对应的父节点;
- 创建新节点,通过
parent.left = node
或者parent.right = node
- 相同的值,如何处理?
- 直接返回;
- 覆盖原有的值(推荐);
1 | void add(E element) { |