파이썬에서 나무의 좌우 회전
Aug 19 2020
나는 수업을 사용합니다.
class Node:
def __init__(self, value):
self.key = value
self.left = None
self.right = None
self.parent = None
이 트리를 만들었습니다.
n_12 = Node(12)
n_15 = Node(15)
n_3 = Node(3)
n_7 = Node(7)
n_1 = Node(1)
n_2 = Node(2)
n_not1 = Node(-1)
n_12.right = n_15
n_12.left = n_3
n_3.right = n_7
n_3.left = n_1
n_1.right = n_2
n_1.left = n_not1
n_12.parent = None
n_15.parent = n_12
n_3.parent = n_12
n_7.parent = n_3
n_1.parent = n_3
n_2.parent = n_1
n_not1.parent = n_1
이 코드를 시도했습니다.
def rightRotate(t):
if t == None or t.left == None:
return None
n = t
l = t.left
r = t.right
lr = t.left.right
ll = t.left.left
t = t.left
t.right = n
if r != None:
t.right.right = r
if lr != None:
t.right.left = lr
if ll != None:
t.left = ll
그러나 작동하지 않았으며 루트 노드 n_12
를 사용하면 일부 노드가 삭제됩니다. 왜 작동하지 않았고 왜 모든 노드가 없는지 이해하지 못합니다. 을 호출 rightRotate(n_1)
하면 무한 루프가 있습니다.
답변
trincot Aug 19 2020 at 18:59
당신은 쓰기 "나는 무한 루프가" 하지만 코드에서 다른 곳에서 발생해야합니다 귀하의 코드는 더 루프가 없습니다.
두 가지 문제가 있습니다.
1) 할당은 무조건적이어야합니다.
if lr != None:
t.right.left = lr
이 과제가되고 또한 때 필요 lr is None
. 하지 않는 경우 t.right.left
동일하게 유지됩니다에 l
이는 t
그 순간에, 당신 때문에 참으로 당신의 트리에서 루프로 남아 있습니다.
2) 이중 스레딩
나무는 이중 스레드입니다. 즉, parent
링크 도 있습니다. 그러나 이들은 rightRotate
함수 에서 업데이트되지 않습니다 . 따라서 parent
링크 없이 수행하거나 (바람직 함), parent
회전에 따라 링크도 업데이트 되도록 코드를 조정하십시오 .
다른 말 :
다음 코드는 단순화 할 수 있습니다.
if r != None:
t.right.right = r # was already equal to r
if lr != None:
t.right.left = lr # see above. should not be behind a condition
if ll != None:
t.left = ll # was already equal to ll
따라서 다음과 같이 줄일 수 있습니다.
t.right.left = lr
또는:
n.left = lr
최종 코드
위에서 언급 한 변경 사항으로 인해 기능은 다음과 같을 수 있습니다.
class Node:
def __init__(self, value):
self.key = value
self.left = None
self.right = None
self.parent = None
def rightRotate(node):
if node is None or node.left is None:
return node
parent = node.parent
left = node.left
left_right = left.right
# change edge 1
if parent: # find out if node is a left or right child of node
if parent.left == node:
parent.left = left
else:
parent.right = left
left.parent = parent
# change edge 2
left.right = node
node.parent = left
# change edge 3
node.left = left_right
if left_right:
left_right.parent = node
return left # the node that took the position of node
# your code to build the tree
n_12 = Node(12)
n_15 = Node(15)
n_3 = Node(3)
n_7 = Node(7)
n_1 = Node(1)
n_2 = Node(2)
n_not1 = Node(-1)
n_12.right = n_15
n_12.left = n_3
n_3.right = n_7
n_3.left = n_1
n_1.right = n_2
n_1.left = n_not1
n_12.parent = None
n_15.parent = n_12
n_3.parent = n_12
n_7.parent = n_3
n_1.parent = n_3
n_2.parent = n_1
n_not1.parent = n_1
# rotate the root
root = n_12
root = rightRotate(root) # returns the node that took the place of n_12
parent
단일 스레드 버전을 얻으려면 줄을 제거하십시오 .