Python 实现二叉搜索树的四种方法
二叉搜索树（Binary Search Tree，简称BST）是一棵二叉树，它具有以下性质：
- 若左子树不为空，则左子树上所有结点的值均小于它的根节点的值；
- 若右子树不为空，则右子树上所有结点的值均大于它的根节点的值；
- 左、右子树分别也为二叉搜索树；
- 没有键值相等的节点；
因其高效性，在排序、查找等问题中，常常使用二叉搜索树来解决。下面，我们将介绍python中四种二叉搜索树的实现。
1. Python实现简单二叉搜索树
在BST的实现中，节点对象包含“val“、”left”和”right”三个域，其中”val“表示节点的值，”left”和”right”分别指向左右子树。get()方法用来查找值，insert()方法用来插入新节点。
class Node:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
class BinarySearchTree:
def __init__(self):
self.root = None
def get(self, val):
if self.root is None:
return None
else:
return self._get(val, self.root)
def _get(self, val, cur_node):
if cur_node.val == val:
return cur_node
elif val < cur_node.val and cur_node.left is not None:
return self._get(val, cur_node.left)
elif val > cur_node.val and cur_node.right is not None:
return self._get(val, cur_node.right)
else:
return None
def insert(self, val):
if self.root is None:
self.root = Node(val)
else:
self._insert(val, self.root)
def _insert(self, val, cur_node):
if val < cur_node.val:
if cur_node.left is None:
cur_node.left = Node(val)
else:
self._insert(val, cur_node.left)
elif val > cur_node.val:
if cur_node.right is None:
cur_node.right = Node(val)
else:
self._insert(val, cur_node.right)
else:
print('Value already in tree.')
下面给出一个简单例子，创建一棵二叉搜索树并插入一些新值：
tree = BinarySearchTree()
tree.insert(6)
tree.insert(3)
tree.insert(9)
tree.insert(2)
tree.insert(4)
tree.insert(8)
tree.insert(10)
2. Python实现AVL树
AVL树是一种自平衡的二叉搜索树，在应用于高并发、高IO、高负载的情况下可以减少树的深度，从而提升搜索的效率。与简单二叉搜索树不同，AVL树可以旋转来自平衡，保证在对一组n个数据进行建树之后的深度总是O(logn)。
class Node:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
self.height = 1
class AVLTree:
def __init__(self):
self.root = None
def _get_height(self, node):
if not node:
return 0
return node.height
def _get_balance(self, node):
if not node:
return 0
return self._get_height(node.left) - self._get_height(node.right)
def _fix_height(self, node):
node.height = 1 + max(self._get_height(node.left),
self._get_height(node.right))
def _right_rotate(self, y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
self._fix_height(y)
self._fix_height(x)
return x
def _left_rotate(self, x):
y = x.right
T2 = y.left
y.left = x
x.right = T2
self._fix_height(x)
self._fix_height(y)
return y
def insert(self, val):
def _insert(node, val):
if not node:
return Node(val)
elif val < node.val:
node.left = _insert(node.left, val)
elif val > node.val:
node.right = _insert(node.right, val)
else:
return node
self._fix_height(node)
balance = self._get_balance(node)
if balance > 1 and val < node.left.val:
return self._right_rotate(node)
if balance < -1 and val > node.right.val:
return self._left_rotate(node)
if balance > 1 and val > node.left.val:
node.left = self._left_rotate(node.left)
return self._right_rotate(node)
if balance < -1 and val < node.right.val:
node.right = self._right_rotate(node.right)
return self._left_rotate(node)
return node
self.root = _insert(self.root, val)
下面给出一个简单例子，创建一棵AVL树并插入一些新值：
tree = AVLTree()
tree.insert(9)
tree.insert(5)
tree.insert(10)
tree.insert(0)
tree.insert(6)
tree.insert(11)
tree.insert(-1)
tree.insert(1)
tree.insert(2)
3. Python实现红黑树
红黑树也是自平衡的二叉搜索树。它通过颜色标记节点来保证在一组n个数据中经过建树之后深度总是O(logn)。
RED = True
BLACK = False
class Node:
def __init__(self,val,color):
self.val=val
self.left=None
self.right=None
self.color=color
class RedBlackTree:
def __init__(self):
self.root = None
@staticmethod
def _color(node):
if node is None:
return BLACK
else:
return node.color
def _rotate_left(self,node):
right_node=node.right
node.right= right_node.left
right_node.left= node
right_node.color= node.color
node.color= RED
return right_node
def _rotate_right(self,node):
left_node= node.left
node.left= left_node.right
left_node.right= node
left_node.color= node.color
node.color= RED
return left_node
def _flip_color(self,node):
node.color= RED
node.left.color= BLACK
node.right.color= BLACK
def insert(self, val):
def _insert(node, val):
if not node:
return Node(val, RED)
if val < node.val:
node.left = _insert(node.left, val)
elif val > node.val:
node.right = _insert(node.right, val)
if self._color(node.right) == RED and self._color(node.left) == BLACK:
node = self._rotate_left(node)
if self._color(node.left) == RED and self._color(node.left.left) == RED:
node = self._rotate_right(node)
if self._color(node.left) == RED and self._color(node.right) == RED:
self._flip_color(node)
return node
self.root = _insert(self.root, val)
self.root.color = BLACK
下面给出一个简单例子，创建一棵红黑树并插入一些新值：
tree = RedBlackTree()
tree.insert(9)
tree.insert(5)
tree.insert(10)
tree.insert(0)
tree.insert(6)
tree.insert(11)
tree.insert(-1)
tree.insert(1)
tree.insert(2)
4. Python实现B树
B树是一种多路平衡查找树，本质上是一个多叉排序树，可以用来解决大数据量的存储和索引问题。B树的特点是每个节点可以有多个儿子，如2-3树一样保持平衡，既能够保证查询效率，又能够提供插入和删除的功能。
class Node:
def __init__(self, t, leaf=False):
self.t = t
self.keys = []
self.children = []
self.leaf = leaf
def split(self, parent, i):
t = self.t
new_node = Node(t, leaf=self.leaf)
parent.children.insert(i + 1, new_node)
parent.keys.insert(i, self.keys[t - 1])
new_node.children = self.children[t:]
self.children = self.children[:t - 1]
new_node.keys = self.keys[t:]
self.keys = self.keys[:t - 1]
return parent
def insert(self, k):
i = len(self.keys) - 1
if self.leaf:
self.keys.append(None)
while i >= 0 and k < self.keys[i]:
self.keys[i + 1] = self.keys[i]
i -= 1
self.keys[i + 1] = k
return self, None
else:
while i >= 0 and k < self.keys[i]:
i -= 1
i += 1
if len(self.children[i].keys) == 2 * self.t - 1:
return self.children[i].insert(k).split(self, i)
else:
return self.children[i].insert(k), None
class BTree:
def __init__(self, t=2):
self.t = t
self.root = Node(t, leaf=True)
def search(self, k):
x = self.root
while x is not None:
i = 0
while i < len(x.keys) and k > x.keys[i]:
i += 1
if i < len(x.keys) and k == x.keys[i]:
return x
if x.leaf:
return None
else:
x = x.children[i]
return None
def insert(self, k):
node, split = self.root.insert(k)
if split is not None:
self.root = Node(self.t, leaf=False)
self.root.children = [node, split]
self.root.keys = [split.keys[0]]
下面给出一个简单例子，创建一棵B树并插入一些新值：
tree = BTree(2)
for i in range(1, 11):
tree.insert(i)
search_val = 8
if tree.search(search_val):
print("{} is found in the B-tree".format(search_val))
else:
print("{} is not found in the B-tree".format(search_val))
# Output: 8 is found in the B-tree
本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：python 实现二叉搜索树的四种方法 - Python技术站
微信扫一扫 
支付宝扫一扫 