Το Στέκι των Πληροφορικών

προτείνετε παρατηρήσεις, όσο προλαβαίνουμε!
θεωρία-q-a-τοταλ.pdf

Καλησπέρα Ευτύχη,

Με μια γρήγορη ματιά μου φαίνεται αρκετά καλό. Είναι και αρκετά μαζεμένο και αυτό βοηθάει.

Μια παρατήρηση: Το δυαδικό δένδρο στη σέλ. 50 ορίζεται ως διατεταγμένο.

το δυαδικό δέντρο αναζήτησης
όχι το δυαδικό γενικά...

Παράθεση από: epsilonXi στις 11 Απρ 2022, 12:37:37 ΜΜτο δυαδικό δέντρο αναζήτησης
όχι το δυαδικό γενικά...

Το δυαδικό γενικά!
σελίδα 50:
Ένα δυαδικό δένδρο (binary tree) είναι ένα διατεταγμένο δένδρο, στο οποίο κάθε κόμβος έχει το πολύ δύο παιδιά, το αριστερό και το δεξί παιδί

πάλι αδιάβαστος πιάστηκα

Παράθεση από: akouts στις 12 Απρ 2022, 08:10:17 ΠΜΤο δυαδικό γενικά!
σελίδα 50:
Ένα δυαδικό δένδρο (binary tree) είναι ένα διατεταγμένο δένδρο, στο οποίο κάθε κόμβος έχει το πολύ δύο παιδιά, το αριστερό και το δεξί παιδί

Επειδή το βιβλίο δεν είναι και Ευαγγέλιο και επειδή ειδικά στη βιβλιογραφία περί Δένδρων
έχουμε διαφοροποιήσεις στους ορισμούς και επειδή στο Δυαδικό δένδρο δεν έχουμε
κάποια συγκεκριμένη διάταξη για τα παιδιά κάθε κόμβου ίσως διατεταγμένο Δένδρο
είναι το Δυαδικό Δένδρο αναζήτησης.

Σελ. 46:  Σε αυτή την περίπτωση, που για κάθε κόμβο υπάρχει μία γραμμική σχέση μεταξύ των παιδιών του κόμβου αυτού, αναφερόμαστε σε ένα διατεταγμένο δένδρο.

Σελ. 50:  Ένα δυαδικό δένδρο (binary tree) είναι ένα διατεταγμένο δένδρο, στο οποίο κάθε κόμβος έχει το πολύ δύο παιδιά, το αριστερό και το δεξί παιδί.

Σελ. 50:  Ένα δυαδικό δένδρο αναζήτησης (binary search tree) είναι ένα δυαδικό δένδρο, όπου για κάθε κόμβο u, όλοι οι κόμβοι του αριστερού υποδένδρου έχουν τιμές μικρότερες της τιμής του κόμβου u και όλοι οι κόμβοι του δεξιού υποδένδρου έχουν τιμές μεγαλύτερες (ή ίσες) της τιμής του κόμβου u.

Το ερώτημα είναι, άσχετα από το βιβλίο, στη βιβλιογραφία ισχύει ότι κάθε δυαδικό δένδρο είναι διατεταγμένο;
Από ό,τι θυμάμαι δεν είναι αναγκαίο να ισχύει αλλά δεν είμαι και σίγουρος.
Κάποιες πηγές;

