不同的二叉搜索树（简单题目+升级题目）

**不同类型的二叉搜索树**

二叉搜索树是一种常见的数据结构，用于存储和检索有序的数据。它通过在每个结点上维护一个值来实现快速查找、插入和删除操作。在本文中，我们将讨论不同的二叉搜索树类型及其特性。

###1. 平衡二叉搜索树（AVL树）

平衡二叉搜索树是一种自平衡的二叉搜索树，每个结点的高度相差不超过1。这种结构保证了在最坏情况下，所有操作的时间复杂度为O(log n)。

**AVL树的定义**

* 每个结点的左子树和右子树都是平衡二叉搜索树。
* 每个结点的高度相差不超过1。

**AVL树的插入和删除操作**

当我们在 AVL 树中插入或删除一个元素时，可能需要进行旋转来维持平衡性。具体来说：

* **左旋转（Left Rotation）**: 当右子树的高度大于左子树的高度时，我们需要对结点进行左旋转。
* **右旋转（Right Rotation）**: 当左子树的高度大于右子树的高度时，我们需要对结点进行右旋转。

**AVL树的实现**

class Node:
 def __init__(self, key):
 self.key = key self.left = None self.right = Noneclass AVLTree:
 def __init__(self):
 self.root = None def insert(self, key):
 if not self.root:
 self.root = Node(key)
 else:
 self._insert(self.root, key)

 def _insert(self, node, key):
 if key < node.key:
 if not node.left:
 node.left = Node(key)
 else:
 self._insert(node.left, key)
 elif key > node.key:
 if not node.right:
 node.right = Node(key)
 else:
 self._insert(node.right, key)

 def delete(self, key):
 self.root = self._delete(self.root, key)

 def _delete(self, node, key):
 if not node:
 return node if key < node.key:
 node.left = self._delete(node.left, key)
 elif key > node.key:
 node.right = self._delete(node.right, key)
 else:
 if not node.left and not node.right:
 return None elif not node.left:
 return node.right elif not node.right:
 return node.left else:
 min_node = self._find_min(node.right)
 node.key = min_node.key node.right = self._delete(node.right, min_node.key)

 if not node or (node.left and node.right):
 return node height_diff = self._get_height_diff(node)
 if height_diff >1:
 if key < node.left.key:
 return self._right_rotate(node)
 else:
 node.left = self._left_rotate(node.left)
 return self._right_rotate(node)

 def _find_min(self, node):
 while node.left:
 node = node.left return node def _get_height_diff(self, node):
 if not node:
 return0 left_height = self._get_height(node.left)
 right_height = self._get_height(node.right)
 return abs(left_height - right_height)

 def _get_height(self, node):
 if not node:
 return0 return max(self._get_height(node.left), self._get_height(node.right)) +1 def _left_rotate(self, node):
 new_root = node.right node.right = new_root.left new_root.left = node return new_root def _right_rotate(self, node):
 new_root = node.left node.left = new_root.right new_root.right = node return new_root# Example usage:
tree = AVLTree()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.insert(2)
tree.insert(4)
tree.insert(6)
tree.insert(8)

print("Height of the tree:", tree._get_height(tree.root))

###2. 红黑树红黑树是一种自平衡的二叉搜索树，每个结点都有一个颜色（红或黑），用于维持平衡性。这种结构保证了在最坏情况下，所有操作的时间复杂度为O(log n)。

**红黑树的定义**

* 每个结点的左子树和右子树都是红黑树。
* 每个结点的颜色是红或黑。
* 根结点是黑色的。
* 如果一个结点是红色的，则其左右子树中至多有一个结点是红色的。
* 对于任何结点，如果它是黑色的，则与之相邻的叶子结点（即，叶子结点的父结点）都是黑色的。

**红黑树的插入和删除操作**

当我们在红黑树中插入或删除一个元素时，可能需要进行旋转来维持平衡性。具体来说：

* **左旋转（Left Rotation）**: 当右子树的高度大于左子树的高度时，我们需要对结点进行左旋转。
* **右旋转（Right Rotation）**: 当左子树的高度大于右子树的高度时，我们需要对结点进行右旋转。

**红黑树的实现**

class Node:
 def __init__(self, key):
 self.key = key self.left = None self.right = None self.color = 'red'

class RedBlackTree:
 def __init__(self):
 self.root = None def insert(self, key):
 if not self.root:
 self.root = Node(key)
 self.root.color = 'black'
 else:
 self._insert(self.root, key)

 def _insert(self, node, key):
 if key < node.key:
 if not node.left:
 node.left = Node(key)
 else:
 self._insert(node.left, key)
 elif key > node.key:
 if not node.right:
 node.right = Node(key)
 else:
 self._insert(node.right, key)

 def delete(self, key):
 self.root = self._delete(self.root, key)

 def _delete(self, node, key):
 if not node:
 return node if key < node.key:
 node.left = self._delete(node.left, key)
 elif key > node.key:
 node.right = self._delete(node.right, key)
 else:
 if not node.left and not node.right:
 return None elif not node.left:
 return node.right elif not node.right:
 return node.left else:
 min_node = self._find_min(node.right)
 node.key = min_node.key node.right = self._delete(node.right, min_node.key)

 if not node or (node.left and node.right):
 return node height_diff = self._get_height_diff(node)
 if height_diff >1:
 if key < node.left.key:
 return self._right_rotate(node)
 else:
 node.left = self._left_rotate(node.left)
 return self._right_rotate(node)

 def _find_min(self, node):
 while node.left:
 node = node.left return node def _get_height_diff(self, node):
 if not node:
 return0 left_height = self._get_height(node.left)
 right_height = self._get_height(node.right)
 return abs(left_height - right_height)

 def _get_height(self, node):
 if not node:
 return0 return max(self._get_height(node.left), self._get_height(node.right)) +1 def _left_rotate(self, node):
 new_root = node.right node.right = new_root.left new_root.left = node if new_root.color == 'red':
 new_root.color = 'black'
 node.color = 'red'
 return new_root def _right_rotate(self, node):
 new_root = node.left node.left = new_root.right new_root.right = node if new_root.color == 'red':
 new_root.color = 'black'
 node.color = 'red'
 return new_root# Example usage:
tree = RedBlackTree()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.insert(2)
tree.insert(4)
tree.insert(6)
tree.insert(8)

print("Height of the tree:", tree._get_height(tree.root))

###3. B-树B-树是一种多叉搜索树，每个结点都有一个关键字和一个指向子树的数组。这种结构保证了在最坏情况下，所有操作的时间复杂度为O(log n)。

**B-树的定义**

* 每个结点的左子树