مسیر رتبه‌برترشدن در کنکور ارشد مهندسی کامپیوتر و IT
ثبت‌نام رایگان
مدت زمان باقیمانده :
ثانیه -
دقیقه -
ساعت -
روز -
کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

درخت AVL ، درخت ای وی ال یا AVL tree

این صفحه عالی به معرفی و آموزش درخت AVL پرداخته و مواردی همچون ساخت درخت AVL، عملیات اصلی درختان AVL مانند حذف و درج در AVL و پیاده سازی درخت AVL را بررسی کرده

در علوم کامپیوترعلوم کامپیوتر یا کامپیوتر ساینس چیستعلوم کامپیوتر یا کامپیوتر ساینس چیستدر این صفحه به بررسی و موشکافی رشته علوم کامپیوتر اعم از بررسی بازار کار، گرایش‌ها، دروس و چارت درسی این رشته، میزان درآمد و حقوق فارغ التحصیلان این رشته و ادامه تحصیل در این رشته پرداخته‌ شده است.، درختان AVL یک ساختمان داده مهم هستند که‌ از درخت‌های جستجوی باینری خود متعادل‌کننده استفاده می‌کنند. هر گره در درخت AVL اطلاعات اضافی به‌ نام ضریب تعادل‌ را در خود دارد که‌ می‌تواند 1-، 0 یا 1+ باشد. این مقاله به بررسی درختان AVL، عملکرد آن‌ها و ارتباط آن‌ها در الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراوانالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد های مرتب‌سازی و جستجو می‌پردازد.

حتما بخوانید :
ساختمان داده چیست؟

عملیات اصلی درختان AVL

برای بررسی عملیات‌ در درختان AVL ابتدا باید مفهوم ضریب تعادل‌ را تعریف کنیم. ضریب تعادل یکی‌ از اجزای حیاتی درخت AVL است. این مفهوم به‌ تفاوت بین ارتفاع زیر درخت چپ‌ و‌ راست یک گره اشاره دارد. فرمول محاسبه ضریب تعادل مطابق زیر است:

ضریب تعادل = (ارتفاع زیر درخت سمت چپ - ارتفاع زیر درخت سمت راست) یا (ارتفاع زیر درخت سمت راست - ارتفاع زیر درخت سمت چپ)

ضریب تعادل همیشه باید 1-، 0 یا 1+ باشد تا اطمینان حاصل شود‌ که درخت AVL خود متعادل باقی می‌ماند. درخت زیر یک مثال برای درخت AVL است:

نمونه ای از یک درخت AVL

چرخش در درختان AVL

در عملیات چرخش، موقعیت گره‌های یک زیر درخت عوض می‌شود. سه نوع چرخش وجود دارد:

در ادامه به‌ بررسی هرکدام از این چرخش‌ها می‌پردازیم.

چرخش چپ

در چرخش چپ، آرایش گره‌ها در سمت راست به‌ آرایش گره چپ تبدیل می‌شود. مثال زیر را در‌ نظر بگیرید:

مثالی برای عمل چرخش به چپ

فرض کنید در درخت بالا، x و y هرکدام گره و A، B، C و D هرکدام زیر درخت باشند. مراحل چرخش به‌ چپ در این درخت به‌صورت زیر است.

اگر y زیر درخت سمت چپ دارد، x را به‌عنوان والد زیر درخت سمت چپ y اختصاص دهید:

x به عنوان والد زیردرخت سمت چپ y تخصیص داده شد

اگر والد x، NULL است، y را ریشه درخت کنید. اگر x فرزند چپ A است، y را فرزند چپ A قرار دهید؛ در غیر این‌ صورت y را به‌عنوان فرزند راست A قرار دهید.

قرار دادن y به عنوان فرزند راست A

در نهایت y را والد x قرار دهید.

قرار دادن y به عنوان والد x

چرخش راست

در چرخش سمت راست، آرایش گره‌ها در سمت چپ به‌ آرایش گره سمت راست تبدیل می‌شود. مثال زیر را در نظر بگیرید:

مثالی جهت انجام چرخش به راست

