Python 中的 AVL 树实现
AVL Tree Implemention In Python
我正在将我的二叉搜索树变成一棵 AVL 树，但我偶然发现了这个问题，我认为平衡因子是正确的，但树本身似乎没有发生旋转。如果有人能指出我的错误和不准确之处，那就太好了！
我这样做是为了让每个节点在制作时从 parent_node + 1 获得它的高度。
平衡系数 = node.left.height - node.right.height
class Node:
def __init__(self, value):
"""
Every Node has a value, and a height based on how far it is from the root node
"""
self.value = value
self.left = None
self.right = None
self.height = 1
class AVLTree:
def __init__(self, List=None):
self.root = None
if List:
for item in List:
self.insert(item)
def inorder(self, current_node):
if current_node:
self.inorder(current_node.left)
print(current_node.value, end=' ')
self.inorder(current_node.right)
def get_height(self, node):
"""
gets the value of height
which is how far the node is from the root node, given that the root node has a height of 1, and its children has 2
Ex:
O Height = 1
/ \
O O Height = 2
/ \ / \
O O O O Height = 3
"""
if node is None:
return 1
return node.height
def update_heights(self, current_node, depth):
"""
"""
if current_node is None:
return
current_node.height = depth
self.update_heights(current_node.left, 1+depth)
self.update_heights(current_node.right, 1+depth)
def get_balance_factor(self, node):
"""
Balance_factor is the difference between the heights of the two child node of the node
Rebalancing occurs when the balance_factor is greater than a difference of 1 (or) less than a difference of -1
usage: balance_factor = get_balance_factor(node)
which is left_child_height - right_child_height
If balanced, balance_factor = -1/0/1:
O O O O
/ \ / \ / \ / \
O O O O O O O O
/ \ / \
O O O O
If balance_factor > 1:
O <--- Node
/ \
O O Height = 2
/ \
O O Height = 3
/ \
O O Height = 4
Difference of L and R = 2 (4-2)
If balance_factor < 1:
O <--- Node
/ \
O O Height = 2
/ \
O O Height = 3
/ \
O O Height = 4
Difference of L and R = -2 (2-4)
"""
if node is None:
return
return self.get_height(node.left) - self.get_height(node.right)
def rotate_right(self, y):
"""
Rotates right
Ex:
y x
/ \ Right Rotation / \
x T3 - - - - - - - > T1 y
/ \ / \
T1 T2 T2 T3
so only 2 things changed
the left child of y became T2
and the right child of x became y
"""
# Rotation
x = y.left
T2 = x.right
x.right = y
y.left = T2
# Updating Heights
self.update_heights(x, y.height)
def rotate_left(self, x):
"""
Rotates left
Ex:
y x
/ \ / \
x T3 T1 y
/ \ < - - - - - - - / \
T1 T2 Left Rotation T2 T3
"""
# Rotation
y = x.right
T2 = y.left
y.left = x
x.right = T2
# Updating Heights
self.update_heights(y, x.height)
def insert(self, value):
NewNode = Node(value)
current_node = self.root
# Traversing through the Tree till we find the right place to put the value
if current_node is None:
self.root = NewNode
else:
while True:
if value < current_node.value:
#Left
if not current_node.left:
current_node.left = NewNode
break
current_node = current_node.left
else:
#Right
if not current_node.right:
current_node.right = NewNode
break
current_node = current_node.right
# Giving the new node a value of height based on how far he is from root node
NewNode.height = 1 + current_node.height
# Getting the balance factor, which shows if the tree is balanced or not after insertion, by the difference of the heights between the left and right children of the node
balance_factor = self.get_balance_factor(current_node)
print(balance_factor)
# Checks if the node is unbalanced, and if it is, perform one of the 4 cases
# Case 1: Left Left
if balance_factor > 1 and value < current_node.left.value:
self.rotate_right(current_node)
# Case 2: Right Right
if balance_factor < -1 and value > current_node.right.value:
self.rotate_left(current_node)
# Case 3: Left Right
if balance_factor > 1 and value > current_node.left.value:
self.rotate_left(current_node.left)
self.rotate_right(current_node)
# Case 4: Right Left
if balance_factor < -1 and value < current_node.right.value:
self.rotate_right(current_node.right)
self.rotate_left(current_node)
这是一个解决方案：
我把get_height改成了get_depth，因为高度的使用是为了检查两个节点之间的深度差异，所以它在上下文中的使用是错误的。
因此，我添加了一个新的递归函数max_depth。检查节点的所有子节点，以及 returns 节点的深度。
我还将平衡更改为递归函数，该函数一直到父节点，直到它到达根节点。
我为指定父节点的树节点添加了一个额外的属性，以便在旋转期间可以在 x 和 y 之间切换。
class Node:
def __init__(self, value, parent=None):
"""
Every Node has a value, and a height based on how far it is from the root node
"""
self.value = value
self.parent = parent
self.left = None
self.right = None
self.height = 1
class AVLTree:
def __init__(self, List=None):
self.root = None
if List:
for item in List:
self.insert(item)
def inorder(self, current_node):
if current_node:
self.inorder(current_node.left)
print(current_node.value, end=' ')
self.inorder(current_node.right)
def max_depth(self, root):
# Null node has 0 depth.
if root == None:
return 0
# Get the depth of the left and right subtree
# using recursion.
leftDepth = self.max_depth(root.left)
rightDepth = self.max_depth(root.right)
# Choose the larger one and add the root to it.
if leftDepth > rightDepth:
return leftDepth + 1
else:
return rightDepth + 1
def get_depth(self, node, parent_node):
"""
gets the value of height
which is how far the node is from the root node, given that the root node has a height of 1, and its children has 2
Ex:
O Height = 1
/ \
O O Height = 2
/ \ / \
O O O O Height = 3
"""
if node is None:
return 0
return self.max_depth(node)
def update_heights(self, current_node, depth):
"""
"""
if current_node is None:
return
current_node.height = depth
self.update_heights(current_node.left, 1+depth)
self.update_heights(current_node.right, 1+depth)
def get_balance_factor(self, node):
"""
Balance_factor is the difference between the heights of the two child node of the node
Rebalancing occurs when the balance_factor is greater than a difference of 1 (or) less than a difference of -1
usage: balance_factor = get_balance_factor(node)
which is left_child_height - right_child_height
If balanced, balance_factor = -1/0/1:
O O O O
/ \ / \ / \ / \
O O O O O O O O
/ \ / \
O O O O
If balance_factor > 1:
O <--- Node
/ \
O O Height = 2
/ \
O O Height = 3
/ \
O O Height = 4
Difference of L and R = 2 (4-2)
If balance_factor < 1:
O <--- Node
/ \
O O Height = 2
/ \
O O Height = 3
/ \
O O Height = 4
Difference of L and R = -2 (2-4)
"""
if node is None:
return
return self.get_depth(node.left, node) - self.get_depth(node.right, node)
def rotate_right(self, y):
"""
Rotates right
Ex:
y x
/ \ Right Rotation / \
x T3 - - - - - - - > T1 y
/ \ / \
T1 T2 T2 T3
so only 2 things changed
the left child of y became T2
and the right child of x became y
"""
# Rotation
parent = y.parent
x = y.left
T2 = x.right
x.right = y
y.left = T2
if T2:
T2.parent = y
x.parent = parent
if parent is None:
self.root = x
if parent.left == y:
parent.left = x
elif y.parent.right == y:
parent.right = x
# Updating Heights
self.update_heights(x, y.height)
def rotate_left(self, x):
"""
Rotates left
Ex:
y x
/ \ / \
x T3 T1 y
/ \ < - - - - - - - / \
T1 T2 Left Rotation T2 T3
"""
# Rotation
parent = x.parent
y = x.right
T2 = y.left
y.left = x
x.right = T2
if T2:
T2.parent = x
y.parent = parent
if parent is None:
self.root = y
elif parent.left == x:
parent.left = y
elif y.parent.right == x:
parent.right = y
# Updating Heights
self.update_heights(y, x.height)
def recursive_balancing(self, current_node, value):
if current_node is None:
return
# Getting the balance factor, which shows if the tree is balanced or not after insertion, by the difference of the heights between the left and right children of the node
balance_factor = self.get_balance_factor(current_node)
print(balance_factor)
# Checks if the node is unbalanced, and if it is, perform one of the 4 cases
# Case 1: Left Left
if balance_factor > 1 and current_node.left:
if value < current_node.left.value:
self.rotate_right(current_node)
# Case 2: Right Right
if balance_factor < -1 and current_node.right:
if value > current_node.right.value:
self.rotate_left(current_node)
# Case 3: Left Right
if balance_factor > 1 and current_node.left:
if value > current_node.left.value:
self.rotate_left(current_node.left)
self.rotate_right(current_node)
# Case 4: Right Left
if balance_factor < -1 and current_node.right:
if value < current_node.right.value:
self.rotate_right(current_node.right)
self.rotate_left(current_node)
self.recursive_balancing(current_node.parent, value)
def insert(self, value):
NewNode = Node(value)
current_node = self.root
# Traversing through the Tree till we find the right place to put the value
if current_node is None:
self.root = NewNode
else:
while True:
if value < current_node.value:
NewNode.parent = current_node
#Left
if not current_node.left:
current_node.left = NewNode
break
NewNode.parent = current_node
current_node = current_node.left
else:
NewNode.parent = current_node
#Right
if not current_node.right:
current_node.right = NewNode
break
NewNode.parent = current_node
current_node = current_node.right
# Giving the new node a value of height based on how far he is from root node
NewNode.height = 1 + current_node.height
# Recursive balancing
self.recursive_balancing(current_node, value)
我正在将我的二叉搜索树变成一棵 AVL 树，但我偶然发现了这个问题，我认为平衡因子是正确的，但树本身似乎没有发生旋转。如果有人能指出我的错误和不准确之处，那就太好了！
我这样做是为了让每个节点在制作时从 parent_node + 1 获得它的高度。 平衡系数 = node.left.height - node.right.height
class Node:
def __init__(self, value):
"""
Every Node has a value, and a height based on how far it is from the root node
"""
self.value = value
self.left = None
self.right = None
self.height = 1
class AVLTree:
def __init__(self, List=None):
self.root = None
if List:
for item in List:
self.insert(item)
def inorder(self, current_node):
if current_node:
self.inorder(current_node.left)
print(current_node.value, end=' ')
self.inorder(current_node.right)
def get_height(self, node):
"""
gets the value of height
which is how far the node is from the root node, given that the root node has a height of 1, and its children has 2
Ex:
O Height = 1
/ \
O O Height = 2
/ \ / \
O O O O Height = 3
"""
if node is None:
return 1
return node.height
def update_heights(self, current_node, depth):
"""
"""
if current_node is None:
return
current_node.height = depth
self.update_heights(current_node.left, 1+depth)
self.update_heights(current_node.right, 1+depth)
def get_balance_factor(self, node):
"""
Balance_factor is the difference between the heights of the two child node of the node
Rebalancing occurs when the balance_factor is greater than a difference of 1 (or) less than a difference of -1
usage: balance_factor = get_balance_factor(node)
which is left_child_height - right_child_height
If balanced, balance_factor = -1/0/1:
O O O O
/ \ / \ / \ / \
O O O O O O O O
/ \ / \
O O O O
If balance_factor > 1:
O <--- Node
/ \
O O Height = 2
/ \
O O Height = 3
/ \
O O Height = 4
Difference of L and R = 2 (4-2)
If balance_factor < 1:
O <--- Node
/ \
O O Height = 2
/ \
O O Height = 3
/ \
O O Height = 4
Difference of L and R = -2 (2-4)
"""
if node is None:
return
return self.get_height(node.left) - self.get_height(node.right)
def rotate_right(self, y):
"""
Rotates right
Ex:
y x
/ \ Right Rotation / \
x T3 - - - - - - - > T1 y
/ \ / \
T1 T2 T2 T3
so only 2 things changed
the left child of y became T2
and the right child of x became y
"""
# Rotation
x = y.left
T2 = x.right
x.right = y
y.left = T2
# Updating Heights
self.update_heights(x, y.height)
def rotate_left(self, x):
"""
Rotates left
Ex:
y x
/ \ / \
x T3 T1 y
/ \ < - - - - - - - / \
T1 T2 Left Rotation T2 T3
"""
# Rotation
y = x.right
T2 = y.left
y.left = x
x.right = T2
# Updating Heights
self.update_heights(y, x.height)
def insert(self, value):
NewNode = Node(value)
current_node = self.root
# Traversing through the Tree till we find the right place to put the value
if current_node is None:
self.root = NewNode
else:
while True:
if value < current_node.value:
#Left
if not current_node.left:
current_node.left = NewNode
break
current_node = current_node.left
else:
#Right
if not current_node.right:
current_node.right = NewNode
break
current_node = current_node.right
# Giving the new node a value of height based on how far he is from root node
NewNode.height = 1 + current_node.height
# Getting the balance factor, which shows if the tree is balanced or not after insertion, by the difference of the heights between the left and right children of the node
balance_factor = self.get_balance_factor(current_node)
print(balance_factor)
# Checks if the node is unbalanced, and if it is, perform one of the 4 cases
# Case 1: Left Left
if balance_factor > 1 and value < current_node.left.value:
self.rotate_right(current_node)
# Case 2: Right Right
if balance_factor < -1 and value > current_node.right.value:
self.rotate_left(current_node)
# Case 3: Left Right
if balance_factor > 1 and value > current_node.left.value:
self.rotate_left(current_node.left)
self.rotate_right(current_node)
# Case 4: Right Left
if balance_factor < -1 and value < current_node.right.value:
self.rotate_right(current_node.right)
self.rotate_left(current_node)
这是一个解决方案：
我把get_height改成了get_depth，因为高度的使用是为了检查两个节点之间的深度差异，所以它在上下文中的使用是错误的。
因此，我添加了一个新的递归函数max_depth。检查节点的所有子节点，以及 returns 节点的深度。
我还将平衡更改为递归函数，该函数一直到父节点，直到它到达根节点。
我为指定父节点的树节点添加了一个额外的属性，以便在旋转期间可以在 x 和 y 之间切换。
class Node:
def __init__(self, value, parent=None):
"""
Every Node has a value, and a height based on how far it is from the root node
"""
self.value = value
self.parent = parent
self.left = None
self.right = None
self.height = 1
class AVLTree:
def __init__(self, List=None):
self.root = None
if List:
for item in List:
self.insert(item)
def inorder(self, current_node):
if current_node:
self.inorder(current_node.left)
print(current_node.value, end=' ')
self.inorder(current_node.right)
def max_depth(self, root):
# Null node has 0 depth.
if root == None:
return 0
# Get the depth of the left and right subtree
# using recursion.
leftDepth = self.max_depth(root.left)
rightDepth = self.max_depth(root.right)
# Choose the larger one and add the root to it.
if leftDepth > rightDepth:
return leftDepth + 1
else:
return rightDepth + 1
def get_depth(self, node, parent_node):
"""
gets the value of height
which is how far the node is from the root node, given that the root node has a height of 1, and its children has 2
Ex:
O Height = 1
/ \
O O Height = 2
/ \ / \
O O O O Height = 3
"""
if node is None:
return 0
return self.max_depth(node)
def update_heights(self, current_node, depth):
"""
"""
if current_node is None:
return
current_node.height = depth
self.update_heights(current_node.left, 1+depth)
self.update_heights(current_node.right, 1+depth)
def get_balance_factor(self, node):
"""
Balance_factor is the difference between the heights of the two child node of the node
Rebalancing occurs when the balance_factor is greater than a difference of 1 (or) less than a difference of -1
usage: balance_factor = get_balance_factor(node)
which is left_child_height - right_child_height
If balanced, balance_factor = -1/0/1:
O O O O
/ \ / \ / \ / \
O O O O O O O O
/ \ / \
O O O O
If balance_factor > 1:
O <--- Node
/ \
O O Height = 2
/ \
O O Height = 3
/ \
O O Height = 4
Difference of L and R = 2 (4-2)
If balance_factor < 1:
O <--- Node
/ \
O O Height = 2
/ \
O O Height = 3
/ \
O O Height = 4
Difference of L and R = -2 (2-4)
"""
if node is None:
return
return self.get_depth(node.left, node) - self.get_depth(node.right, node)
def rotate_right(self, y):
"""
Rotates right
Ex:
y x
/ \ Right Rotation / \
x T3 - - - - - - - > T1 y
/ \ / \
T1 T2 T2 T3
so only 2 things changed
the left child of y became T2
and the right child of x became y
"""
# Rotation
parent = y.parent
x = y.left
T2 = x.right
x.right = y
y.left = T2
if T2:
T2.parent = y
x.parent = parent
if parent is None:
self.root = x
if parent.left == y:
parent.left = x
elif y.parent.right == y:
parent.right = x
# Updating Heights
self.update_heights(x, y.height)
def rotate_left(self, x):
"""
Rotates left
Ex:
y x
/ \ / \
x T3 T1 y
/ \ < - - - - - - - / \
T1 T2 Left Rotation T2 T3
"""
# Rotation
parent = x.parent
y = x.right
T2 = y.left
y.left = x
x.right = T2
if T2:
T2.parent = x
y.parent = parent
if parent is None:
self.root = y
elif parent.left == x:
parent.left = y
elif y.parent.right == x:
parent.right = y
# Updating Heights
self.update_heights(y, x.height)
def recursive_balancing(self, current_node, value):
if current_node is None:
return
# Getting the balance factor, which shows if the tree is balanced or not after insertion, by the difference of the heights between the left and right children of the node
balance_factor = self.get_balance_factor(current_node)
print(balance_factor)
# Checks if the node is unbalanced, and if it is, perform one of the 4 cases
# Case 1: Left Left
if balance_factor > 1 and current_node.left:
if value < current_node.left.value:
self.rotate_right(current_node)
# Case 2: Right Right
if balance_factor < -1 and current_node.right:
if value > current_node.right.value:
self.rotate_left(current_node)
# Case 3: Left Right
if balance_factor > 1 and current_node.left:
if value > current_node.left.value:
self.rotate_left(current_node.left)
self.rotate_right(current_node)
# Case 4: Right Left
if balance_factor < -1 and current_node.right:
if value < current_node.right.value:
self.rotate_right(current_node.right)
self.rotate_left(current_node)
self.recursive_balancing(current_node.parent, value)
def insert(self, value):
NewNode = Node(value)
current_node = self.root
# Traversing through the Tree till we find the right place to put the value
if current_node is None:
self.root = NewNode
else:
while True:
if value < current_node.value:
NewNode.parent = current_node
#Left
if not current_node.left:
current_node.left = NewNode
break
NewNode.parent = current_node
current_node = current_node.left
else:
NewNode.parent = current_node
#Right
if not current_node.right:
current_node.right = NewNode
break
NewNode.parent = current_node
current_node = current_node.right
# Giving the new node a value of height based on how far he is from root node
NewNode.height = 1 + current_node.height
# Recursive balancing
self.recursive_balancing(current_node, value)