如何實(shí)現(xiàn)TreeNode的平衡

小樊
82
2024-09-03 12:11:59

要實(shí)現(xiàn)一個(gè)平衡的樹(shù)，通常我們會(huì)使用 AVL 樹(shù)或紅黑樹(shù)。這里我將簡(jiǎn)要介紹如何實(shí)現(xiàn)一個(gè)簡(jiǎn)單的 AVL 樹(shù)。

AVL 樹(shù)是一種自平衡二叉搜索樹(shù)，它的每個(gè)節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的高度差不超過(guò) 1。為了實(shí)現(xiàn)一個(gè) AVL 樹(shù)，我們需要定義一個(gè) TreeNode 類，并實(shí)現(xiàn)插入、刪除和平衡等操作。

首先，定義一個(gè) TreeNode 類：

class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

接下來(lái)，實(shí)現(xiàn)插入操作。在插入節(jié)點(diǎn)時(shí)，我們需要更新節(jié)點(diǎn)的高度，并檢查樹(shù)是否平衡。如果不平衡，我們需要進(jìn)行相應(yīng)的旋轉(zhuǎn)操作來(lái)恢復(fù)平衡。

class AVLTree:
    def insert(self, root, key):
        if not root:
            return TreeNode(key)
        elif key< root.key:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)

        root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))

        balance = self.get_balance(root)

        # Left Left Case
        if balance > 1 and key< root.left.key:
            return self.right_rotate(root)

        # Right Right Case
        if balance < -1 and key > root.right.key:
            return self.left_rotate(root)

        # Left Right Case
        if balance > 1 and key > root.left.key:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)

        # Right Left Case
        if balance < -1 and key< root.right.key:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

        return root

    def get_height(self, root):
        if not root:
            return 0
        return root.height

    def get_balance(self, root):
        if not root:
            return 0
        return self.get_height(root.left) - self.get_height(root.right)

    def left_rotate(self, z):
        y = z.right
        T2 = y.left

        y.left = z
        z.right = T2

        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))

        return y

    def right_rotate(self, y):
        x = y.left
        T2 = x.right

        x.right = y
        y.left = T2

        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))

        return x

類似地，你可以實(shí)現(xiàn)刪除操作，并在刪除節(jié)點(diǎn)時(shí)檢查樹(shù)是否平衡。如果不平衡，進(jìn)行相應(yīng)的旋轉(zhuǎn)操作來(lái)恢復(fù)平衡。

注意：這里給出的代碼僅作為實(shí)現(xiàn) AVL 樹(shù)的參考，你可能需要根據(jù)自己的需求進(jìn)行調(diào)整和優(yōu)化。

0 踩