اگر x دارای زیر درخت راست است، y را به‌عنوان والد زیر درخت سمت راست x نسبت دهید.

نسبت دادن y به عنوان والد زیردرخت سمت راست

  1. اگر والد y، NULL است، ریشه درخت‌ را x قرار دهید.
  2. در غیر این صورت، اگر y فرزند راست والد خود یعنی A است، x را فرزند راست A قرار دهید.
  3. در غیر این صورت x را به‌عنوان فرزند سمت چپ A اختصاص دهید.

تخصیص x به عنوان فرزند سمت چپ A

x را والد y کنید:

قرار دادن x به عنوان والد y

چرخش چپ - راست و راست - چپ

در چرخش چپ - راست، ترتیب‌ها ابتدا به‌ چپ و سپس به‌ راست جابه‌جا می‌شوند. مثال زیر را در نظر بگیرید:

مثال برای چرخش چپ-راست

در این درخت ابتدا چرخش به‌سمت چپ‌را روی x-y انجام می‌دهیم:

چرخش به سمت چپ روی x-y

سپس چرخش به‌راست را روی y-z انجام می‌دهیم:

چرخش به سمت راست روی y-z

در چرخش راست - چپ، ترتیب‌ها ابتدا به‌ سمت راست و سپس به‌ چپ منتقل می‌شوند. مثال زیر را در نظر بگیرید:

مثالی برای چرخش راست-چپ

ابتدا چرخش راست‌ را روی x-y انجام می‌دهیم:

انجام چرخش راست روی x-y

سپس چرخش به‌ چپ‌ را روی z-y انجام می‌دهیم:

انجام چرخش چپ روی z-y

عملیات درج

یک گره جدید همیشه به‌عنوان یک گره برگ با ضریب تعادل برابر با 0 درج می‌شود. مثال زیر را در نظر بگیرید:

مثال برای انجام عملیات درج

فرض کنید می‌خواهیم گره 9 را به‌ این درخت اضافه کنیم. برای درج یک گره جدید با استفاده‌ از مراحل بازگشتی زیر، به‌ گره برگ مناسب بروید. کلید جدید‌ را با کلید ریشه درخت فعلی مقایسه کنید.

  1. اگر کلید جدید کوچک‌تر‌ از کلید ریشه است، الگوریتم درج‌ را در زیر درخت سمت چپ گره فعلی تا رسیدن به‌ گره برگ فراخوانی کنید.
  2. در غیر این‌ صورت، اگر کلید جدید بزرگ‌تر‌ از کلید ریشه است، الگوریتم درج‌ را در زیر درخت سمت راست گره فعلی تا رسیدن به‌ گره برگ فراخوانی کنید.
  3. در غیر این‌ صورت، گره برگ‌ را برگردانید.

رفتن به گره برگ مناسب جهت درج

پس‌ از رسیدن‌ به برگ، کلید برگ به‌دست‌آمده از مراحل بالا‌ را با کلید جدید مقایسه کنید:

  1. اگر کلید جدید کوچک‌تر‌ از کلید برگ است، گره جدید‌ را به‌عنوان فرزند سمت چپ برگ گره ایجاد کنید.
  2. در غیر این‌ صورت، یک گره جدید به‌عنوان فرزند سمت راست گره برگ ایجاد کنید.

ایجاد یک گره جدید به عنوان فرزند راست گره برگ

ضریب تعادل‌های درخت فعلی به‌ شکل زیر است:

ضریب تعادل درخت بعد از درج گره جدید

اگر گره‌ها نامتعادل هستند، گره‌ را باید دوباره متعادل کنید.

  1. اگر ضریب تعادل > 1 باشد، به‌ این معنی است که‌ ارتفاع زیر درخت سمت چپ بیشتر‌ از ارتفاع زیر درخت سمت راست است؛ بنابراین یک چرخش راست یا چرخش چپ - راست انجام دهید.
    • اگر کلید فرزند سمت چپ بزرگ‌تر‌ از کلید گره جدید است، چرخش به‌ راست انجام دهید.
    • در غیر این‌ صورت یک چرخش چپ - راست انجام دهید.
  2. اگر ضریب تعادل < 1- باشد، به‌ این معنی است که‌ ارتفاع زیر درخت سمت راست بیشتر‌ از ارتفاع زیر درخت سمت چپ است؛ بنابراین یک چرخش راست یا چرخش راست - چپ انجام دهید
    • اگر کلید فرزند سمت راست کوچک‌تر‌ از کلید گره جدید است، چرخش به‌ چپ انجام دهید.
    • در غیر این‌ صورت یک چرخش راست - چپ انجام دهید.

