Esta página é um anexo da página BSTs: operações adicionais.

Exercícios sobre o método min( )

1. Toda BST tem um mínimo?

   RESPOSTA: Não. A árvore vazia não tem mínimo. (Mas esta é a único exceção.)  O método min() poderia enfrentar isso de duas maneiras:  (1) ao receber uma árvore vazia, devolver alguma coisa que não possa ser confundida com uma resposta válida;  (2) dizer claramente na documentação que não aceita árvore vazia como argumento.   Vamos adotar a primeira alternativa e devolver null para indicar que a BST em questão não tem mínimo.

2. Discuta e critique (se for o caso) a seguinte implementação do método min() na classe BST:

       public Key min() {
          if (root == null) return null;
          return min(root).key;
       }
       private Node min(Node x) {  // recebe x != null
          if (x.left == null) return x;
          return min(x.left);
       }
   

3. Discuta e critique (se for o caso) a seguinte implementação do método min() na classe BST:

       public Node min() {
          if (root == null) return null;
          return min(root);
       }
       private Node min(Node x) { 
          if (x.left == null) return x;
          return min(x.left);
       }
   

4. Discuta e critique (se for o caso) a seguinte implementação do método min() na classe BST:

       public Key min() {
          return min(root);
       }
       private Key min(Node x) { 
          if (x == null) return x;
          if (x.left == null) return x.key;
          return min(x.left);
       }
   

5. Discuta e critique (se for o caso) a seguinte implementação do método min() na classe BST:

       public static Key min() {
          Node x = min(root);
          if (x == null) return null;
          return x.key;
       }
       private static Node min(Node x) {
          if (x == null) return null;
          return min(x.left);
       }
   

6. Discuta e critique (se for o caso) a seguinte implementação do método min() na classe BST:

       public Key min() {
          if (root == null) return null;
          Node x = root;
          while (x.left != null) 
             x = x.left;
          return x.key;
       }