二叉树进阶(搜索二叉树)

**二叉树进阶: 搜索二叉树**

二叉树是一种常见的数据结构，广泛应用于算法设计、计算机科学等领域。搜索二叉树是二叉树的一种特殊形式，它通过在每个结点中存储一个关键字来实现快速查找和插入操作。在本文中，我们将详细介绍搜索二叉树的定义、性质、算法以及相关代码示例。

**1. 搜索二叉树的定义**

搜索二叉树是一种二叉树，每个结点都有一个关键字（也称为值或键），且满足以下条件：

* 每个结点的左子树中所有结点的关键字均小于该结点的关键字。
* 每个结点的右子树中所有结点的关键字均大于该结点的关键字。

**2. 搜索二叉树的性质**

搜索二叉树具有以下重要性质：

* **查找时间复杂度**: 在平均情况下，搜索二叉树的查找操作的时间复杂度为 O(log n)，其中 n 是结点总数。
* **插入时间复杂度**: 搜索二叉树的插入操作的时间复杂度也为 O(log n)。
* **删除时间复杂度**: 删除操作的时间复杂度为 O(log n)，但需要注意的是，删除操作可能会导致树的高度增加。

**3. 搜索二叉树的算法**

以下是搜索二叉树的基本算法：

###3.1 查找查找操作涉及在树中找到一个特定的关键字。我们可以使用递归或迭代方法来实现这个过程。

class Node:
 def __init__(self, key):
 self.key = key self.left = None self.right = Nonedef search(root, key):
 """
 Search for a key in the binary search tree.

 Args:
 root (Node): The root of the binary search tree.
 key: The key to be searched.

 Returns:
 Node or None: The node containing the key if found, otherwise None.
 """
 if root is None:
 return None # If the key is less than the current node's key,
 # recursively search in the left subtree if key < root.key:
 return search(root.left, key)

 # If the key is greater than the current node's key,
 # recursively search in the right subtree elif key > root.key:
 return search(root.right, key)

 # If the key matches the current node's key,
 # return the current node else:
 return root# Example usage:
root = Node(5)
root.left = Node(3)
root.right = Node(7)
root.left.left = Node(2)
root.left.right = Node(4)

print(search(root,4).key) # Output:4

def insert(root, key):
 """
 Insert a new node with the given key into the binary search tree.

 Args:
 root (Node): The root of the binary search tree.
 key: The key to be inserted.

 Returns:
 Node: The updated root of the binary search tree.
 """
 if root is None:
 return Node(key)

 # If the key is less than the current node's key,
 # recursively insert into the left subtree if key < root.key:
 root.left = insert(root.left, key)
 # If the key is greater than the current node's key,
 # recursively insert into the right subtree elif key > root.key:
 root.right = insert(root.right, key)

 return root# Example usage:
root = Node(5)
root = insert(root,3)
root = insert(root,7)
root = insert(root,2)
root = insert(root,4)

print(search(root,4).key) # Output:4

def delete(root, key):
 """
 Delete the node with the given key from the binary search tree.

 Args:
 root (Node): The root of the binary search tree.
 key: The key to be deleted.

 Returns:
 Node or None: The updated root of the binary search tree if deletion is successful,
 otherwise None.
 """
 if root is None:
 return None # If the key matches the current node's key,
 # delete the current node if key == root.key:
 # Case1: No children if root.left is None and root.right is None:
 return None # Case2: One child (left)
 elif root.left is None:
 return root.right # Case3: One child (right)
 elif root.right is None:
 return root.left # Case4: Two children else:
 min_node = find_min(root.right)
 root.key = min_node.key root.right = delete(root.right, min_node.key)

 # If the key is less than the current node's key,
 # recursively delete from the left subtree elif key < root.key:
 root.left = delete(root.left, key)
 # If the key is greater than the current node's key,
 # recursively delete from the right subtree else:
 root.right = delete(root.right, key)

 return rootdef find_min(node):
 """
 Find the minimum value in a binary tree.

 Args:
 node (Node): The root of the binary tree.

 Returns:
 Node: The node containing the minimum value.
 """
 current = node while current.left is not None:
 current = current.left return current# Example usage:
root = Node(5)
root.left = Node(3)
root.right = Node(7)
root.left.left = Node(2)
root.left.right = Node(4)

print(delete(root,4).key) # Output: None