بر روی درخت فعلی ابتدا یک چرخش چپ انجام می‌دهیم:

انجام چرخش چپ

درخت به‌ این شکل درمی‌آید:

درخت فعلی بعد از چرخش به چپ

سپس یک چرخش به‌ راست انجام می‌دهیم:

انجام چرخش به سمت راست روی درخت فعلی

در این مرحله درخت متعادل شده است.

متعادل شدن درخت

عملیات حذف

یک گره همیشه به‌عنوان گره برگ حذف می‌شود. پس‌ا ز حذف یک گره، عوامل تعادل گره‌ها تغییر می‌کند. برای تعادل مجدد ضریب تعادل، چرخش‌های مناسب انجام می‌شوند. برای مثال درخت زیر‌ را در‌ نظر بگیرید:

مثالی برای انجام عملیات حذف

فرض کنید در این درخت می‌خواهیم گره 20 را حذف کنیم. سه حالت برای حذف یک گره وجود دارد:

  1. اگر گره‌ای که‌ باید حذف شود، گره برگ است (فرزندی ندارد)، گره‌ای که‌ باید حذف شود‌ را حذف کنید.
  2. اگر گره‌ای که‌ باید حذف شود دارای یک فرزند است، محتوای گره‌ای که‌ باید حذف شود‌ را بامحتوای فرزند جایگزین کنید و سپس فرزند‌ را حذف کنید.
  3. اگر گره‌ای که‌ باید حذف شود دو فرزند دارد، گره بعدی گره‌ای که‌ باید حذف شود‌ را در پیمایش Inorder پیدا کنید. (گره با حداقل مقدار کلید در زیر درخت سمت راست)

در این مثال گره 20 دو فرزند دارد و گره بعدی آن در پیمایش Inorder، گره 26 است. مقدار گره 20 را با 26 جایگزین می‌کنیم و گره 26 را حذف می‌کنیم:

جایگزینی گره 20 با 26 و حذف گره 26

حال ضریب تعادل گره‌ها‌ را دوباره محاسبه می‌کنیم:

محاسبه مجدد ضریب تعادل پس از حذف گره

اگر ضریب تعادل هریک‌ از گره‌ها برابر با 1- ،0 یا 1 نباشد، درخت را مجدداً متعادل کنید.

  1. اگر فاکتور تعادل گره فعلی > 1 باشد:
    • اگر ضریب تعادل فرزند چپ => 0 باشد، چرخش‌ را به‌ راست انجام دهید.
    • در غیر این‌ صورت چرخش چپ - راست‌ را انجام دهید.
  2. اگر ضریب تعادل گره فعلی < 1- باشد،
    • اگر ضریب تعادل فرزند راست =< 0 باشد، چرخش به‌ چپ‌ را انجام دهید.
    • در غیر این‌ صورت چرخش راست - چپ‌ را انجام دهید.

انجام چرخش مورد نظر روی درخت

درخت نهایی به‌شکل زیر خواهد بود:

نتیجه نهایی درخت پس از حذف گره

پیچیدگی زمانی عملیات های درخت AVL

پیچیدگی زمانیپیچیدگی زمانی الگوریتم چیست؟ معرفی نماد های مجانبیپیچیدگی زمانی الگوریتم چیست؟ معرفی نماد های مجانبیاین صفحه عالی به معرفی پیچیدگی زمانی الگوریتم پرداخته، همچنین انواع نماد های مجانبی و پیچیدگی زمانی های برخی از الگوریتم های مرتب سازی و جستجو را توضیح داده هر سه عملیات درج، حذف و جستجو در درخت AVL ازمرتبه O(Log n) است.

