درخت دودویی، آموزش درخت دودویی در ساختمان داده

درخت باینری یا دودویی یک ساختمان دادهآموزش ساختمان داده و الگوریتمهر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتم‌ها و کاربردها فراهم می‌کند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است درختی است که در آن هر گره والد می‌تواند حداکثر دو فرزند داشته باشد. هر گره از یک درخت دودویی از سه مورد تشکیل شده است:

آیتم داده
آدرس فرزند چپ
آدرس فرزند راست

در ادامه مقاله به بررسی انواع درخت دودویی، نمایش و نحوه پیاده‌ سازی درخت دودویی و کاربرد آن خواهیم پرداخت.

انواع درخت دودویی

انواع مختلفی از درختان دودویی وجود دارد و هر یک از این انواع درختان دودویی ویژگی‌های منحصر به فردی دارند. در اینجا هر یک از انواع درخت دودویی به شکل خلاصه آورده شده است:

درخت دودویی پر(Full)

درخت باینری پر نوع خاصی از درخت دودویی است که در آن هر گره والد/گره داخلی دارای دو یا بدون فرزند است.

درخت دودویی عالی(Perfect)

درخت دودویی عالی نوعی درخت دودویی است که در آن هر گره داخلی دقیقاً دو گره فرزند دارد و تمام گره‌های برگ در یک سطح هستند.

درخت دودویی کامل(Complete)

یک درخت باینری کامل درست مانند یک درخت باینری پر است اما با سه تفاوت عمده:

هر سطح باید پر شود.
تمام عناصر برگ باید به سمت چپ متمایل شوند.
عنصر برگ آخر ممکن است خواهر یا برادر راست نداشته باشد، یعنی یک درخت باینری کامل لازم نیست یک درخت باینری پر باشد.

درخت منحط یا پاتولوژیک

درخت منحط یا پاتولوژیک درختی است که هر گره دارای تک فرزند چپ یا راست است.

درخت دودویی اریب

درخت دودویی اریب، درختی منحط است که در آن درخت تمام گره های داخلی یا دارای فرزند راست هستند یا چپ. بنابراین، دو نوع درخت دودویی اریب وجود دارد: درخت دوتایی با انحراف چپ و درخت دوتایی با انحراف راست.

درخت دودویی متعادل

این یک نوع درخت باینری است که در آن اختلاف بین ارتفاع زیردرخت چپ و راست برای هر گره 0 یا 1 است.

حتما بخوانید :

پیمایش درخت، آموزش پیمایش درخت دودویی

نمایش درخت دودویی

یک گره از یک درخت دودویی با ساختاری حاوی یک آیتم داده و دو اشاره گر به ساختارهای دیگر از همان نوع نشان داده می شود.

struct node
{
 int data;
 struct node *left;
 struct node *right;
};

struct node
{
 int data;
 struct node *left;
 struct node *right;
};

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

Python

# Binary Tree in Python
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

    # Traverse preorder
    def traversePreOrder(self):
        print(self.val, end=' ')
        if self.left:
            self.left.traversePreOrder()
        if self.right:
            self.right.traversePreOrder()

    # Traverse inorder
    def traverseInOrder(self):
        if self.left:
            self.left.traverseInOrder()
        print(self.val, end=' ')
        if self.right:
            self.right.traverseInOrder()

    # Traverse postorder
    def traversePostOrder(self):
        if self.left:
            self.left.traversePostOrder()
        if self.right:
            self.right.traversePostOrder()
        print(self.val, end=' ')
root = Node(1)

root.left = Node(2)
root.right = Node(3)

root.left.left = Node(4)

print("Pre order Traversal: ", end="")
root.traversePreOrder()
print("\nIn order Traversal: ", end="")
root.traverseInOrder()
print("\nPost order Traversal: ", end="")
root.traversePostOrder()

# Binary Tree in Python

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

    # Traverse preorder
    def traversePreOrder(self):
        print(self.val, end=' ')
        if self.left:
            self.left.traversePreOrder()
        if self.right:
            self.right.traversePreOrder()

    # Traverse inorder
    def traverseInOrder(self):
        if self.left:
            self.left.traverseInOrder()
        print(self.val, end=' ')
        if self.right:
            self.right.traverseInOrder()

    # Traverse postorder
    def traversePostOrder(self):
        if self.left:
            self.left.traversePostOrder()
        if self.right:
            self.right.traversePostOrder()
        print(self.val, end=' ')


root = Node(1)

root.left = Node(2)
root.right = Node(3)

root.left.left = Node(4)

print("Pre order Traversal: ", end="")
root.traversePreOrder()
print("\nIn order Traversal: ", end="")
root.traverseInOrder()
print("\nPost order Traversal: ", end="")
root.traversePostOrder()

Java

// Binary Tree in Java

