Tree ใน Data Structures - การปรับสมดุล AVL Tree

ในการพัฒนาโปรแกรมที่ซับซ้อน การใช้งานโครงสร้างข้อมูลที่มีประสิทธิภาพก็เป็นสิ่งสำคัญ หนึ่งในโครงสร้างข้อมูลที่นิยมใช้งานและมีความสำคัญคือ "Tree" ในบทความนี้ เราจะพูดถึง "AVL Tree" ซึ่งเป็น Balanced Binary Search Tree (BST) ประเภทหนึ่งที่มีประโยชน์ในการรักษาความสมดุลในความสูงของต้นไม้เพื่อเพิ่มประสิทธิภาพในกระบวนการค้นหา แทรก และลบข้อมูล

AVL Tree คืออะไร?

AVL Tree ถูกพัฒนาขึ้นในปี 1962 โดยนักคณิตศาสตร์ G. M. Adelson-Velsky และ E. M. Landis ซึ่งชื่อ AVL มาจากนามสกุลของพวกเขา AVL Tree นั้นเป็นการปรับปรุง Binary Search Tree (BST) เพื่อรักษาสมดุล ทำให้การปฏิบัติการต่างๆ เกิดขึ้นได้ในเวลา O(log n)

หนึ่งในคุณสมบัติเด่นของ AVL Tree คือ ที่กำหนดให้ "Height Balance" หรือความต่างของความสูงของ sub-trees ทางซ้ายและขวา ของโหนดใดๆ ต้องไม่เกิน 1 นี่คือปัจจัยที่ทำให้ AVL Tree สมดุลเสมอ

ทำไมต้องใช้ AVL Tree?

ใน BST ธรรมดา เมื่อมีการเพิ่มหรือลบข้อมูลหลายๆ ครั้ง โครงสร้างของต้นไม้อาจเอียงไปทางใดทางหนึ่งมากเกินไป ทำให้การค้นหาอาจใช้เวลามากขึ้นใกล้เคียง O(n) และเสียประสิทธิภาพ AVL Tree เข้ามาแก้ปัญหานี้ด้วยการปรับสมดุลให้ทุกครั้งที่มีการเปลี่ยนแปลงโครงสร้างการแทรกหรือลบข้อมูล

การปรับสมดุลของ AVL Tree

ในการรักษาสมดุลของ AVL Tree เราใช้การหมุน (Rotation) แบ่งออกเป็น 4 แบบคือ

เรามาดูตัวอย่างการหมุนและปรับสมดุล AVL Tree กันดีกว่า

ตัวอย่างการใช้งาน AVL Tree

ลองมาดูโค้ดสำหรับการทำการปรับสมดุล AVL Tree ในการแทรก (insert) ข้อมูลภาษา Python กัน

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

class AVLTree:

    def insert(self, root, key):

        # Step 1: Perform normal BST insert
        if not root:
            return Node(key)
        elif key < root.key:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)

        # Step 2: Update height of current node
        root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))

        # Step 3: Get the balance factor
        balance = self.getBalance(root)

        # Step 4: If the node is unbalanced, then try out the 4 cases
        # Left Left Case
        if balance > 1 and key < root.left.key:
            return self.rightRotate(root)

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

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

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

        return root

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

        # Perform rotation
        y.left = z
        z.right = T2

        # Update heights
        z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))

        # Return the new root
        return y

    def rightRotate(self, z):
        y = z.left
        T3 = y.right

        # Perform rotation
        y.right = z
        z.left = T3

        # Update heights
        z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))

        # Return the new root
        return y

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

    def getBalance(self, root):
        if not root:
            return 0
        return self.getHeight(root.left) - self.getHeight(root.right)

ในโค้ดตัวอย่างด้านบน การแทรกข้อมูลเข้าไปใน AVL Tree จะดำเนินการเหมือน BST ปกติก่อน จากนั้นจะปรับสมดุลด้วยการหมุนหากต้นไม้มีการเสียสมดุล

สรุป

AVL Tree เป็นโครงสร้างข้อมูลที่มีประโยชน์มากในหลายกรณีที่ต้องการความเร็วในการปฏิบัติการหลายๆ ชนิด เช่น การค้นหา แทรก และลบ เนื่องจากให้เวลาที่ใกล้เคียง O(log n) อยู่ตลอด การเรียนรู้ AVL Tree จึงเป็นเรื่องที่น่าสนใจสำหรับผู้ที่สนใจในการนำโครงสร้างข้อมูลไปปรับใช้ในงานโปรแกรมที่ต้องการความรวดเร็วและมีปริมาณข้อมูลจำนวนมาก

หากคุณสนใจเรียนรู้เพิ่มเติมเกี่ยวกับการโปรแกรมและโครงสร้างข้อมูลต่างๆ สามารถศึกษาเพิ่มเติมที่ Expert-Programming-Tutor (EPT) ซึ่งเป็นแหล่งการศึกษาเกี่ยวกับการเขียนโปรแกรมที่ครบวงจรและน่าสนใจ!

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง

หากเจอข้อผิดพลาด หรือต้องการพูดคุย ติดต่อได้ที่ https://m.me/expert.Programming.Tutor/