پیاده سازی درخت AVL

در ادامه به‌ پیاده‌سازی درخت AVL در زبان های برنامه نویسیزبان های برنامه نویسی چیست؟زبان های برنامه نویسی چیست؟این مقاله عالی توضیح داده که زبان های برنامه نویسی چیست؟ و انواع زبان های برنامه نویسی و بهترین زبان برنامه نویسی برای شروع و پردرآمدترین آنها را معرفی کرده مانند پایتونزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون (Python) چیست؟ این مقاله عالی به بررسی دلایل محبوبیت پایتون، موارد استفاده از پایتون و نحوه شروع به برنامه نویسی پایتون پرداخته و جاواجاوا چیست؟ تعریف، معنی و ویژگی های جاوا (java) از 0تا100جاوا چیست؟ تعریف، معنی و ویژگی های جاوا (java) از 0تا100جاوا یک زبان برنامه نویسی همه منظوره، مبتنی بر کلاس و شی گرا است که برای داشتن وابستگی های پیاده سازی کمتر طراحی شده است، زبان برنامه نویسی جاوا شبیه ++C است می‌پردازیم:

Python

# AVL tree implementation in Python


import sys

# Create a tree node
class TreeNode(object):
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1


class AVLTree(object):

    # Function to insert a node
    def insert_node(self, root, key):

        # Find the correct location and insert the node
        if not root:
            return TreeNode(key)
        elif key < root.key:
            root.left = self.insert_node(root.left, key)
        else:
            root.right = self.insert_node(root.right, key)

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

        # Update the balance factor and balance the tree
        balanceFactor = self.getBalance(root)
        if balanceFactor > 1:
            if key < root.left.key:
                return self.rightRotate(root)
            else:
                root.left = self.leftRotate(root.left)
                return self.rightRotate(root)

        if balanceFactor < -1:
            if key > root.right.key:
                return self.leftRotate(root)
            else:
                root.right = self.rightRotate(root.right)
                return self.leftRotate(root)

        return root

    # Function to delete a node
    def delete_node(self, root, key):

        # Find the node to be deleted and remove it
        if not root:
            return root
        elif key < root.key:
            root.left = self.delete_node(root.left, key)
        elif key > root.key:
            root.right = self.delete_node(root.right, key)
        else:
            if root.left is None:
                temp = root.right
                root = None
                return temp
            elif root.right is None:
                temp = root.left
                root = None
                return temp
            temp = self.getMinValueNode(root.right)
            root.key = temp.key
            root.right = self.delete_node(root.right,
                                          temp.key)
        if root is None:
            return root

        # Update the balance factor of nodes
        root.height = 1 + max(self.getHeight(root.left),
                              self.getHeight(root.right))

        balanceFactor = self.getBalance(root)

        # Balance the tree
        if balanceFactor > 1:
            if self.getBalance(root.left) >= 0:
                return self.rightRotate(root)
            else:
                root.left = self.leftRotate(root.left)
                return self.rightRotate(root)
        if balanceFactor < -1:
            if self.getBalance(root.right) <= 0:
                return self.leftRotate(root)
            else:
                root.right = self.rightRotate(root.right)
                return self.leftRotate(root)
        return root

    # Function to perform left rotation
    def leftRotate(self, z):
        y = z.right
        T2 = y.left
        y.left = z
        z.right = T2
        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 y

    # Function to perform right rotation
    def rightRotate(self, z):
        y = z.left
        T3 = y.right
        y.right = z
        z.left = T3
        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 y

    # Get the height of the node
    def getHeight(self, root):
        if not root:
            return 0
        return root.height

    # Get balance factore of the node
    def getBalance(self, root):
        if not root:
            return 0
        return self.getHeight(root.left) - self.getHeight(root.right)

    def getMinValueNode(self, root):
        if root is None or root.left is None:
            return root
        return self.getMinValueNode(root.left)

    def preOrder(self, root):
        if not root:
            return
        print("{0} ".format(root.key), end="")
        self.preOrder(root.left)
        self.preOrder(root.right)

    # Print the tree
    def printHelper(self, currPtr, indent, last):
        if currPtr != None:
            sys.stdout.write(indent)
            if last:
                sys.stdout.write("R----")
                indent += "     "
            else:
                sys.stdout.write("L----")
                indent += "|    "
            print(currPtr.key)
            self.printHelper(currPtr.left, indent, False)
            self.printHelper(currPtr.right, indent, True)


