Trova in modo efficiente se l'albero di ricerca binario è bilanciato in altezza o no?

Question

Trova in modo efficiente se l'albero di ricerca binario è bilanciato in altezza o no?

#1 da (2 voti)
#2 da (1 voti)

0

Un albero binario è bilanciato in altezza se e solo se i due sottoalberi di root sono bilanciati in altezza e la differenza tra l'altezza dei due sottoalberi è al massimo 1.

Ho implementato un codice in java per scoprire se un albero di ricerca binario è bilanciato in altezza o meno. L'ho fatto in questo modo:

Richiama ricorsivamente la funzione isBalanced(Node) che inizia con root e la condizione di base è se il nodo è null restituisce true. Ma per calcolare l'altezza di un sottoalbero radicato in Node x , devo chiamare una funzione separata getHeight(Node) su quel nodo e usare questa funzione per ottenere e confrontare l'altezza di due sottoalberi di un nodo e restituire di conseguenza un valore booleano.

Ma questa chiamata di funzione separata sta rendendo il mio codice inefficiente, perché in caso di albero di skew quando ogni nodo ha un figlio questa funzione farà sì che la complessità temporale del mio programma sia O(N^2) , N è il numero di vertici.

Quello che voglio sapere è che c'è un modo per rimuovere questa chiamata di funzione separata e continuare a svolgere il lavoro, in modo che possa avere un algoritmo lineare di tempo.

Ecco il mio codice java.

class BST
{
 public Node insert(Node x,int key)
 {
     if(x==null)
      return new Node(key,null,null);
     else if(key>x.key)
     {
         x.right=insert(x.right,key);
         return x;
     }
     else if(key<x.key)
     {
         x.left=insert(x.left,key);
         return x;
     }
     else {x.key=key;return x;}
 }
 public boolean isBalanced(Node root)
 {
     if(root==null)
      return true;
     else
     {
         if(isBalanced(root.left)&&isBalanced(root.right))
         {
             if(Math.abs(getHeight(root.left)-getHeight(root.right))<=1)
              return true;
             else return false;
         }
         else return false;
     }
 }
 public int getHeight(Node x)
 {
     return BFS(x,0);
 }
 public int BFS(Node x,int h)
 {
     if(x==null)
      return h;     
     return Math.max(BFS(x.right,h+1),BFS(x.left,h+1));
 }
 public static void main(String []args)
 {
     BST tree1=new BST();
     Node root=null;
     root=tree1.insert(root,14);
     root=tree1.insert(root,16);
     root=tree1.insert(root,5);
     root=tree1.insert(root,3);
     root=tree1.insert(root,12);
     root=tree1.insert(root,10);
     root=tree1.insert(root,13);
     root=tree1.insert(root,20);
     root=tree1.insert(root,18);
     root=tree1.insert(root,23);   
     root=tree1.insert(root,15);
     System.out.println(tree1.isBalanced(root));
 }
}
class Node
{
 Node left,right;
 int key;
 Node(int key,Node left,Node right)
 {
  this.key=key;
  this.left=left;
  this.right=right;
 }
}

_{Sto ripubblicando questa domanda qui perché non ho ricevuto risposta on Stack Overflow .}

java complexity binary-tree

posta Sumeet 25.06.2015 - 20:34

fonte

2 risposte

Leggi altre domande sui tag java complexity binary-tree

Test della logica con dati esterni [duplicato] Esiste un piano per eliminare le "funzionalità" dalle prossime versioni di javascript? [chiuso]

score 2 · Answer 1

Se bilanciato significa che l'altezza è al massimo log_2(number_of_nodes) + 1 , Suggerisco che un algoritmo potrebbe assomigliare a questo:

# define a tree
tree := null | (left : tree, right : tree)

# check if a tree is balanced
is_balanced(tree) {
    maximum_height, number_of_elements = walk(tree)
    return maximum_height <= 1 + log_with_base_2(number_of_elements) 
}

# walk the tree
walk(tree) {
    if tree is null return 0, 0
    left_height,  left_number_of_elements  = walk(tree.left )
    right_height, right_number_of_elements = walk(tree.right)
    height = 1 + max(left_height, right_height)
    number_of_elements = left_number_of_elements + right_number_of_elements + 1
    return height, number_of_elements
}

L'algoritmo percorre l'intero albero una volta. walk(tree) = O(number_of_nodes(tree)) = O(n) .

Durante i test, tieni presente questo caso:

  x
  |\
  x x
 /| |\
  x x x
     \
      x

Le altezze degli alberi secondari sono disattivate di una unità, ma l'intero albero non è bilanciato.

score 1 · Answer 2

Per calcolare l'altezza, devi attraversare l'albero, possibilmente usando la ricorsione. Per verificare che sia equilibrato, devi attraversarlo esattamente allo stesso modo. Quindi questi modi possono probabilmente essere combinati.

Sono stanco e non riesco a pensare ad un buon nome per una tale funzione in questo momento, e ho la sensazione che la soluzione sia brutta e probabilmente c'è un modo migliore. Ma funzionerà.

Diciamo che creiamo una funzione find_height_and_balance , che restituisce -1 se l'albero non è bilanciato e l'altezza dell'albero, se lo è.

Qualcosa come:

int find_height_and_balance(node) {
    if (node == null) {
        return 0  // A leaf is balanced and height 0
    }

    int left = find_height_and_balance(node.left)
    if (left == -1) { return -1 }
    int right = find_height_and_balance(node.right)
    if (right == -1) { return -1 }

    if (Math.abs(left - right) > 1) {
        return -1  // The difference in heights is larger than 1
    }

    return max(left, right) + 1 # Return height

(se il nome della funzione somiglia a Python, è perché ho scritto Python per primo e poi l'ho cambiato ...)

Modifica: si noti che la definizione di "bilanciata" e il caso di test nella risposta dell'utente sono diversi; questo codice controlla la tua definizione, ma penso che la definizione sia sbagliata.