顺序查找，折半查找、散列查找、二叉排序树查找算法的时间复杂度和空间复杂度

顺序查找的时间复杂度是O(n)，空间复杂度是O(1)。

折半查找（二分查找）的时间复杂度是O(logn)，空间复杂度是O(1)。

散列查找（哈希查找）的时间复杂度在理想情况下是O(1)，但最坏情况下可能会达到O(n)，空间复杂度取决于哈希表的大小。

二叉排序树查找的时间复杂度在平均情况下是O(logn)，但在最坏情况下可能会达到O(n)，空间复杂度取决于树的高度，平均情况下是O(logn)。

相关问题

分析顺序查找，折半查找、散列查找、二叉排序树查找算法的时间复杂度和空间复杂度

顺序查找：
- 时间复杂度：O(n)，其中n是待查找的元素数量。因为需要逐个比较每个元素，直到找到目标元素或遍历完整个列表。
- 空间复杂度：O(1)，因为只需要常数级的额外空间来存储一些辅助变量。

折半查找（二分查找）：
- 时间复杂度：O(logn)，其中n是有序列表的元素数量。每次比较后可以将查找范围减半，因此时间复杂度是对数级别的。
- 空间复杂度：O(1)，因为只需要常数级的额外空间来存储一些辅助变量。

散列查找（哈希查找）：
- 时间复杂度：在理想情况下，散列查找的时间复杂度是O(1)。即通过哈希函数直接定位到目标元素所在的位置。但最坏情况下，如果有很多元素被映射到同一个位置，时间复杂度可能会达到O(n)。
- 空间复杂度：取决于哈希表的大小和元素数量。通常情况下，散列查找的空间复杂度是O(n)，因为需要存储所有元素以及哈希表的额外空间。

二叉排序树查找：
- 时间复杂度：在平均情况下，二叉排序树的时间复杂度是O(logn)，其中n是二叉排序树的节点数量。但在最坏情况下，如果二叉排序树退化成链表，时间复杂度可能会达到O(n)。
- 空间复杂度：取决于二叉排序树的高度。平均情况下，二叉排序树的空间复杂度是O(logn)，最坏情况下是O(n)。

折半查找和二叉排序树的算法实现

折半查找（Binary Search）和二叉排序树（Binary Search Tree）是两种常用的查找算法。

1. 折半查找算法实现：
折半查找是一种在有序数组中查找指定元素的算法。它的基本思想是将数组分成两部分，然后判断目标元素与中间元素的大小关系，进而确定目标元素在哪一部分中，然后再在该部分中进行查找，如此循环直到找到目标元素或者确定目标元素不存在。

以下是折半查找的算法实现示例：

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1  # 目标元素不存在

arr = [5, 14, 18, 21, 23, 29, 31, 35]
target = 29
result = binary_search(arr, target)
print("小于29的最大关键字值是:", arr[result-1])  # 输出：23

2. 二叉排序树算法实现：
二叉排序树是一种特殊的二叉树，它的每个节点的左子树的所有节点的值都小于该节点的值，右子树的所有节点的值都大于该节点的值。通过这种特性，可以实现高效的插入和删除操作。

以下是二叉排序树的算法实现示例：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def insert(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def delete(root, val):
    if root is None:
        return root
    if val < root.val:
        root.left = delete(root.left, val)
    elif val > root.val:
        root.right = delete(root.right, val)
    else:
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        else:
            min_node = find_min(root.right)
            root.val = min_node.val
            root.right = delete(root.right, min_node.val)
    return root

def find_min(root):
    while root.left:
        root = root.left
    return root

def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.val, end=" ")
        inorder_traversal(root.right)

# 构造二叉排序树
keys = [45, 24, 53, 12, 37, 93, 13]
root = None
for key in keys:
    root = insert(root, key)

# 删除关键字53和24
root = delete(root, 53)
root = delete(root, 24)

# 中序遍历二叉排序树
inorder_traversal(root)  # 输出：12 13 37 45 93