myTree = AVLTree()
root = None
nums = [33, 13, 52, 9, 21, 61, 8, 11]
for num in nums:
    root = myTree.insert_node(root, num)
myTree.printHelper(root, "", True)
key = 13
root = myTree.delete_node(root, key)
print("After Deletion: ")
myTree.printHelper(root, "", True)

Java

// AVL tree implementation in Java

// Create node
class Node {
  int item, height;
  Node left, right;

  Node(int d) {
    item = d;
    height = 1;
  }
}

// Tree class
class AVLTree {
  Node root;

  int height(Node N) {
    if (N == null)
      return 0;
    return N.height;
  }

  int max(int a, int b) {
    return (a > b) ? a : b;
  }

  Node rightRotate(Node y) {
    Node x = y.left;
    Node T2 = x.right;
    x.right = y;
    y.left = T2;
    y.height = max(height(y.left), height(y.right)) + 1;
    x.height = max(height(x.left), height(x.right)) + 1;
    return x;
  }

  Node leftRotate(Node x) {
    Node y = x.right;
    Node T2 = y.left;
    y.left = x;
    x.right = T2;
    x.height = max(height(x.left), height(x.right)) + 1;
    y.height = max(height(y.left), height(y.right)) + 1;
    return y;
  }

  // Get balance factor of a node
  int getBalanceFactor(Node N) {
    if (N == null)
      return 0;
    return height(N.left) – height(N.right);
  }