Διατεταγμένο δέντρο είναι αυτό που τα παιδιά κάθε κόμβου του συνδέονται με κάποια σχέση διάταξης. Δηλαδή η θέση τους από αριστερά προς τα δεξιά δηλώνει και ακολουθεί ένα κανόνα.
Τώρα τα Δυαδικά δέντρα επειδή περιορίζουν τα παιδιά κάθε κόμβου σε 2 το πολύ, είναι σύνηθες να χρησιμοποιούνται
ως διατεταγμένα (βλέπε δυαδικά δέντρα αναζήτησης, το παράδειγμα του βιβλίου που θεωρεί το αριστερό παιδί μεγαλύτερο σε ηλικία απ' το δεξί κ.λ.π).
Αυτός είναι μάλλον ο λόγος που στη βιβλιογραφία κάποιοι συγγραφείς θεωρούν ένα δυαδικό δέντρο εξ' ορισμού διατεταγμένο.

Ο ορισμός του απλού binary tree είναι 
a tree data structure in which each node has at most two children, which are referred to as the left child and the right child
Πηγή: https://en.wikipedia.org/wiki/Binary_tree (https://en.wikipedia.org/wiki/Binary_tree)
Δηλαδή υπάρχει διάκριση μεταξύ αριστερού και δεξιού παιδιού, αυτό εννοεί.

Δεν μιλάει για διάταξη=ταξινόμηση αλλά λέει ότι ένα δέντρο με τους αριθμούς 5 ως ρίζα και 12 ως αριστερό παιδί και 16 ως δεξί δεν είναι το ίδιο αν αντιστρέψουμε τα παιδιά, δηλαδή να γίνει το 12 δεξί και το 16 αριστερό. Αυτό εννοεί με την λέξη διατεταγμένο, ότι υπάρχει μια διάταξη όπως και ένας πίνακας είναι μια διατεταγμένη ακολουθία και όχι ένα σύνολο. Η σχέση διάταξης δεν σημαίνει απαραίτητα ότι υπακούει σε κανόνες ταξινόμησης. π.χ. μπορώ να ορίσω μια σχέση διάταξης όπου το 3 είναι πριν το 7  και μετά το 12, φυσικά θα πρέπει να έχει κάποιες ιδιότητες (reflective, transitive κλπ), αλλά αυτό είναι άλλο θέμα. Δεν εννοεί δηλαδή σχέση διάταξης με την αυστηρή έννοια που έχουμε στο μυαλό μας αλλά κάτι πιο χαλαρό.
To binary search tree ορίζεται ως: 

binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.  
Πηγή:  https://en.wikipedia.org/wiki/Binary_search_tree (https://en.wikipedia.org/wiki/Binary_search_tree)

Παράθεση από: evry στις 14 Απρ 2022, 03:28:57 ΜΜΟ ορισμός του απλού binary tree είναι
a tree data structure in which each node has at most two children, which are referred to as the left child and the right child
Πηγή: https://en.wikipedia.org/wiki/Binary_tree (https://en.wikipedia.org/wiki/Binary_tree)
Δηλαδή υπάρχει διάκριση μεταξύ αριστερού και δεξιού παιδιού, αυτό εννοεί.

Δεν μιλάει για διάταξη=ταξινόμηση αλλά λέει ότι ένα δέντρο με τους αριθμούς 5 ως ρίζα και 12 ως αριστερό παιδί και 16 ως δεξί δεν είναι το ίδιο αν αντιστρέψουμε τα παιδιά, δηλαδή να γίνει το 12 δεξί και το 16 αριστερό. Αυτό εννοεί με την λέξη διατεταγμένο, ότι υπάρχει μια διάταξη όπως και ένας πίνακας είναι μια διατεταγμένη ακολουθία και όχι ένα σύνολο. Η σχέση διάταξης δεν σημαίνει απαραίτητα ότι υπακούει σε κανόνες ταξινόμησης. π.χ. μπορώ να ορίσω μια σχέση διάταξης όπου το 3 είναι πριν το 7  και μετά το 12, φυσικά θα πρέπει να έχει κάποιες ιδιότητες (reflective, transitive κλπ), αλλά αυτό είναι άλλο θέμα. Δεν εννοεί δηλαδή σχέση διάταξης με την αυστηρή έννοια που έχουμε στο μυαλό μας αλλά κάτι πιο χαλαρό.
To binary search tree ορίζεται ως:

binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree. 
Πηγή:  https://en.wikipedia.org/wiki/Binary_search_tree (https://en.wikipedia.org/wiki/Binary_search_tree)

Όμως έτσι όλα τα δένδρα δεν θα έπρεπε να είναι διατεταγμένα; (π.χ. τριαδικό: αριστερό παιδί-μεσαίο-δεξί κ.ο.κ).
Ή πάλι γιατί να μην μπορώ να δημιουργήσω μια δυαδική δενδρική δομή όπου αν αλλάζω αμοιβαία το αριστερό με το
δεξί υποδένδρο οποιουδήποτε κόμβου να προκύπτει ισοδύναμο δένδρο;
Αυτό δεν εξαρτάται μόνο από αυτό που θέλω να αναπαραστήσω; (Να μην παίζει ρόλο αν το τυχόν δεδομένο είναι δεξί ή αριστερό παιδί κάθε κόμβου)
Δηλαδή θέλω να πω ότι ένα δυαδικό δένδρο μπορεί να είναι διατεταγμένο, μπορεί και όχι ανάλογα με αυτό που αναπαριστά.
Και στη βιβλιογραφία δεν αναφέρεται ως διατεταγμένο σ' όλους τους ορισμούς των δυαδικών δένδρων.
Τελικά;

Την ιδιότητα αυτή να μην παίζει ρόλο η διάταξη μεταξύ των παιδιών την έχω δει μόνο στον σωρό (heap). Αυτό είναι ότι πιο κοντινο σε αυτό που λες, όμως στον σωρό υπάρχει διάταξη μεταξύ του πατέρα και των παιδιών.
Ο ορισμός που ισχύει είναι ότι όταν λέμε δυαδικό δέντρο είναι default διατεταγμένο, δηλαδή υπάρχει διάκριση αριστερού/δεξιού παιδιού. Για αυτό υπάρχει στην βιβλιογραφία το unordered binary tree που είναι αυτό ακριβώς που λες.
Δες εδώ:
Generation of Unordered Binary Trees (https://link.springer.com/chapter/10.1007/978-3-540-24767-8_68)

Απλά κάποιοι όταν μιλάνε για ordered εννοούν ταξινομημένο και όχι διάκριση left/right και εκεί υπάρχει η σύγχυση

Παράθεση από: evry στις 14 Απρ 2022, 05:50:41 ΜΜΟ ορισμός που ισχύει είναι ότι όταν λέμε δυαδικό δέντρο είναι default διατεταγμένο, δηλαδή υπάρχει διάκριση αριστερού/δεξιού παιδιού. Για αυτό υπάρχει στην βιβλιογραφία το unordered binary tree που είναι αυτό ακριβώς που λες.
Απλά κάποιοι όταν μιλάνε για ordered εννοούν ταξινομημένο και όχι διάκριση left/right και εκεί υπάρχει η σύγχυση

Ακριβώς αλλιώς πχ δεν θα υπήρχε preorder, inorder, postorder διάσχιση των δυαδικών δένδρων

https://en.wikipedia.org/wiki/Binary_tree

Types of binary trees[edit]
Tree terminology is not well-standardized and so varies in the literature.

• A rooted binary tree has a root node and every node has at most two children.

• A full binary tree (sometimes referred to as a proper^[15] or plane binary tree)^[16][17] is a tree in which every node has either 0 or 2 children. Another way of defining a full binary tree is a recursive definition. A full binary tree is either:^[11]
  
  
  • A single vertex.
  • A tree whose root node has two subtrees, both of which are full binary trees.
• A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level.^[18] An example of a perfect binary tree is the (non-incestuous) ancestry chart of a person to a given depth, as each person has exactly two biological parents (one mother and one father). Provided the ancestry chart always displays the mother and the father on the same side for a given node, their sex can be seen as an analogy of left and right children, children being understood here as an algorithmic term.
• A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes at the last level h.^[19] A perfect tree is therefore always complete but a complete tree is not necessarily perfect. An alternative definition is a perfect tree whose rightmost leaves (perhaps all) have been removed. Some authors use the term complete to refer instead to a perfect binary tree as defined above, in which case they call this type of tree (with a possibly not filled last level) an almost complete binary tree or nearly complete binary tree.^[20][21] A complete binary tree can be efficiently represented using an array.^[19]

• In the infinite complete binary tree, every node has two children (and so the set of levels is countably infinite). The set of all nodes is countably infinite, but the set of all infinite paths from the root is uncountable, having the cardinality of the continuum. That's because these paths correspond by an order-preserving bijection to the points of the Cantor set, or (using the example of a Stern–Brocot tree) to the set of positive irrational numbers.
• A balanced binary tree is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1.^[22] One may also consider binary trees where no leaf is much farther away from the root than any other leaf. (Different balancing schemes allow different definitions of "much farther".^[23])
• A degenerate (or pathological) tree is where each parent node has only one associated child node.^[24] This means that the tree will behave like a linked list data structure.

Discrete Mathematics:Proofs, Structures and Applications, Third Edition (https://www.amazon.com/Discrete-Mathematics-Proofs-Structures-Applications/dp/1439812802), Third Edition. CRC Press. p. 620. ISBN 978-1-4398-1280-8.