Δυαδικό δέντρο στη δομή δεδομένων (ΠΑΡΑΔΕΙΓΜΑ)
Σάρα Τσεν
Τι είναι ένα Δυαδικό Δέντρο;
Η λέξη δυαδικό σημαίνει δύο. Στη δομή δεδομένων δέντρου "Δυαδικό δέντρο", σημαίνει ένα δέντρο όπου κάθε κόμβος μπορεί να έχει το πολύ δύο θυγατρικούς κόμβους (αριστερός και δεξιός κόμβος). Είναι ένα απλό δυαδικό δέντρο.
Ωστόσο, υπάρχει ένα άλλο δυαδικό δέντρο που χρησιμοποιείται πιο συχνά και έχει αρκετές περιπτώσεις χρήσης. Ονομάζεται Δυαδικό Δέντρο Αναζήτησης (BST). Αυτό το δέντρο μπορεί να κάνει τον αλγόριθμο αναζήτησης πολύ πιο γρήγορο, με ακρίβεια log(n) πολυπλοκότητας χρόνου. Στη δομή δεδομένων, n σημαίνει τον αριθμό των κόμβων στο δυαδικό δέντρο.
Ποιες είναι οι διαφορές μεταξύ δυαδικού δέντρου και δυαδικού δέντρου αναζήτησης;
Η διαφορά μεταξύ του BST και του κανονικού Δυαδικού δέντρου είναι ότι ο αριστερός κόμβος BST έχει μικρότερη τιμή από τον κόμβο ρίζας και ο δεξιός κόμβος έχει μεγαλύτερη τιμή από τον κόμβο ρίζας. Έτσι, το αριστερό υποδέντρο θα περιέχει πάντα μικρότερη τιμή από τη ρίζα και το δεξί υποδέντρο θα περιέχει πάντα μεγαλύτερη τιμή από τη ρίζα.
Παράδειγμα δυαδικών δέντρων αναζήτησης
Ας έχουμε το ακόλουθο παράδειγμα για την επίδειξη των εννοιών του Δυαδικού Δέντρου Αναζήτησης.
Εδώ μπορείτε όλοι οι κόμβοι να ακολουθήσουν τη δεδομένη πειθαρχία. Υπάρχει ένας τύπος για τον μέγιστο αριθμό κόμβων στη Δυαδική Δενδρική Αναζήτηση. Αν παρατηρήσουμε το παραπάνω δέντρο, μπορούμε να δούμε ότι κάθε κόμβος έχει δύο παιδιά εκτός από όλους τους κόμβους των φύλλων. Και το ύψος(h) του δεδομένου Δυαδικού Δέντρου είναι 4. Ο τύπος είναι 2h - 1. Έτσι, δίνει 15.
Η παραπάνω εικόνα δεν είναι πλήρες Δυαδικό Δυαδικό δέντρο ή Ισορροπημένο Δυαδικό Δέντρο, ονομάζεται Πλήρες Δυαδικό δέντρο ή Ισορροπημένο Δυαδικό Δέντρο. Υπάρχει μια άλλη Δομή Δεδομένων που ονομάζεται AVL (άλλος τύπος δυαδικού δέντρου) που βελτιστοποιεί το ύψος του Δυαδικού δέντρου και εκτελεί ταχύτερα την αναζήτηση για το BST όπως στο Σχήμα 3.
Προσπαθήστε να υπολογίσετε τη διέλευση κατά σειρά του Δυαδικού Δέντρου που δίνεται παραπάνω. Θα διαπιστώσετε ότι θα δώσει έναν μη μειούμενο ταξινομημένο πίνακα και οι αλγόριθμοι διέλευσης θα είναι ίδιοι με το Δυαδικό δέντρο.
Τύποι δυαδικού δέντρου
Ακολουθούν ορισμένοι σημαντικοί τύποι δυαδικών δέντρων:
- Πλήρες δυαδικό δέντρο: Κάθε κόμβος μπορεί να έχει 0 ή 2 θυγατρικούς κόμβους σε αυτό το δυαδικό δέντρο. Μόνο ένας θυγατρικός κόμβος δεν επιτρέπεται σε αυτόν τον τύπο δυαδικού δέντρου. Έτσι, εκτός από τον κόμβο φύλλων, όλοι οι κόμβοι θα έχουν 2 παιδιά.
- Πλήρες δυαδικό δέντρο: Κάθε κόμβος μπορεί να έχει 0 ή 2 κόμβους. Φαίνεται σαν το Πλήρες Δυαδικό Δέντρο, αλλά όλα τα στοιχεία του φύλλου κλίνουν προς το αριστερό υποδέντρο, ενώ στο πλήρες δυαδικό δέντρο ο κόμβος μπορεί να βρίσκεται στο δεξί ή στο αριστερό υποδέντρο.
- Τέλειο δυαδικό δέντρο: Όλοι οι κόμβοι πρέπει να έχουν 0 ή 2 κόμβους και όλοι οι κόμβοι φύλλων πρέπει να βρίσκονται στο ίδιο επίπεδο ή ύψος. Το παραπάνω παράδειγμα μιας πλήρους δυαδικής δομής δέντρου δεν είναι τέλειο δυαδικό δέντρο επειδή ο κόμβος 6 και ο κόμβος 1,2,3 δεν βρίσκονται στο ίδιο ύψος. Αλλά το παράδειγμα του Πλήρους Δυαδικού Δέντρου είναι ένα τέλειο δυαδικό δέντρο.
- Εκφυλισμένο δυαδικό δέντρο: Κάθε κόμβος μπορεί να έχει μόνο ένα παιδί. Όλες οι λειτουργίες όπως η αναζήτηση, η εισαγωγή και η διαγραφή χρειάζονται χρόνο O(N).
- Ισορροπημένο δυαδικό δέντρο: Εδώ σε αυτό το δυαδικό δέντρο, η διαφορά ύψους του αριστερού και του δεξιού υποδέντρου είναι το πολύ 1. Έτσι, κατά την προσθήκη ή τη διαγραφή ενός κόμβου, πρέπει να εξισορροπήσουμε ξανά το ύψος του δέντρου. Αυτός ο τύπος αυτο-ισορροπημένο δυαδικό δέντρο ονομάζεται Δέντρο AVL.
Υπάρχουν τρεις βασικές λειτουργίες του BST. Αυτά συζητούνται αναλυτικά παρακάτω.
Εφαρμογή του Binary Tree σε C και C++
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int value;
struct Node *left, *right;
}
struct Node *getEmptynode(int val)
{
struct Node *tempNode = (struct Node *)malloc(sizeof(struct Node));
tempNode->value = val;
tempNode->left = NULL;
tempNode->right = NULL;
return tempNode;
}
struct Node *successor(struct Node *node)
{
struct Node *present = node;
// going to the left most node
while (present != NULL && present->left != NULL)
{
present = present->left;
}
return present;
}
struct Node *insert(struct Node *node, int value)
{
if (node == NULL)
{
return getEmptynode(value);
}
if (value < node->value)
{
node->left = insert(node->left, value);
}
else
{
node->right = insert(node->right, value);
}
return node;
}
int searchInBST(struct Node *node, int value)
{
struct Node *current = node;
while (current->value != value)
{
if (current->value > value)
{
current = current->left;
}
else
{
current = current->right;
}
if (current == NULL)
{
return 0;
}
}
return 1;
}
void inorder(struct Node *root)
{
if (root != NULL)
{
inorder(root->left);
cout << root->value << " ";
inorder(root->right);
}
}
struct Node *deleteNode(struct Node *node, int value)
{
if (node == NULL)
{
return node;
}
if (value < node->value)
{
node->left = deleteNode(node->left, value);
}
else if (value > node->value)
{
node->right = deleteNode(node->right, value);
}
else
{
if (node->left == NULL)
{
struct Node *temp = node->right;
free(node);
return temp;
}
else if (node->right == NULL)
{
struct Node *temp = node->left;
free(node);
return temp;
}
struct Node *temp = successor(node->right);
node->value = temp->value;
node->right = deleteNode(node->right, temp->value);
}
return node;
}
int main()
{
struct Node *root = NULL;
root = insert(root, 8);
root = insert(root, 4);
root = insert(root, 12);
root = insert(root, 2);
root = insert(root, 6);
root = insert(root, 10);
root = insert(root, 14);
root = insert(root, 1);
root = insert(root, 3);
root = insert(root, 5);
root = insert(root, 7);
root = insert(root, 9);
root = insert(root, 11);
root = insert(root, 13);
root = insert(root, 15);
cout << "InOrder Traversal after inserting all nodes: " << endl;
inorder(root);
root = insert(root, -10);
cout << "\nInOrder Traversal after inserting -10 : " << endl;
inorder(root);
cout << "\nSearching -5 in the BST: " << searchInBST(root, -5) << endl;
cout << "Searching -10 in the BST: " << searchInBST(root, -10) << endl;
root = deleteNode(root,8);
cout<<"After deleting node 8, inorder traversal: "<<endl;
inorder(root);
root = deleteNode(root,-10);
cout<<"\nAfter deleting node -10, inorder traversal: "<<endl;
inorder(root);
}
Παραγωγή:
InOrder Traversal after inserting all nodes: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 InOrder Traversal after inserting -10 : 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Searching -5 in the BST: 0 Searching -10 in the BST: 1 After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15
Εφαρμογή δυαδικού δέντρου σε Python
class Node:
def __init__(self,value):
self.left = None
self.right = None
self.value = value
def insert(root,value):
if root == None:
return Node(value)
if value< root.value:
root.left = insert(root.left,value)
else:
root.right = insert(root.right,value)
return root
def searchInBST(root,value):
current = root
while current.value != value:
if current.value > value:
current = current.left
else:
current = current.right
if current == None:
return "Not found"
return "Found"
def inorder(root):
if root != None:
inorder(root.left)
print(root.value,end=" ")
inorder(root.right)
def successor(root):
present = root
while present != None and present.left != None:
present = present.left
return present
def deleteNode(root,value):
if root == None:
return root
if value < root.value:
root.left = deleteNode(root.left, value)
elif value>root.value:
root.right = deleteNode(root.right, value)
else:
if root.left == None:
temp = root.right
root = None
return temp
elif root.right == None:
temp = root.left
root = None
return temp
temp = successor(root.right)
root.value = temp.value
root.right = deleteNode(root.right, temp.value)
return root
root = Node(8)
root = insert(root, 4)
root = insert(root, 12)
root = insert(root, 2)
root = insert(root, 6)
root = insert(root, 10)
root = insert(root, 14)
root = insert(root, 1)
root = insert(root, 3)
root = insert(root, 5)
root = insert(root, 7)
root = insert(root, 9)
root = insert(root, 11)
root = insert(root, 13)
root = insert(root, 15)
print("InOrder Traversal after inserting all nodes: ")
inorder(root)
root = insert(root, -10)
print("\nInOrder Traversal after inserting -10 : ")
inorder(root)
print("\nSearching -5 in the BST: ",searchInBST(root, -5))
print("Searching -5 in the BST: ",searchInBST(root, -10))
root = deleteNode(root,8)
print("After deleting node 8, inorder traversal:")
inorder(root)
root = deleteNode(root,-10)
print("\nAfter deleting node -10, inorder traversal:")
inorder(root)
Παραγωγή:
InOrder Traversal after inserting all nodes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 InOrder Traversal after inserting -10 : -10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Searching -5 in the BST: Not found Searching -5 in the BST: Found After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15
Εφαρμογή δυαδικού δέντρου
Ακολουθούν ορισμένες κοινές εφαρμογές του Binary Tree:
- Οργάνωση δεδομένων κόμβου με ταξινομημένη σειρά
- Χρησιμοποιείται στο χάρτη και ορίζει αντικείμενα κόμβων σε βιβλιοθήκες γλωσσών προγραμματισμού.
- Αναζήτηση στοιχείων στις δομές δεδομένων
» Μάθετε τον επόμενο σεμινάριο μας σχετικά Αλγόριθμος συνδυασμού
