Rotasi kanan dan kiri pohon dengan python
Saya menggunakan kelas:
class Node:
def __init__(self, value):
self.key = value
self.left = None
self.right = None
self.parent = None
dan saya telah membuat pohon ini:
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
Saya mencoba kode ini:
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
Tapi itu tidak berhasil, menggunakan node root n_12
itu menghapus beberapa node. Mengapa tidak berhasil dan saya tidak mengerti mengapa saya tidak memiliki semua node. Jika saya menelepon rightRotate(n_1)
, saya memiliki loop tak terbatas.
Jawaban
Anda menulis "I have an infinite loop" , tetapi kode Anda tidak memiliki loop, jadi itu pasti terjadi di tempat lain dalam kode Anda.
Saya melihat dua masalah:
1) Penugasan harus tanpa syarat
if lr != None:
t.right.left = lr
Tugas ini juga dibutuhkan saat lr is None
. Jika tidak, t.right.left
akan tetap sama dengan l
yang ada t
pada saat itu, dan Anda memang tertinggal dengan lingkaran di pohon Anda.
2) Ulir ganda
Pohon Anda berulir ganda, yaitu, pohon juga memiliki parent
tautan. Tetapi ini tidak diperbarui dalam rightRotate
fungsi Anda . Jadi lakukan tanpa parent
tautan (yang lebih disukai), atau sesuaikan kode Anda sehingga parent
tautan juga diperbarui sesuai dengan rotasi.
Keterangan Lainnya:
Potongan kode berikut dapat disederhanakan:
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
Sehingga bisa direduksi menjadi hanya:
t.right.left = lr
atau bahkan:
n.left = lr
Kode Akhir
Dengan perubahan yang disebutkan di atas, fungsi Anda bisa jadi:
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
Hapus saja baris dengan parent
untuk mendapatkan versi single-threaded.