Foreplay
Αυτό το άρθρο αφορά τα δέντρα δυαδικής αναζήτησης. Πρόσφατα έγραψα ένα άρθρο για Εκεί δεν έδωσα σημασία στα δυαδικά δέντρα, γιατί οι μέθοδοι αναζήτησης, εισαγωγής, διαγραφής δεν ήταν σχετικές. Τώρα αποφάσισα να γράψω ένα άρθρο για τα δέντρα. Ίσως ξεκινήσουμε.
Ένα δέντρο είναι μια δομή δεδομένων που αποτελείται από κόμβους που συνδέονται με ακμές. Μπορούμε να πούμε ότι ένα δέντρο είναι μια ειδική περίπτωση γραφήματος. Εδώ είναι ένα παράδειγμα δέντρου:
Αυτό δεν είναι ένα δυαδικό δέντρο αναζήτησης! Όλα είναι κάτω από το κόψιμο!
Λεξιλόγιο
Ρίζα
Ρίζα δέντρου είναι ο κορυφαίος κόμβος. Στο παράδειγμα, αυτός είναι ο κόμβος Α. Στο δέντρο, μόνο ένα μονοπάτι μπορεί να οδηγήσει από τη ρίζα σε οποιονδήποτε άλλο κόμβο! Στην πραγματικότητα, οποιοσδήποτε κόμβος μπορεί να θεωρηθεί ως η ρίζα του υποδέντρου που αντιστοιχεί σε αυτόν τον κόμβο.
Γονείς/απόγονοι
Όλοι οι κόμβοι εκτός από τη ρίζα έχουν ακριβώς μια άκρη που οδηγεί σε έναν άλλο κόμβο. Ο κόμβος πάνω από τον τρέχοντα κόμβο καλείται μητρική εταιρεία αυτόν τον κόμβο. Καλείται ένας κόμβος που βρίσκεται κάτω από τον τρέχοντα και είναι συνδεδεμένος με αυτόν απόγονος αυτόν τον κόμβο. Ας πάρουμε ένα παράδειγμα. Πάρτε τον κόμβο Β, τότε ο γονέας του θα είναι ο κόμβος Α και τα παιδιά του θα είναι οι κόμβοι D, E και F.
Φύλλο
Ένας κόμβος που δεν έχει παιδιά ονομάζεται φύλλο του δέντρου. Στο παράδειγμα, οι κόμβοι D, E, F, G, I, J, K θα είναι φύλλα.
Αυτή είναι η βασική ορολογία. Άλλες έννοιες θα συζητηθούν αργότερα. Έτσι, ένα δυαδικό δέντρο είναι ένα δέντρο στο οποίο κάθε κόμβος δεν θα έχει περισσότερα από δύο παιδιά. Όπως μαντέψατε, το δέντρο από το παράδειγμα δεν θα είναι δυαδικό, επειδή οι κόμβοι Β και Η έχουν περισσότερα από δύο παιδιά. Ακολουθεί ένα παράδειγμα δυαδικού δέντρου:
Οι κόμβοι του δέντρου μπορούν να περιέχουν οποιαδήποτε πληροφορία. Ένα δυαδικό δέντρο αναζήτησης είναι ένα δυαδικό δέντρο που έχει τις ακόλουθες ιδιότητες:
- Τόσο τα αριστερά όσο και τα δεξιά υποδέντρα είναι δυαδικά δέντρα αναζήτησης.
- Όλοι οι κόμβοι του αριστερού υποδέντρου ενός αυθαίρετου κόμβου Χ έχουν τιμές κλειδιού δεδομένων μικρότερες από την τιμή του κλειδιού δεδομένων του ίδιου του κόμβου Χ.
- Όλοι οι κόμβοι του δεξιού υποδέντρου ενός αυθαίρετου κόμβου Χ έχουν τιμές κλειδιού δεδομένων μεγαλύτερες ή ίσες με την τιμή του κλειδιού δεδομένων του ίδιου του κόμβου Χ.
Κλειδί - κάποιο χαρακτηριστικό του κόμβου (για παράδειγμα, ένας αριθμός). Το κλειδί χρειάζεται για να μπορέσουμε να βρούμε το στοιχείο του δέντρου στο οποίο αντιστοιχεί αυτό το κλειδί. Παράδειγμα δέντρου δυαδικής αναζήτησης:
όψη δέντρου
Καθώς προχωρώ, θα συμπεριλάβω μερικά (ίσως ημιτελή) κομμάτια κώδικα για να βελτιώσω την κατανόησή σας. Ο πλήρης κωδικός θα βρίσκεται στο τέλος του άρθρου.
Το δέντρο αποτελείται από κόμβους. Δομή κόμβου:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
//...остальные методы узла
}
Κάθε κόμβος έχει δύο παιδιά (είναι πολύ πιθανό τα παιδιά leftChild και/ή rightChild να είναι μηδενικά). Μάλλον καταλάβατε ότι σε αυτή την περίπτωση τα αριθμητικά δεδομένα είναι τα δεδομένα που είναι αποθηκευμένα στον κόμβο. κλειδί - κλειδί κόμβου.
Καταλάβαμε τον κόμπο, τώρα ας μιλήσουμε για τα πιεστικά προβλήματα με τα δέντρα. Στο εξής, η λέξη "δέντρο" θα σημαίνει την έννοια του δυαδικού δέντρου αναζήτησης. Δυαδική δομή δέντρου:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Ως πεδίο κλάσης, χρειαζόμαστε μόνο τη ρίζα του δέντρου, γιατί από τη ρίζα, χρησιμοποιώντας τις μεθόδους getLeftChild() και getRightChild(), μπορείτε να φτάσετε σε οποιονδήποτε κόμβο του δέντρου.
Αλγόριθμοι δέντρων
Αναζήτηση
Ας πούμε ότι έχετε ένα χτισμένο δέντρο. Πώς να βρείτε στοιχείο με κλειδί κλειδιού; Πρέπει να μετακινηθείτε διαδοχικά από τη ρίζα προς τα κάτω στο δέντρο και να συγκρίνετε την τιμή του κλειδιού με το κλειδί του επόμενου κόμβου: αν το κλειδί είναι μικρότερο από το κλειδί του επόμενου κόμβου, τότε μεταβείτε στον αριστερό απόγονο του κόμβου, αν είναι περισσότερο - προς τα δεξιά, εάν τα κλειδιά είναι ίσα - ο επιθυμητός κόμβος βρίσκεται! Σχετικός κωδικός:
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
Εάν το ρεύμα γίνει μηδενικό, τότε η επανάληψη έχει φτάσει στο τέλος του δέντρου (σε εννοιολογικό επίπεδο, βρίσκεστε σε μια ανύπαρκτη θέση στο δέντρο - ένα παιδί ενός φύλλου).
Εξετάστε την αποτελεσματικότητα του αλγορίθμου αναζήτησης σε ένα ισορροπημένο δέντρο (ένα δέντρο στο οποίο οι κόμβοι κατανέμονται περισσότερο ή λιγότερο ομοιόμορφα). Τότε η αποτελεσματικότητα αναζήτησης θα είναι O(log(n)) και ο λογάριθμος βάσης 2. Δείτε: εάν υπάρχουν n στοιχεία σε ένα ισορροπημένο δέντρο, τότε αυτό σημαίνει ότι θα υπάρχουν log(n) επίπεδα βάσης 2 του δέντρου. Και στην αναζήτηση, για ένα βήμα του κύκλου, κατεβαίνεις ένα επίπεδο.
εισάγετε
Εάν έχετε κατανοήσει την ουσία της αναζήτησης, τότε δεν θα σας είναι δύσκολο να κατανοήσετε την εισαγωγή. Απλά πρέπει να κατεβείτε στο φύλλο του δέντρου (σύμφωνα με τους κανόνες καθόδου που περιγράφονται στην αναζήτηση) και να γίνετε ο απόγονός του - αριστερά ή δεξιά, ανάλογα με το κλειδί. Εκτέλεση:
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
Σε αυτήν την περίπτωση, εκτός από τον τρέχοντα κόμβο, είναι απαραίτητο να αποθηκεύσετε πληροφορίες για τον γονέα του τρέχοντος κόμβου. Όταν το ρεύμα γίνει μηδενικό, η γονική μεταβλητή θα περιέχει το φύλλο που χρειαζόμαστε.
Η αποτελεσματικότητα εισαγωγής θα είναι προφανώς η ίδια με αυτή της αναζήτησης - O(log(n)).
Μετακίνηση
Η διαγραφή είναι η πιο περίπλοκη λειτουργία που θα χρειαστεί να γίνει με ένα δέντρο. Είναι σαφές ότι πρώτα θα χρειαστεί να βρούμε το στοιχείο που πρόκειται να αφαιρέσουμε. Αλλά μετά τι; Αν απλώς ορίσουμε την αναφορά του σε null, τότε θα χάσουμε πληροφορίες για το υποδέντρο του οποίου η ρίζα είναι αυτός ο κόμβος. Οι μέθοδοι αφαίρεσης δέντρων χωρίζονται σε τρεις περιπτώσεις.
Πρώτη περίπτωση. Ο κόμβος που πρόκειται να αφαιρεθεί δεν έχει παιδιά.
Εάν ο κόμβος που θα διαγραφεί δεν έχει παιδιά, σημαίνει ότι είναι φύλλο. Επομένως, μπορείτε απλά να ορίσετε τα πεδία leftChild ή rightChild του γονέα του σε null.
Δεύτερη περίπτωση. Ο κόμβος που πρόκειται να αφαιρεθεί έχει ένα παιδί
Αυτή η περίπτωση επίσης δεν είναι πολύ δύσκολη. Ας επιστρέψουμε στο παράδειγμά μας. Ας υποθέσουμε ότι πρέπει να διαγράψουμε ένα στοιχείο με το κλειδί 14. Συμφωνήστε ότι εφόσον είναι το σωστό παιδί του κόμβου με το κλειδί 10, τότε οποιοσδήποτε από τους απόγονους του (σε αυτήν την περίπτωση, ο σωστός) θα έχει κλειδί μεγαλύτερο από 10, οπότε μπορεί εύκολα να το «κόψει» από το δέντρο και να συνδέσει τον γονέα απευθείας με το παιδί του κόμβου που διαγράφεται, δηλ. συνδέστε τον κόμβο με το κλειδί 10 στον κόμβο 13. Η κατάσταση θα ήταν παρόμοια αν έπρεπε να διαγράψουμε έναν κόμβο που είναι το αριστερό παιδί του γονέα του. Σκεφτείτε το μόνοι σας - μια ακριβής αναλογία.
Τρίτη περίπτωση. Ο Κόμβος έχει δύο παιδιά
Η πιο δύσκολη περίπτωση. Ας ρίξουμε μια ματιά σε ένα νέο παράδειγμα.
Αναζήτηση διαδόχου
Ας υποθέσουμε ότι πρέπει να αφαιρέσουμε τον κόμβο με το κλειδί 25. Ποιον θα βάλουμε στη θέση του; Ένας από τους οπαδούς του (απόγονοι ή απόγονοι απογόνων) πρέπει να γίνει διάδοχος(αυτός που θα πάρει τη θέση του αφαιρεθέντος κόμβου).
Πώς ξέρετε ποιος πρέπει να είναι ο διάδοχος; Διαισθητικά, αυτός είναι ο κόμβος στο δέντρο του οποίου το κλειδί είναι το επόμενο μεγαλύτερο από τον κόμβο που αφαιρείται. Ο αλγόριθμος είναι ο εξής. Πρέπει να πάτε στο δεξί παιδί του (πάντα στο δεξί, επειδή ειπώθηκε ήδη ότι το κλειδί του διαδόχου είναι μεγαλύτερο από το κλειδί του κόμβου που διαγράφεται) και στη συνέχεια να περάσετε από την αλυσίδα των αριστερών παιδιών αυτού του δεξιού παιδί. Στο παράδειγμα, πρέπει να πάμε στον κόμβο με το κλειδί 35 και, στη συνέχεια, να κατεβούμε την αλυσίδα των αριστερών τέκνων του στο φύλλο - σε αυτήν την περίπτωση, αυτή η αλυσίδα αποτελείται μόνο από τον κόμβο με το κλειδί 30. Αυστηρά μιλώντας, αναζητούμε ο μικρότερος κόμβος στο σύνολο των κόμβων μεγαλύτερος από τον επιθυμητό κόμβο.
Κωδικός μεθόδου αναζήτησης διαδόχου:
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;//родитель преемника
Node<T> successor = deleteNode;//преемник
Node<T> current = successor.getRightChild();//просто "пробегающий" узел
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
//на выходе из цикла имеем преемника и родителя преемника
if (successor != deleteNode.getRightChild()) {//если преемник не совпадает с правым потомком удаляемого узла
parentSuccessor.setLeftChild(successor.getRightChild());//то его родитель забирает себе потомка преемника, чтобы не потерять его
successor.setRightChild(deleteNode.getRightChild());//связываем преемника с правым потомком удаляемого узла
}
return successor;
}
Ο πλήρης κωδικός της μεθόδου διαγραφής:
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;//В зависимости от того, является ли удаляемый узел левым или правым потомком своего родителя, булевская переменная isLeftChild будет принимать значение true или false соответственно.
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {//первый случай
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {//второй случай
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {//третий случай
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
Η πολυπλοκότητα μπορεί να προσεγγιστεί σε O(log(n)).
Εύρεση του μέγιστου/ελάχιστου σε ένα δέντρο
Προφανώς, πώς να βρείτε την ελάχιστη / μέγιστη τιμή στο δέντρο - πρέπει να περάσετε διαδοχικά από την αλυσίδα των αριστερών / δεξιών στοιχείων του δέντρου, αντίστοιχα. όταν φτάσετε στο φύλλο, θα είναι το ελάχιστο/μέγιστο στοιχείο.
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
Πολυπλοκότητα - O(log(n))
Συμμετρική παράκαμψη
Η διέλευση είναι μια επίσκεψη σε κάθε κόμβο του δέντρου προκειμένου να γίνει κάτι με αυτόν.
Αναδρομικός αλγόριθμος συμμετρικής διέλευσης:
- Κάντε μια ενέργεια στο αριστερό παιδί
- Κάντε μια ενέργεια με τον εαυτό σας
- Κάντε μια ενέργεια στο σωστό παιδί
Κωδικός:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Συμπέρασμα
Τελικά! Αν δεν εξήγησα κάτι ή έχω σχόλια, τότε περιμένω στα σχόλια. Όπως υποσχέθηκε, εδώ είναι ο πλήρης κώδικας.
Node.java:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public void setLeftChild(Node<T> newNode) {
leftChild = newNode;
}
public void setRightChild(Node<T> newNode) {
rightChild = newNode;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
public T getData() {
return data;
}
public int getKey() {
return key;
}
}
BinaryTree.java:
public class BinaryTree<T> {
private Node<T> root;
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;
Node<T> successor = deleteNode;
Node<T> current = successor.getRightChild();
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
if (successor != deleteNode.getRightChild()) {
parentSuccessor.setLeftChild(successor.getRightChild());
successor.setRightChild(deleteNode.getRightChild());
}
return successor;
}
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");
inOrder(current.getRightChild());
}
}
}
PS
Εκφυλισμός σε O(n)
Πολλοί από εσάς μπορεί να έχετε παρατηρήσει: τι γίνεται αν κάνετε το δέντρο να γίνει ανισόρροπο; Για παράδειγμα, βάλτε κόμβους στο δέντρο με αυξανόμενα κλειδιά: 1,2,3,4,5,6... Τότε το δέντρο θα θυμίζει κάπως μια συνδεδεμένη λίστα. Και ναι, το δέντρο θα χάσει τη δομή του δέντρου, και ως εκ τούτου την αποτελεσματικότητα της πρόσβασης στα δεδομένα. Η πολυπλοκότητα των λειτουργιών αναζήτησης, εισαγωγής και διαγραφής θα γίνει ίδια με αυτή μιας συνδεδεμένης λίστας: O(n). Αυτό είναι ένα από τα πιο σημαντικά, κατά τη γνώμη μου, μειονεκτήματα των δυαδικών δέντρων.
Μόνο εγγεγραμμένοι χρήστες μπορούν να συμμετάσχουν στην έρευνα. , Σας παρακαλούμε.
Δεν είμαι στο Habré για πολύ καιρό και θα ήθελα να μάθω ποια άρθρα για ποια θέματα θα θέλατε να δείτε περισσότερα;
-
ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ
-
Αλγόριθμοι (DP, αναδρομή, συμπίεση δεδομένων κ.λπ.)
-
Εφαρμογή δομών δεδομένων και αλγορίθμων στην πραγματική ζωή
-
Προγραμματισμός εφαρμογών android σε Java
-
Προγραμματισμός διαδικτυακών εφαρμογών Java
Ψήφισαν 2 χρήστες. 1 χρήστης απείχε.
Πηγή: www.habr.com