// Node creation
class Node {
  int key;
  Node left, right;

  public Node(int item) {
  key = item;
  left = right = null;
  }
}

class BinaryTree {
  Node root;

  BinaryTree(int key) {
  root = new Node(key);
  }

  BinaryTree() {
  root = null;
  }

  // Traverse Inorder
  public void traverseInOrder(Node node) {
  if (node != null) {
    traverseInOrder(node.left);
    System.out.print(" " + node.key);
    traverseInOrder(node.right);
  }
  }

  // Traverse Postorder
  public void traversePostOrder(Node node) {
  if (node != null) {
    traversePostOrder(node.left);
    traversePostOrder(node.right);
    System.out.print(" " + node.key);
  }
  }

  // Traverse Preorder
  public void traversePreOrder(Node node) {
  if (node != null) {
    System.out.print(" " + node.key);
    traversePreOrder(node.left);
    traversePreOrder(node.right);
  }
  }

  public static void main(String[] args) {
  BinaryTree tree = new BinaryTree();

  tree.root = new Node(1);
  tree.root.left = new Node(2);
  tree.root.right = new Node(3);
  tree.root.left.left = new Node(4);

  System.out.print("Pre order Traversal: ");
  tree.traversePreOrder(tree.root);
  System.out.print("\nIn order Traversal: ");
  tree.traverseInOrder(tree.root);
  System.out.print("\nPost order Traversal: ");
  tree.traversePostOrder(tree.root);
  }
}

// Binary Tree in Java

// Node creation
class Node {
  int key;
  Node left, right;

  public Node(int item) {
  key = item;
  left = right = null;
  }
}

class BinaryTree {
  Node root;

  BinaryTree(int key) {
  root = new Node(key);
  }

  BinaryTree() {
  root = null;
  }

  // Traverse Inorder
  public void traverseInOrder(Node node) {
  if (node != null) {
    traverseInOrder(node.left);
    System.out.print(" " + node.key);
    traverseInOrder(node.right);
  }
  }

  // Traverse Postorder
  public void traversePostOrder(Node node) {
  if (node != null) {
    traversePostOrder(node.left);
    traversePostOrder(node.right);
    System.out.print(" " + node.key);
  }
  }

  // Traverse Preorder
  public void traversePreOrder(Node node) {
  if (node != null) {
    System.out.print(" " + node.key);
    traversePreOrder(node.left);
    traversePreOrder(node.right);
  }
  }

  public static void main(String[] args) {
  BinaryTree tree = new BinaryTree();

  tree.root = new Node(1);
  tree.root.left = new Node(2);
  tree.root.right = new Node(3);
  tree.root.left.left = new Node(4);

  System.out.print("Pre order Traversal: ");
  tree.traversePreOrder(tree.root);
  System.out.print("\nIn order Traversal: ");
  tree.traverseInOrder(tree.root);
  System.out.print("\nPost order Traversal: ");
  tree.traversePostOrder(tree.root);
  }
}

C

// Tree traversal in C

#include 
#include 

struct node {
  int item;
  struct node* left;
  struct node* right;
};

// Inorder traversal
void inorderTraversal(struct node* root) {
  if (root == NULL) return;
  inorderTraversal(root->left);
  printf("%d ->", root->item);
  inorderTraversal(root->right);
}

// Preorder traversal
void preorderTraversal(struct node* root) {
  if (root == NULL) return;
  printf("%d ->", root->item);
  preorderTraversal(root->left);
  preorderTraversal(root->right);
}

// Postorder traversal
void postorderTraversal(struct node* root) {
  if (root == NULL) return;
  postorderTraversal(root->left);
  postorderTraversal(root->right);
  printf("%d ->", root->item);
}

// Create a new Node
struct node* createNode(value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->item = value;
  newNode->left = NULL;
  newNode->right = NULL;

  return newNode;
}

// Insert on the left of the node
struct node* insertLeft(struct node* root, int value) {
  root->left = createNode(value);
  return root->left;
}

// Insert on the right of the node
struct node* insertRight(struct node* root, int value) {
  root->right = createNode(value);
  return root->right;
}

int main() {
  struct node* root = createNode(1);
  insertLeft(root, 2);
  insertRight(root, 3);
  insertLeft(root->left, 4);

  printf("Inorder traversal \n");
  inorderTraversal(root);

  printf("\nPreorder traversal \n");
  preorderTraversal(root);

  printf("\nPostorder traversal \n");
  postorderTraversal(root);
}

// Tree traversal in C

#include 
#include 

struct node {
  int item;
  struct node* left;
  struct node* right;
};

// Inorder traversal
void inorderTraversal(struct node* root) {
  if (root == NULL) return;
  inorderTraversal(root->left);
  printf("%d ->", root->item);
  inorderTraversal(root->right);
}

