Il modo migliore per calcolare l'altezza di un albero binario di ricerca? (Equilibra un'AVL-tree)
https://stackoverflow.com/questions/575772
-
05-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
sto cercando il modo migliore per calcolare un equilibrio nodi in un AVL-tree . Ho pensato che avevo a lavorare, ma dopo un po 'pesante inserimento / aggiornamento posso vedere che non funziona correttamente (a tutti).
Questa è una specie di una domanda in due parti, la prima parte sarebbe come calcolare l'altezza di un sotto-albero, so che la definizione "L'altezza di un nodo è la lunghezza del percorso di discesa più lunga ad una foglia da quel nodo ". e lo capisco, ma non riesco a sua attuazione. E per confondermi ulteriormente questa citazione può essere trovato su wikipedia sul viale altezze "Convenzionalmente, il valore -1 corrisponde a una sottostruttura senza nodi, mentre lo zero corrisponde a una sottostruttura con un nodo."
E la seconda parte è sempre il fattore di equilibrio di un sotto-albero in un albero AVL, ho alcun problema la comprensione del concetto, "ottenere l'altezza dei vostri L e R sotto-alberi e sottrarre R da L ". E questo è definito come qualcosa di simile: BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]
lettura su wikipedia dice sulle prime righe descrivono inserimenti in un albero AVL: "Se il fattore di equilibrio diventa -1, 0, 1 o allora l'albero è ancora in forma AVL, e non sono necessarie rotazioni . "
Si passa poi, dicendo questo "Se il fattore di equilibrio diventa 2 o -2 poi l'albero radicato in questo nodo è sbilanciato, ed è necessaria una rotazione albero. Al massimo sarà necessaria una rotazione singola o doppia per bilanciare l'albero " -., che non ho difficoltà a cogliere.
Ma (sì, c'è sempre un ma).
Ecco dove si confonde, gli stati di testo "Se il fattore di equilibrio di R è 1, significa che l'inserimento è verificato il (esterno) destra di quel nodo ed è necessaria una rotazione sinistra" . Ma da m comprensione del testo ha detto (come ho citato) che se il fattore di equilibrio era all'interno [-1, 1] allora non c'era bisogno per il bilanciamento?
mi sento così vicino a afferrare il concetto, ho ottenuto le rotazioni degli alberi verso il basso, implementato un normale albero binario di ricerca, e sul punto di cogliere AVL-alberi, ma solo sembrano essere mancante che epifania essenziale.
Modifica:. esempi di codice sono preferite rispetto alle formule accademiche come ho sempre avuto un tempo più facile afferrare qualcosa nel codice, ma qualsiasi aiuto è molto apprezzato
Modifica Vorrei poter segnare tutte le risposte come "accettato", ma per me la risposta di Nick è stato il primo che mi ha fatto andare "aha"
.Soluzione
Parte 1 - altezza
Come starblue dice, l'altezza è solo ricorsiva. In pseudo-codice:
height(node) = max(height(node.L), height(node.R)) + 1
Ora altezza può essere definito in due modi. Potrebbe essere il numero di nodi nel percorso dalla radice a quel nodo, o potrebbe essere il numero di collegamenti. Secondo la pagina hai fatto riferimento , la definizione più comune è per il numero di link. Nel qual caso la pseudo codice completo sarebbe:
height(node):
if node == null:
return -1
else:
return max(height(node.L), height(node.R)) + 1
Se si voleva il numero di nodi il codice sarebbe:
height(node):
if node == null:
return 0
else:
return max(height(node.L), height(node.R)) + 1
In entrambi i casi, l'algoritmo di riequilibrio penso che dovrebbe funzionare lo stesso.
Tuttavia, il vostro albero sarà molto più efficiente ( O (ln (n)) ) se si memorizzano le informazioni e l'altezza di aggiornamento nella struttura, piuttosto che calcolare ogni volta. ( O (n) )
Parte 2 - bilanciamento
Quando si dice "Se il fattore di equilibrio di R è 1", si sta parlando del fattore di equilibrio del ramo di destra, quando il fattore di equilibrio in alto è 2. E ti dice come scegliere se fare un rotazione singola o doppia rotazione. In (pitone simili) pseudo-codice:
if balance factor(top) = 2: // right is imbalanced
if balance factor(R) = 1: //
do a left rotation
else if balance factor(R) = -1:
do a double rotation
else: // must be -2, left is imbalanced
if balance factor(L) = 1: //
do a left rotation
else if balance factor(L) = -1:
do a double rotation
Spero che questo ha un senso
Altri suggerimenti
-
Altezza è facilmente implementata da ricorsione, prendere il massimo l'altezza delle sottostrutture più uno.
-
Il "fattore di equilibrio R" si riferisce al sottoalbero destro dell'albero che è fuori equilibrio, suppongo.
Non è necessario calcolare profondità albero al volo.
È possibile mantenere loro come si eseguono le operazioni.
Inoltre, non in realtà, infatti, deve mantenere traccia di profondità; si può semplicemente tenere traccia della differenza tra le profondità degli alberi a sinistra ea destra.
http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx
Basta tenere traccia del fattore di equilibrio (differenza tra sottostrutture destra e sinistra) è che ho trovato più facile da un POV di programmazione, se non che sistemare il fattore di equilibrio dopo una rotazione è una valle di lacrime ...
Ecco un modo alternativo di trovare altezza. Aggiungere un attributo aggiuntivo al vostro nodo denominato Altezza:
class Node
{
data value; //data is a custom data type
node right;
node left;
int height;
}
Ora, faremo un semplice attraversamento in ampiezza dell'albero, e mantenere l'aggiornamento del valore di altezza per ogni nodo:
int height (Node root)
{
Queue<Node> q = Queue<Node>();
Node lastnode;
//reset height
root.height = 0;
q.Enqueue(root);
while(q.Count > 0)
{
lastnode = q.Dequeue();
if (lastnode.left != null){
lastnode.left.height = lastnode.height + 1;
q.Enqueue(lastnode.left);
}
if (lastnode.right != null){
lastnode.right.height = lastnode.height + 1;
q.Enqueue(lastnode.right);
}
}
return lastnode.height; //this will return a 0-based height, so just a root has a height of 0
}
Saluti,
Beh, si può calcolare l'altezza di un albero con la seguente funzione ricorsiva:
int height(struct tree *t) {
if (t == NULL)
return 0;
else
return max(height(t->left), height(t->right)) + 1;
}
con una definizione appropriata della max() e struct tree. Si dovrebbe prendere il tempo di capire perché questo corrisponde alla definizione basata sul percorso di lunghezza che lei cita. Questa funzione utilizza zero come altezza dell'albero vuoto.
Tuttavia, per qualcosa come un albero AVL, non credo che in realtà calcolare l'altezza ogni volta che ne avete bisogno. Invece, ogni nodo della struttura è aumentata con un campo aggiuntivo che ricorda l'altezza del sottoalbero con radice in quel nodo. Questo campo deve essere tenuto up-to-date, come l'albero viene modificato da inserimenti ed eliminazioni.
Ho il sospetto che, se si calcola l'altezza ogni volta invece di cache all'interno del albero come suggerito sopra, che la forma albero AVL sarà corretto, ma non avrà le prestazioni logaritmica previsto.
Ecco dove ottiene confusione, il testo afferma "Se il fattore di equilibrio di R è 1, significa che l'inserimento è verificato il (esterno) destra di quel nodo ed è necessaria una rotazione sinistra". Ma da m comprensione del testo ha detto (come ho citato) che se il fattore di equilibrio era all'interno [-1, 1], quindi non c'era bisogno di bilanciare?
R è il figlio destro del N nodo corrente.
Se balance(N) = +2, allora avete bisogno di una rotazione di qualche tipo. Ma che la rotazione da usare? Beh, dipende da balance(R): se balance(R) = +1 allora avete bisogno di una sinistra-rotazione su N; ma se balance(R) = -1 allora si avrà bisogno di una doppia rotazione di qualche tipo.
Qui è dove si confonde, il testo afferma: "Se il fattore di equilibrio di R è 1, significa l'inserimento si è verificato il (esterno) destra di quel nodo e sinistra la rotazione è necessaria". Ma da m comprensione del testo ha detto (come ho citato) che se la fattore di equilibrio era all'interno [-1, 1], quindi non c'era bisogno per il bilanciamento?
D'accordo, il tempo epifania.
Si consideri che cosa fa una rotazione. Pensiamo a una rotazione a sinistra.
P = parent
O = ourself (the element we're rotating)
RC = right child
LC = left child (of the right child, not of ourself)
P
\
O
\
RC
/
LC
P
\
RC
/
O
\
LC
10
\
15
\
20
/
18
10
\
20
/
15
\
18
basically, what happens is;
1. our right child moves into our position
2. we become the left child of our right child
3. our right child's left child becomes our right
Ora, la cosa più importante che dovete notare qui - questa rotazione a sinistra non è cambiata la profondità delle DELL'ALBERO. Siamo più equilibrata per averlo fatto.
Ma - ed ecco la magia di AVL - se abbiamo ruotato il bambino diritto alla prima a destra, quello che avremmo è questo ...
P
\
O
\
LC
\
RC
E ora se ruotiamo O a sinistra, ciò che otteniamo è questo ...
P
\
LC
/ \
O RC
Magic! siamo riusciti a sbarazzarsi di un livello dell'albero -. Abbiamo reso il bilanciamento albero
Bilanciamento dei mezzi d'albero sbarazzarsi di eccesso di profondità, e l'imballaggio i livelli superiori in modo più completo - che è esattamente quello che abbiamo appena fatto
.Quella roba tutta su singole doppie rotazioni / è semplicemente che si deve avere il vostro sottostruttura cercando come questo;
P
\
O
\
LC
\
RC
prima di ruotare - e si può avere a che fare un diritto ruotare per entrare in quello stato. Ma se siete già in quello stato, avete solo bisogno di fare la rotazione a sinistra.
Dare BinaryTree<T, Comparator>::Node un membro di dati subtreeHeight, inizializzato a 0 nel suo costruttore, e aggiornare automaticamente ogni volta con:
template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::Node::setLeft (std::shared_ptr<Node>& node) {
const std::size_t formerLeftSubtreeSize = left ? left->subtreeSize : 0;
left = node;
if (node) {
node->parent = this->shared_from_this();
subtreeSize++;
node->depthFromRoot = depthFromRoot + 1;
const std::size_t h = node->subtreeHeight;
if (right)
subtreeHeight = std::max (right->subtreeHeight, h) + 1;
else
subtreeHeight = h + 1;
}
else {
subtreeSize -= formerLeftSubtreeSize;
subtreeHeight = right ? right->subtreeHeight + 1 : 0;
}
}
template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::Node::setRight (std::shared_ptr<Node>& node) {
const std::size_t formerRightSubtreeSize = right ? right->subtreeSize : 0;
right = node;
if (node) {
node->parent = this->shared_from_this();
subtreeSize++;
node->depthFromRoot = depthFromRoot + 1;
const std::size_t h = node->subtreeHeight;
if (left)
subtreeHeight = std::max (left->subtreeHeight, h) + 1;
else
subtreeHeight = h + 1;
}
else {
subtreeSize -= formerRightSubtreeSize;
subtreeHeight = left ? left->subtreeHeight + 1 : 0;
}
}
Si noti che i membri di dati subtreeSize e depthFromRoot sono anche aggiornati.
Queste funzioni sono chiamate quando si inserisce un nodo (tutto testato), per esempio.
template <typename T, typename Comparator>
inline std::shared_ptr<typename BinaryTree<T, Comparator>::Node>
BinaryTree<T, Comparator>::Node::insert (BinaryTree& tree, const T& t, std::shared_ptr<Node>& node) {
if (!node) {
std::shared_ptr<Node> newNode = std::make_shared<Node>(tree, t);
node = newNode;
return newNode;
}
if (getComparator()(t, node->value)) {
std::shared_ptr<Node> newLeft = insert(tree, t, node->left);
node->setLeft(newLeft);
}
else {
std::shared_ptr<Node> newRight = insert(tree, t, node->right);
node->setRight(newRight);
}
return node;
}
Se la rimozione di un nodo, utilizzare una versione diversa di removeLeft e removeRight sostituendo subtreeSize++; con subtreeSize--;. Algoritmi per rotateLeft e rotateRight possono essere adattati senza molto problema. Quanto segue è stato testato e approvato:
template <typename T, typename Comparator>
void BinaryTree<T, Comparator>::rotateLeft (std::shared_ptr<Node>& node) { // The root of the rotation is 'node', and its right child is the pivot of the rotation. The pivot will rotate counter-clockwise and become the new parent of 'node'.
std::shared_ptr<Node> pivot = node->right;
pivot->subtreeSize = node->subtreeSize;
pivot->depthFromRoot--;
node->subtreeSize--; // Since 'pivot' will no longer be in the subtree rooted at 'node'.
const std::size_t a = pivot->left ? pivot->left->subtreeHeight + 1 : 0; // Need to establish node->heightOfSubtree before pivot->heightOfSubtree is established, since pivot->heightOfSubtree depends on it.
node->subtreeHeight = node->left ? std::max(a, node->left->subtreeHeight + 1) : std::max<std::size_t>(a,1);
if (pivot->right) {
node->subtreeSize -= pivot->right->subtreeSize; // The subtree rooted at 'node' loses the subtree rooted at pivot->right.
pivot->subtreeHeight = std::max (pivot->right->subtreeHeight, node->subtreeHeight) + 1;
}
else
pivot->subtreeHeight = node->subtreeHeight + 1;
node->depthFromRoot++;
decreaseDepthFromRoot(pivot->right); // Recursive call for the entire subtree rooted at pivot->right.
increaseDepthFromRoot(node->left); // Recursive call for the entire subtree rooted at node->left.
pivot->parent = node->parent;
if (pivot->parent) { // pivot's new parent will be its former grandparent, which is not nullptr, so the grandparent must be updated with a new left or right child (depending on whether 'node' was its left or right child).
if (pivot->parent->left == node)
pivot->parent->left = pivot;
else
pivot->parent->right = pivot;
}
node->setRightSimple(pivot->left); // Since pivot->left->value is less than pivot->value but greater than node->value. We use the NoSizeAdjustment version because the 'subtreeSize' values of 'node' and 'pivot' are correct already.
pivot->setLeftSimple(node);
if (node == root) {
root = pivot;
root->parent = nullptr;
}
}
dove
inline void decreaseDepthFromRoot (std::shared_ptr<Node>& node) {adjustDepthFromRoot(node, -1);}
inline void increaseDepthFromRoot (std::shared_ptr<Node>& node) {adjustDepthFromRoot(node, 1);}
template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::adjustDepthFromRoot (std::shared_ptr<Node>& node, int adjustment) {
if (!node)
return;
node->depthFromRoot += adjustment;
adjustDepthFromRoot (node->left, adjustment);
adjustDepthFromRoot (node->right, adjustment);
}
Ecco l'intero codice: http://ideone.com/d6arrv
Questa soluzione BFS-come è abbastanza semplice. Semplicemente salti livelli uno per uno.
def getHeight(self,root, method='links'):
c_node = root
cur_lvl_nodes = [root]
nxt_lvl_nodes = []
height = {'links': -1, 'nodes': 0}[method]
while(cur_lvl_nodes or nxt_lvl_nodes):
for c_node in cur_lvl_nodes:
for n_node in filter(lambda x: x is not None, [c_node.left, c_node.right]):
nxt_lvl_nodes.append(n_node)
cur_lvl_nodes = nxt_lvl_nodes
nxt_lvl_nodes = []
height += 1
return height