  // Insert a node
  Node insertNode(Node node, int item) {

    // Find the position and insert the node
    if (node == null)
      return (new Node(item));
    if (item  node.item)
      node.right = insertNode(node.right, item);
    else
      return node;

    // Update the balance factor of each node
    // And, balance the tree
    node.height = 1 + max(height(node.left), height(node.right));
    int balanceFactor = getBalanceFactor(node);
    if (balanceFactor > 1) {
      if (item  node.right.item) {
        return leftRotate(node);
      } else if (item < node.right.item) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
      }
    }
    return node;
  }

  Node nodeWithMimumValue(Node node) {
    Node current = node;
    while (current.left != null)
      current = current.left;
    return current;
  }

  // Delete a node
  Node deleteNode(Node root, int item) {

    // Find the node to be deleted and remove it
    if (root == null)
      return root;
    if (item  root.item)
      root.right = deleteNode(root.right, item);
    else {
      if ((root.left == null) || (root.right == null)) {
        Node temp = null;
        if (temp == root.left)
          temp = root.right;
        else
          temp = root.left;
        if (temp == null) {
          temp = root;
          root = null;
        } else
          root = temp;
      } else {
        Node temp = nodeWithMimumValue(root.right);
        root.item = temp.item;
        root.right = deleteNode(root.right, temp.item);
      }
    }
    if (root == null)
      return root;

    // Update the balance factor of each node and balance the tree
    root.height = max(height(root.left), height(root.right)) + 1;
    int balanceFactor = getBalanceFactor(root);
    if (balanceFactor > 1) {
      if (getBalanceFactor(root.left) >= 0) {
        return rightRotate(root);
      } else {
        root.left = leftRotate(root.left);
        return rightRotate(root);
      }
    }
    if (balanceFactor < -1) {
      if (getBalanceFactor(root.right) = 0) {
        return leftRotate(root);
      } else {
        root.right = rightRotate(root.right);
        return leftRotate(root);
      }
    }
    return root;
  }

  void preOrder(Node node) {
    if (node != null) {
      System.out.print(node.item + “ “);
      preOrder(node.left);
      preOrder(node.right);
    }
  }

  // Print the tree
  private void printTree(Node currPtr, String indent, boolean last) {
    if (currPtr != null) {
      System.out.print(indent);
      if (last) {
        System.out.print(“R----");
        indent += “   “;
      } else {
        System.out.print(“L----");
        indent += “|  “;
      }
      System.out.println(currPtr.item);
      printTree(currPtr.left, indent, false);
      printTree(currPtr.right, indent, true);
    }
  }

  // Driver code
  public static void main(String[] args) {
    AVLTree tree = new AVLTree();
    tree.root = tree.insertNode(tree.root, 33);
    tree.root = tree.insertNode(tree.root, 13);
    tree.root = tree.insertNode(tree.root, 53);
    tree.root = tree.insertNode(tree.root, 9);
    tree.root = tree.insertNode(tree.root, 21);
    tree.root = tree.insertNode(tree.root, 61);
    tree.root = tree.insertNode(tree.root, 8);
    tree.root = tree.insertNode(tree.root, 11);
    tree.printTree(tree.root, “”, true);
    tree.root = tree.deleteNode(tree.root, 13);
    System.out.println(“After Deletion: “);
    tree.printTree(tree.root, “”, true);
  }
}

کاربردهای درخت AVL

کاربردهای درخت AVL شامل موارد زیر است:

جمع‌بندی

درختان AVL یک ساختمان داده حیاتی برای ذخیره‌سازی و بازیابی بهینه اطلاعات در علوم کامپیوتر هستند. این درختان خود‌ متعادل‌ کننده هستند و امکان جستجوی سریع، عملیات درج/حذف و سازگاری‌ را فراهم می‌کنند. در این مقاله به‌ مفهوم درختان AVL، یک ساختمان داده درخت جستجوی باینری متعادل که‌ معمولاً در علوم کامپیوتر استفاده می‌شود پرداختیم؛ همچنین به‌ بررسی عملیات‌ اساسی این نوع درختان پرداختیم و به‌ پیاده‌سازی آن‌ها اشاره کردیم.

تفاوت بین درخت جستجوی باینری و درخت AVL چیست؟

در درخت جستجوی باینری، درج و حذف آسان است؛ زیرا نیازی‌ به چرخش نیست. در درخت AVL، درج و حذف پیچیده هستند و به‌ فرایندهای متعددی برای متعادل‌کردن درخت نیاز دارند.

چرا AVL بهتر از BST است؟

درخت AVL همیشه با ارتفاع متعادل است و ارتفاع آن همیشه O(Log n) است که‌ در‌ آن n تعداد کل گره‌های درخت است. پیچیدگی‌های زمانی همه عملیات‌ در AVL بهتر‌از BST است؛ زیرا بدترین پیچیدگی زمانی درخت AVL در تمام عملیات‌ به‌صورت O(Log n) است، درحالی‌که در BST، بدترین حالت‌ از مرتبه O(n) است.

در چه مواردی از درخت AVL استفاده می‌شود؟

از آن برای نمایه‌سازی رکوردهای عظیم در پایگاه داده و همچنین جستجوی مؤثر در آن استفاده می‌شود. درختان AVL برای همه انواع مجموعه‌های درون حافظه ازجمله مجموعه‌ها و دیکشنری‌ها استفاده می‌شوند. کاربرد دیگر این درختان، برنامه‌های کاربردی پایگاه داده است، جایی‌ که درج و حذف کمتر رایج است؛ اما جستجوی مکرر داده‌ها متداول است.

پیچیدگی زمانی درخت AVL چقدر است؟

همان‌طور که‌ از ارتفاع درخت AVL عبور می‌کنیم، در این مورد، پیچیدگی زمانی O(Log n) خواهد بود. بدترین حالت زمانی است که‌ درخت پس‌ از اضافه‌کردن گره جدید از تعادل خارج می‌شود و چرخش لازم است. پیچیدگی زمانی در این مورد نیز O (Log n) است.

امتیازدهی5 1 1 1 1 1 1 1 1 1 15.00 امتیاز (1 امتیاز)
اشتراک
بارگذاری نظرات
تلگرام اینستاگرام