// Preorder traversal
void preorderTraversal(struct node* root) {
  if (root == NULL) return;
  printf("%d ->", root->item);
  preorderTraversal(root->left);
  preorderTraversal(root->right);
}

// Postorder traversal
void postorderTraversal(struct node* root) {
  if (root == NULL) return;
  postorderTraversal(root->left);
  postorderTraversal(root->right);
  printf("%d ->", root->item);
}

// Create a new Node
struct node* createNode(value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->item = value;
  newNode->left = NULL;
  newNode->right = NULL;

  return newNode;
}

// Insert on the left of the node
struct node* insertLeft(struct node* root, int value) {
  root->left = createNode(value);
  return root->left;
}

// Insert on the right of the node
struct node* insertRight(struct node* root, int value) {
  root->right = createNode(value);
  return root->right;
}

int main() {
  struct node* root = createNode(1);
  insertLeft(root, 2);
  insertRight(root, 3);
  insertLeft(root->left, 4);

  printf("Inorder traversal \n");
  inorderTraversal(root);

  printf("\nPreorder traversal \n");
  preorderTraversal(root);

  printf("\nPostorder traversal \n");
  postorderTraversal(root);
}

C++

// Binary Tree in C++

#include 

#include 

using namespace std;

struct node {
  int data;
  struct node *left;
  struct node *right;
};

// New node creation
struct node *newNode(int data) {
  struct node *node = (struct node *)malloc(sizeof(struct node));

  node->data = data;

  node->left = NULL;
  node->right = NULL;
  return (node);
}

// Traverse Preorder
void traversePreOrder(struct node *temp) {
  if (temp != NULL) {
    cout  " " data;
    traversePreOrder(temp->left);
    traversePreOrder(temp->right);
  }
}

// Traverse Inorder
void traverseInOrder(struct node *temp) {
  if (temp != NULL) {
    traverseInOrder(temp->left);
    cout  " " data;
    traverseInOrder(temp->right);
  }
}

// Traverse Postorder
void traversePostOrder(struct node *temp) {
  if (temp != NULL) {
    traversePostOrder(temp->left);
    traversePostOrder(temp->right);
    cout  " " data;
  }
}

int main() {
  struct node *root = newNode(1);
  root->left = newNode(2);
  root->right = newNode(3);
  root->left->left = newNode(4);

  cout  "preorder traversal: ";
  traversePreOrder(root);
  cout  "\nInorder traversal: ";
  traverseInOrder(root);
  cout  "\nPostorder traversal: ";
  traversePostOrder(root);
}

// Binary Tree in C++

#include 

#include 

using namespace std;

struct node {
  int data;
  struct node *left;
  struct node *right;
};

// New node creation
struct node *newNode(int data) {
  struct node *node = (struct node *)malloc(sizeof(struct node));

  node->data = data;

  node->left = NULL;
  node->right = NULL;
  return (node);
}

// Traverse Preorder
void traversePreOrder(struct node *temp) {
  if (temp != NULL) {
    cout  " " data;
    traversePreOrder(temp->left);
    traversePreOrder(temp->right);
  }
}

// Traverse Inorder
void traverseInOrder(struct node *temp) {
  if (temp != NULL) {
    traverseInOrder(temp->left);
    cout  " " data;
    traverseInOrder(temp->right);
  }
}

// Traverse Postorder
void traversePostOrder(struct node *temp) {
  if (temp != NULL) {
    traversePostOrder(temp->left);
    traversePostOrder(temp->right);
    cout  " " data;
  }
}

int main() {
  struct node *root = newNode(1);
  root->left = newNode(2);
  root->right = newNode(3);
  root->left->left = newNode(4);

  cout  "preorder traversal: ";
  traversePreOrder(root);
  cout  "\nInorder traversal: ";
  traverseInOrder(root);
  cout  "\nPostorder traversal: ";
  traversePostOrder(root);
}

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

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

