重新说明一下,上述代码添加一个条件:请使用BST、AVL、红黑树三种搜索树将其实现
时间: 2023-06-16 21:06:07 浏览: 62
好的,那么我们来分别使用BST、AVL、红黑树三种搜索树来实现上述代码。
首先是使用BST实现:
```python
class BSTNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = BSTNode(val)
return
curr = self.root
while curr:
if val < curr.val:
if not curr.left:
curr.left = BSTNode(val)
return
curr = curr.left
elif val > curr.val:
if not curr.right:
curr.right = BSTNode(val)
return
curr = curr.right
else:
return
def search(self, val):
curr = self.root
while curr:
if val < curr.val:
curr = curr.left
elif val > curr.val:
curr = curr.right
else:
return True
return False
```
然后是使用AVL树实现:
```python
class AVLNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.height = 1
class AVL:
def __init__(self):
self.root = None
def insert(self, val):
def get_height(node):
if not node:
return 0
return node.height
def get_balance(node):
if not node:
return 0
return get_height(node.left) - get_height(node.right)
def rotate_left(node):
right_child = node.right
node.right = right_child.left
right_child.left = node
node.height = max(get_height(node.left), get_height(node.right)) + 1
right_child.height = max(get_height(right_child.left), get_height(right_child.right)) + 1
return right_child
def rotate_right(node):
left_child = node.left
node.left = left_child.right
left_child.right = node
node.height = max(get_height(node.left), get_height(node.right)) + 1
left_child.height = max(get_height(left_child.left), get_height(left_child.right)) + 1
return left_child
def insert_node(node, val):
if not node:
return AVLNode(val)
elif val < node.val:
node.left = insert_node(node.left, val)
else:
node.right = insert_node(node.right, val)
node.height = max(get_height(node.left), get_height(node.right)) + 1
balance = get_balance(node)
if balance > 1 and val < node.left.val:
return rotate_right(node)
if balance < -1 and val > node.right.val:
return rotate_left(node)
if balance > 1 and val > node.left.val:
node.left = rotate_left(node.left)
return rotate_right(node)
if balance < -1 and val < node.right.val:
node.right = rotate_right(node.right)
return rotate_left(node)
return node
self.root = insert_node(self.root, val)
def search(self, val):
curr = self.root
while curr:
if val < curr.val:
curr = curr.left
elif val > curr.val:
curr = curr.right
else:
return True
return False
```
最后是使用红黑树实现:
```python
class RBNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.color = "RED"
class RedBlackTree:
def __init__(self):
self.root = None
def insert(self, val):
def rotate_left(node):
right_child = node.right
node.right = right_child.left
right_child.left = node
return right_child
def rotate_right(node):
left_child = node.left
node.left = left_child.right
left_child.right = node
return left_child
def is_red(node):
return node and node.color == "RED"
def flip_colors(node):
node.color = "RED"
node.left.color = "BLACK"
node.right.color = "BLACK"
def insert_node(node, val):
if not node:
return RBNode(val)
elif val < node.val:
node.left = insert_node(node.left, val)
elif val > node.val:
node.right = insert_node(node.right, val)
else:
return node
if is_red(node.right) and not is_red(node.left):
node = rotate_left(node)
if is_red(node.left) and is_red(node.left.left):
node = rotate_right(node)
if is_red(node.left) and is_red(node.right):
flip_colors(node)
return node
self.root = insert_node(self.root, val)
self.root.color = "BLACK"
def search(self, val):
curr = self.root
while curr:
if val < curr.val:
curr = curr.left
elif val > curr.val:
curr = curr.right
else:
return True
return False
```
以上就是使用BST、AVL、红黑树三种搜索树实现的代码,它们都能够完成相同的功能,但是在不同的场景下,它们的性能表现可能会有所不同。