Rotasi kanan dan kiri pohon dengan python

Aug 19 2020

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_12itu 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

trincot Aug 19 2020 at 18:59

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.leftakan tetap sama dengan lyang ada tpada saat itu, dan Anda memang tertinggal dengan lingkaran di pohon Anda.

2) Ulir ganda

Pohon Anda berulir ganda, yaitu, pohon juga memiliki parenttautan. Tetapi ini tidak diperbarui dalam rightRotatefungsi Anda . Jadi lakukan tanpa parenttautan (yang lebih disukai), atau sesuaikan kode Anda sehingga parenttautan 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 parentuntuk mendapatkan versi single-threaded.