الگوریتم‌های جستجو: الگوریتم‌های جستجوی باینری از ساختار درخت‌های دودویی برای جستجوی مؤثر عنصر خاصی استفاده می‌کنند. جستجو را می توان در پیچیدگی زمانیپیچیدگی زمانی الگوریتم چیست؟ معرفی نماد های مجانبیاین صفحه عالی به معرفی پیچیدگی زمانی الگوریتم پرداخته، همچنین انواع نماد های مجانبی و پیچیدگی زمانی های برخی از الگوریتم های مرتب سازی و جستجو را توضیح داده O(log n) انجام داد، که n تعداد گره‌های درخت است.
الگوریتم‌های مرتب‌سازی: درخت‌های باینری را می‌توان برای پیاده‌سازی کارآمد، مانند مرتب‌سازی درخت جستجوی دودویی و مرتب‌سازی پشتهساختمان داده پشته ⚡️ پشته چیست؟ کاربرد پشته در ساختمان دادهاین مقاله عالی توضیح داده که پشته چیست و کاربرد پشته در ساختمان داده چیست، همچنین نحوه کارکرد پشته، پیاده سازی پشته و عملیات های پشته را معرفی کرده ای استفاده کرد.
سیستم‌های پایگاه دادهپایگاه داده چیست؟ – انواع، مفاهیم و کاربردهاپایگاه داده چیست؟ این مقاله به بررسی این موضوع و همچنین انواع پایگاه داده، کاربردهای پایگاه داده، محبوب ترین پایگاه های داده و اجزای اصلی پایگاه داده پرداخته : درخت های باینری را می توان برای ذخیره داده‌ها در یک سیستم پایگاه داده استفاده کرد که هر گره نشان دهنده یک رکورد است. این کار امکان عملیات جستجوی کارآمد را فراهم می کند و سیستم پایگاه داده را قادر می‌سازد تا حجم زیادی از داده‌ها را مدیریت کند.
سیستم های مدیریت فایل: درخت های باینری را می‌توان برای پیاده‌سازی سیستم های مدیریت فایل استفاده کرد، بصورتیکه که هر گره نشان‌دهنده یک فهرست یا فایل باشد. این کار امکان ناوبری و جستجوی بهینه در سیستم مدیریت فایل را فراهم می‌کند.
الگوریتم‌های فشرده‌سازی: از درخت‌های باینری می‌توان برای پیاده‌سازی کدگذاری هافمن استفاده کرد. هافمن یک الگوریتم فشرده‌سازی است که کدهای با طول متغیر را به کاراکترها بر اساس فراوانی وقوع آن‌ها در داده‌های ورودی اختصاص می‌دهد.
درخت‌های تصمیم: درخت‌های باینری را می‌توان برای پیاده‌ سازی درخت‌های تصمیم که نوعی الگوریتم های یادگیری ماشینالگوریتم های یادگیری ماشیناین صفحه عالی به معرفی الگوریتم های یادگیری ماشین پرداخته و انواع الگوریتم های یادگیری ماشین و نحوه افزایش دقت الگوریتم های یادگیری ماشین را توضیح داده است که برای طبقه‌بندی و تحلیل رگرسیون استفاده می‌شود، استفاده کرد.
هوش مصنوعیهوش مصنوعی (AI) چیست؟ انواع، کاربردها، مزایا و معایبهوش مصنوعی یا Artificial Intelligence یا به اختصار AI، امروزه کاربردهای بسیاری پیدا کرده و به یکی از داغ‌ترین حوزه‌های بشر تبدیل شده است، اما با این وجود بسیاری از افراد با کاربردهای آن آشنایی کامل ندارند، به همین علت در این صفحه کاربردها، مزایا و معایب AI بطور کامل بررسی شده است بازی: درخت‌ های باینری را می‌توان برای پیاده‌سازی هوش مصنوعی بازی استفاده کرد، بصورتیکه که هر گره نشان‌دهنده یک حرکت احتمالی در بازی باشد. الگوریتم های هوش مصنوعیالگوریتم های هوش مصنوعی چیست اند و چگونه کار میکنند؟این صفحه عالی به معرفی انواع الگوریتم های هوش مصنوعی پرداخته و توضیح داده که هر یک از الگوریتم های هوش مصنوعی چگونه کار می‌کنند و چه کاربردی دارند می‌تواند درخت را جستجو کند تا بهترین حرکت ممکن را پیدا کند.

حتما بخوانید :

الگوریتم جستجوی اول سطح چیست؟ پیمایش سطحی (BFS) چیست؟

مزایا و معایب درخت دودویی

مزایای درخت دودویی

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

معایب درخت دودویی

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

حتما بخوانید :

خرید فیلم ساختمان داده

جمع‌بندی

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

درخت باینری چیست؟

درختان دودویی درختانی هستند که تنها گره ریشه می‌تواند حداکثر تا 2 زیردرخت را در خود جای دهد: زیردرخت چپ و زیردرخت راست. هر گره دیگر نیز مانند گره ریشه حداکثر دارای دو زیردرخت چپ یا راست است.

درختان باینری در زندگی واقعی چگونه استفاده می‌شوند؟

در زیر کاربردهای درخت باینری آورده شده است:

درخت باینری به عنوان ساختارداده پایه در مایکروسافت اکسل و spreadsheets استفاده می‌شود.
درخت دودویی برای پیاده سازی شاخص پایگاه داده های تقسیم شده استفاده می‌شود.
Splay Tree (نوعی درخت دودویی) در پیاده سازی کش بهینه در سیستم‌های سخت‌افزاری و نرم‌افزاری استفاده می‌شود.

اشکال درخت باینری چیست؟

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