Python
Python copied to clipboard
Published
1 month ago
•
TheAlgorithms
TheAlgorithms
Python/data_structures/binary_tree/red_black_tree.py remove error
''' remove can not change root '''
def test_self(): rb = [10, 11, 12, 6, 7, 8, 9, 2, 1, 18, 13, 14, 15, 16] tree = RedBlackTree(5) for d in rb: tree = tree.insert(d)
def u(t: RedBlackTree):
print(t.label, t.color)
if t.left:
u(t.left)
if t.right:
u(t.right)
def u1(t):
print("---")
u(tree)
print("---")
u1(tree)
for d in [10, 9, 8, 7, 6, 5, 2]:
tree.remove(d)
u1(tree)
This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.
![stale[bot] avatar](https://avatars.githubusercontent.com/in/1724?v=4 "Published by a pub.dev verified publisher"){kind=small}
Are we supposed to get errors running this code? Because I think it has been fixed.
maybe not
def print_tree(node: RedBlackTree):
rt = ['---']
def util(nd: RedBlackTree, indent: int):
if nd.right:
util(nd.right, indent+4)
text = '%s%s%s' % (indent*" ", ['b', 'r'][nd.color], nd.label)
rt.append(text)
if nd.left:
util(nd.left, indent+4)
util(node, 0)
rt.append('---')
print("\n".join(rt))
def test_insertion_speed() -> bool:
"""Test that the tree balances inserts to O(log(n)) by doing a lot
of them.
"""
t = RedBlackTree(0)
for i in range(1, 5):
t = t.insert(i)
print_tree(t)
print("insert finish")
t = t.remove(1)
print_tree(t)
print("remove finish")
return True
i test with code get result
maybe you need a root refer 算法导论
class TreeManage:
nil = None
def __init__(self, cls) -> None:
self.name = cls.__name__
self.nil: TreeBase = cls(None, None, self)
self.nil.set_color_black()
self.root: TreeBase = cls(None, self.nil, self)
self.root.set_color_black()
def set_root(self, node):
self.root = node
node.parent = self.nil
node.set_color_black()
def insert(self, val):
self.root.insert(val)
def remove(self, val):
self.root.remove(val)
from typing import List
from common import function
class TreeBase:
RED = 1
BLACK = 0
def __init__(self, val, parent, manage) -> None:
self.val = val
self.parent: TreeBase = parent
self.childs: List[TreeBase] = [None]*2
self.manage: TreeManage = manage
@property
def text(self):
return "%s" % self.val
@property
def left(self):
return self.childs[0]
@property
def right(self):
return self.childs[len(self.childs)-1]
@property
def brother(self):
if self.is_left():
return self.parent.right
if self.is_right():
return self.parent.left
@property
def uncle(self):
return self.parent.brother
def is_left(self):
return self.parent and self.parent.left == self
def is_right(self):
return self.parent and self.parent.right == self
def set_left(self, node):
self.childs[0] = node
if node:
node.set_parent(self)
def set_right(self, node):
self.childs[len(self.childs)-1] = node
if node:
node.set_parent(self)
def repair(self):
pass
def set_parent(self, node):
self.parent = node
if self.parent.is_nil():
self.manage.set_root(self)
def replace_by(self, node):
if self.is_left():
self.parent.set_left(node)
elif self.is_right():
self.parent.set_right(node)
if node:
node.set_parent(self.parent)
def rotate_left(self):
node = self.right
self.set_right(node.left)
self.replace_by(node)
node.set_left(self)
def rotate_right(self):
'''
5 3
3 6 2 5
2 4 -> 0 1 4 6
0 1
'''
node = self.left
self.set_left(node.right)
self.replace_by(node)
node.set_right(self)
def get_min(self):
if self.left is None or self.left.is_nil():
return self
return self.left.get_min()
def get_max(self):
if self.right and not self.right.is_nil():
return self
return self.right.get_max()
def big(self, val):
return self.val > val
def small(self, val):
return self.val < val
def is_nil(self):
return self.val is None
def is_red(self):
return self.color == TreeBase.RED
def set_color_red(self):
if self.is_nil():
return
self.color = TreeBase.RED
def set_color_black(self):
self.color = TreeBase.BLACK
def is_black(self):
return self.color == TreeBase.BLACK
def to_str(self):
split_line = '-------------------'
rt = [split_line]
def util(node: TreeBase, indent):
if node is None or node.is_nil():
return
util(node.right, indent+4)
rt.append("%s%s" %
(' '*indent, node.text))
util(node.left, indent+4)
util(self, 0)
rt.append(split_line)
return "\n".join(rt)
def get_err_msg(self):
return ""
def insert(self, val):
pass
def remove(self, val):
pass
class TreeManage:
nil = None
def __init__(self, cls) -> None:
self.name = cls.__name__
self.nil: TreeBase = cls(None, None, self)
self.nil.set_color_black()
self.root: TreeBase = cls(None, self.nil, self)
self.root.set_color_black()
def set_root(self, node):
self.root = node
node.parent = self.nil
node.set_color_black()
def insert(self, val):
self.root.insert(val)
def remove(self, val):
self.root.remove(val)
def tree_insert_remove(m: TreeManage, rb_insert_array, rb_remove_array):
def util(method, array):
for i, value in enumerate(array):
last_state = m.root.to_str()
if method == "insert":
m.root.insert(value)
else:
m.root.remove(value)
err_msg = m.root.get_err_msg()
if err_msg:
print(last_state)
print("%s v:%s e:%s" %
(method, value, err_msg))
print(m.root.to_str())
print(rb_insert_array, rb_remove_array)
exit()
util("insert", rb_insert_array)
util("remove", rb_remove_array)
def test_random_tree(m: TreeManage, n):
from random import randint
def rand_array(array):
rt = []
while len(array):
index = randint(0, len(array)-1)
rt.append(array.pop(index))
return rt
rb_insert_array = rand_array(list(range(0, n)))
rb_remove_array = rand_array(list(range(0, n)))
tree_insert_remove(m, rb_insert_array, rb_remove_array)
def test_all(m: TreeManage):
input_case = [
[7, 16, 9, 2, 8, 0, 6, 12, 11, 3, 13, 10, 15, 5, 4, 14, 1],
[14, 13, 2, 10, 6, 16, 11, 7, 1, 0, 8, 3, 4, 5, 15, 12, 9],
[10, 5, 12, 7, 9, 13, 1, 4, 8, 2, 6, 3, 0, 11, 14],
[7, 0, 6, 10, 2, 3, 11, 4, 14, 5, 13, 1, 8, 9, 12],
[0, 3, 1, 4, 5, 2, 6, 7, 9, 8, 10, 12, 11, 13, 14],
[4, 0, 8, 9, 1, 11, 2, 3, 12, 13, 5, 6, 7, 10, 14],
[1, 3, 10, 12, 6, 8, 9, 2, 4, 14, 11, 0, 5, 7, 13],
[9, 6, 5, 3, 8, 12, 7, 13, 11, 10, 1, 4, 2, 14, 0]
]
for i in range(0, len(input_case), 2):
tree_insert_remove(m, input_case[i], input_case[i+1])
for i in range(50):
test_random_tree(m, i)
from .tree_base import TreeBase
class RedBlackTree(TreeBase):
def __init__(self, val, parent, manage) -> None:
super().__init__(val, parent, manage)
if self.manage.nil:
self.set_left(self.manage.nil)
self.set_right(self.manage.nil)
self.color = RedBlackTree.RED
@property
def text(self):
return "%s:%s" % (['b', 'r'][self.color], 'n' if self.is_nil() else self.val)
def insert_repair(self):
# print(self.text, self.parent.text)
if self.parent.is_nil():
self.manage.set_root(self)
return
if self.parent.is_red():
if self.uncle and self.uncle.is_red():
self.parent.set_color_black()
self.uncle.set_color_black()
self.parent.parent.set_color_red()
self.parent.parent.insert_repair()
else:
if self.parent.is_right():
if self.is_left():
self.parent.rotate_right()
self.right.insert_repair()
elif self.is_right():
self.parent.set_color_black()
self.parent.parent.set_color_red()
self.parent.parent.rotate_left()
elif self.parent.is_left():
if self.is_right():
self.parent.rotate_left()
self.left.insert_repair()
elif self.is_left():
self.parent.set_color_black()
self.parent.parent.set_color_red()
self.parent.parent.rotate_right()
def insert(self, val):
if self.is_nil():
self.val = val
elif self.small(val):
if self.right is None or self.right.is_nil():
self.set_right(RedBlackTree(val, self, self.manage))
self.right.insert_repair()
else:
self.right.insert(val)
elif self.big(val):
if self.left is None or self.left.is_nil():
self.set_left(RedBlackTree(val, self, self.manage))
self.left.insert_repair()
else:
self.left.insert(val)
def remove_repair(self):
if self.brother is None:
return
if self.brother.is_black():
if self.brother.left.is_black() and self.brother.right.is_black():
self.brother.set_color_red()
if self.parent.is_red():
self.parent.set_color_black()
else:
self.parent.remove_repair() # 最难的代码
elif self.brother.is_right():
if self.brother.right.is_red():
self.brother.color = self.parent.color
self.brother.right.set_color_black()
self.parent.set_color_black()
self.parent.rotate_left()
elif self.brother.left.is_red() and self.brother.right.is_black():
self.brother.left.set_color_black()
self.brother.set_color_red()
self.brother.rotate_right()
self.remove_repair()
elif self.brother.is_left():
if self.brother.left.is_red():
self.brother.color = self.parent.color
self.brother.left.set_color_black()
self.parent.set_color_black()
self.parent.rotate_right()
elif self.brother.right.is_red() and self.brother.left.is_black():
self.brother.right.set_color_black()
self.brother.set_color_red()
self.brother.rotate_left()
self.remove_repair()
elif self.brother.is_red():
self.brother.set_color_black()
self.parent.set_color_red()
if self.brother.is_right():
self.parent.rotate_left()
elif self.brother.is_left():
self.parent.rotate_right()
self.remove_repair()
def remove(self, val):
# print("remove", self.text, val)
if self.is_nil():
return
elif self.val == val:
if not self.left.is_nil() and not self.right.is_nil():
z = self.right.get_min()
self.val = z.val
self.right.remove(z.val)
elif not self.left.is_nil():
self.replace_by(self.left)
self.left.set_color_black()
elif not self.right.is_nil():
self.replace_by(self.right)
self.right.set_color_black()
else:
if self == self.manage.root:
self.val = None
return
if self.is_black():
self.remove_repair()
self.replace_by(self.manage.nil)
elif self.small(val):
self.right.remove(val)
elif self.big(val):
self.left.remove(val)
def get_err_msg(self):
if self.manage and self.manage.root.is_red():
return "root red"
class Rt:
error_msg = ""
last_leaf_depth = None
def util(node: RedBlackTree, depth):
if Rt.error_msg or node is None:
return
if node.parent.is_red() and node.is_red():
Rt.error_msg = "parent and son is red"
return
if node.is_nil():
depth += 1
if Rt.last_leaf_depth is not None and Rt.last_leaf_depth != depth:
Rt.error_msg = "depth err %s==%s" % (
Rt.last_leaf_depth, depth)
Rt.last_leaf_depth = depth
else:
if node.is_black():
depth += 1
util(node.left, depth)
util(node.right, depth)
util(self, 0)
return Rt.error_msg
Are we supposed to get errors running this code? Because I think it has been fixed.
I'm not sure because I see there are some tests around remove. How did you figure out there's an error?
I don't know, I didn't fully understand the problem in the ticket but wanted to help. I am not the one who posted the issue.
The issue still exists. I tried using this library (Red Black Tree) and ran into this error - cannot delete root with class remove method.
# Minimal code to reproduce:
$ python
>>> from red_black_tree import RedBlackTree
>>> tree = RedBlackTree()
>>> tree.insert(1)
'1 blk'
>>> print(tree)
'1 blk'
>>> tree.remove(1)
'None blk'
>>> print(tree)
'1 blk'
# How it should work using TheAlgorithms AVL Tree as an example:
$ python
>>> from avl_tree import AVLtree
>>> tree = AVLtree()
>>> tree.insert(1)
insert:1
>>> print(tree)
1
*************************************
>>> tree.del_node(1)
delete:1
>>> print(tree)
>>>
I will take a stab at producing a PR...
Created PR #7439 to fix above issue and corresponding test. Any comments welcome.