Tree ใน Data Structures - การสร้าง AVL Tree

 

# เรียนรู้โครงสร้างข้อมูล Tree กับการสร้าง AVL Tree

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

 

Tree ในโครงสร้างข้อมูล

Tree เป็นโครงสร้างข้อมูลที่มีลักษณะเป็นลำดับชั้น (hierarchical) ประกอบไปด้วยโหนด (nodes) ซึ่งโหนดจะเชื่อมโยงกันด้วยขอบ (edges) มีคุณลักษณะสำคัญคือมีโหนดราก (root node) ที่เป็นจุดเริ่มต้น จากนั้นสามารถมีโหนดย่อย (child nodes) และโหนดผู้ปกครอง (parent node) จนถึงโหนดยอด (leaf nodes) ที่ไม่มีโหนดย่อย

ประเภทของ Tree

- Binary Tree: เป็น Tree ที่แต่ละโหนดมีโหนดย่อยได้ไม่เกินสองโหนด - Binary Search Tree (BST): เป็น Binary Tree ที่โหนดด้านซ้ายจะมีค่าน้อยกว่าโหนดพ่อ ส่วนโหนดด้านขวาจะมีค่ามากกว่าโหนดพ่อ - AVL Tree: เป็น Binary Search Tree ที่มีความสมดุลของความสูงระหว่างโหนดซ้ายและขวา ซึ่งจะอธิบายเพิ่มเติมในส่วนถัดไป

 

AVL Tree คืออะไร?

AVL Tree ถูกพัฒนาขึ้นเพื่อแก้ไขปัญหาของความไม่สมดุลใน Binary Search Tree การไม่สมดุลนั้นส่งผลต่อประสิทธิภาพในการค้นหา แทรก และลบข้อมูล โดย AVL Tree ได้รับการออกแบบให้รักษาสมดุลของทุกโหนดผ่านการหมุน (rotations) เพื่อรักษาให้ส่วนสูงของโหนดทางซ้ายและขวาต่างกันไม่เกิน 1

การหมุนใน AVL Tree

1. การหมุนแบบซ้าย (Left Rotation): ใช้เมื่อโหนดลูกแฝงทางขวาของโหนดหลักเกิดสูงเกินไป 2. การหมุนแบบขวา (Right Rotation): ใช้เมื่อโหนดลูกแฝงทางซ้ายของโหนดหลักเกิดสูงเกินไป 3. การหมุนแบบซ้าย-ขวา (Left-Right Rotation): เป็นการหมุนสองขั้นตอน เริ่มจากการหมุนแบบซ้ายที่โหนดย่อย และตามด้วยการหมุนแบบขวาที่โหนดหลัก 4. การหมุนแบบขวา-ซ้าย (Right-Left Rotation): เป็นการหมุนสองขั้นตอน เริ่มจากการหมุนแบบขวาที่โหนดย่อย และตามด้วยการหมุนแบบซ้ายที่โหนดหลัก

ขั้นตอนการแทรกใน AVL Tree

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

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

def insert(root, key):
    if not root:
        return Node(key)
    elif key < root.val:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)

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

    balance = get_balance(root)

    if balance > 1 and key < root.left.val:
        return rotate_right(root)
    if balance < -1 and key > root.right.val:
        return rotate_left(root)
    if balance > 1 and key > root.left.val:
        root.left = rotate_left(root.left)
        return rotate_right(root)
    if balance < -1 and key < root.right.val:
        root.right = rotate_right(root.right)
        return rotate_left(root)

    return root

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

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

def rotate_left(z):
    y = z.right
    T2 = y.left
    y.left = z
    z.right = T2
    z.height = 1 + max(get_height(z.left), get_height(z.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    return y

def rotate_right(y):
    x = y.left
    T2 = x.right
    x.right = y
    y.left = T2
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    x.height = 1 + max(get_height(x.left), get_height(x.right))
    return x

 

ประโยชน์ของการใช้ AVL Tree

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

 

สรุป

AVL Tree เป็นหนึ่งในตัวอย่างที่ยอดเยี่ยมของการปรับปรุงและปรับสมดุลของ Tree ที่ไม่เพียงทำให้การดำเนินการสแกนหา แทรก และลบมีประสิทธิภาพสูง แต่ยังสามารถมีบทเรียนในเรื่องการออกแบบ ระบบ หรือซอฟต์แวร์เมื่อต้องเผชิญกับข้อมูลจำนวนมาก หากคุณสนใจที่จะเรียนรู้และพัฒนาทักษะในเรื่องของโครงสร้างข้อมูลและการเขียนโปรแกรม สามารถศึกษาต่อได้ที่ Expert Programming Tutor (EPT) ที่มีหลักสูตรหลากหลายรอคุณในการก้าวเข้าสู่โลกของการเขียนโปรแกรมอย่างมืออาชีพ!

 

 

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

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