Añadiendo un nuevo nodo en un árbol avl -- performance campo con c campo con tree campo con file-structure camp codereview Relacionados El problema

Adding a new node in an AVL tree


3
vote

problema

Español

Estaba trabajando en una asignación de clase hoy y escribí este código que funciona perfectamente bien. Parece que tiene demasiada "si las declaraciones", y estaba pensando que podría ser escritas mucho mejor que esto. (Todavía soy un principiante en C).

¿Sugiere alguna técnica nueva que pueda usar / aprender a evitar tantos 99887766655443333 y cómo podría mejorar este código sin hacerlo mucho más largo o complejo?

El código es una parte de un código mucho mayor para agregar un nuevo nodo en un árbol AVL.

  if (avlt->root == NULL) {     new = &(avlt->root);        parent = NULL; } if (avlt->root != NULL) {     parent = avlt->root;     while (1)     {         if (parent->value > value)         {             if (parent->left) parent = parent->left;             else             {                 new = &(parent->left);                 break;             }         }         else if (parent->value < value)         {             if (parent->right) parent = parent->right;             else             {                 new = &(parent->right);                 break;             }         }         else return;     } }   

Estas son las estructuras, tal vez pueden ser útiles para que usted entienda el código:

  struct AVLNode {   struct AVLNode* left;        struct AVLNode* right;       struct AVLNode* parent;   int value;   int height; };  struct AVLTree {   struct AVLNode* root;   int numberOfNodes; };  typedef struct AVLNode AVLNode; typedef struct AVLTree AVLTree;   
Original en ingles

I was working on a class assignment today and I wrote this code which works perfectly fine. It looks tho kind of has too much 'if statements' in it, and I was thinking that it could be written much better than this. (I'm still a beginner in C).

Do you suggest any new techniques that I could use/learn to avoid so many if statements and how could you improve this code without making it much longer or complex?

The code is a part of much bigger code to add a new node in an AVL tree.

if (avlt->root == NULL) {     new = &(avlt->root);        parent = NULL; } if (avlt->root != NULL) {     parent = avlt->root;     while (1)     {         if (parent->value > value)         {             if (parent->left) parent = parent->left;             else             {                 new = &(parent->left);                 break;             }         }         else if (parent->value < value)         {             if (parent->right) parent = parent->right;             else             {                 new = &(parent->right);                 break;             }         }         else return;     } } 

These are the structs, maybe they can be useful for you to understand the code:

struct AVLNode {   struct AVLNode* left;        struct AVLNode* right;       struct AVLNode* parent;   int value;   int height; };  struct AVLTree {   struct AVLNode* root;   int numberOfNodes; };  typedef struct AVLNode AVLNode; typedef struct AVLTree AVLTree; 
           

Lista de respuestas

3
 
vote

Complejidad

Un método para determinar qué tan complejo es su código, se llama complejidad ciclomática . Básicamente, usted cuenta el número de sucursales en el código para determinar su complejidad. Cuento alrededor de 10 en el fragmento de código anterior. Una complejidad ciclomática de 10 a menudo se considera el máximo que debe tener en un buen código legible. (Esto es por supuesto subjetivo). Por ese estándar, este código está bien. Sin embargo, creo que el código podría ser más claro, aunque.

Bucles infinitos

Generalmente odio los bucles infinitos en código a menos que sea algo de nivel superior como un bucle de eventos que de manera realista nunca debe detenerse. El bucle infinito que ha creado no es uno de esos casos. Tiene un criterio muy claro para detenerse. Cuando el valor sea mayor que el mayor valor en esta ruta, o menor que el valor mínimo a lo largo de esta ruta, o igual a cualquier valor a lo largo de la ruta. La fijación hará que el código sea más claro, aunque no sé si reducirá el número de condiciones para verificar. Podría valer la pena romperlo en una función separada. Algo así:

  void whateverFunctionThisIs(AVLTree* avlt) {     //...     if (avlt->root == NULL) {         new = &(avlt->root);            parent = NULL;     }     else     {         new = findPositionInTree(avlt->root);     }          if (new == NULL) {         return;     }     // ... }   

que reduce inmediatamente la complejidad de esa función de 10 a 3. Ahora podemos reescribir el bucle en su propia función como esta:

  AVLNode* findPositionInTree(AVLNode* parent) {     struct AVLNode* new = NULL;          int found = 0;     do {         if (parent->value > value)          {             if (parent->left)              {                 parent = parent->left;             }             else              {                 new = &(parent->left);                 found = 1;             }         }         else if (parent->value < value)          {             if (parent->right)              {                 parent = parent->right;             }             else              {                 new = &(parent->right);                 found = 1;             }         }         else          {             found = 1;         }     } while (!found);          return new; }   

Aunque tenemos los mismos numerosos de if , parece más claro para mí sin el break y 99887766555443344 Y esta función solo tiene una complejidad ciclomática de 8.

Reduciendo if S

Puede reducir la cantidad de sentencias if65544336 Si realmente necesita usar parent después de que finalice el bucle invirtiendo el sentido del interno, la mayoría if s. Por ejemplo, en lugar de:

  if (parent->right)  {     parent = parent->right; } else {     new = &(parent->right);     found = 1; }   

Podrías hacer esto:

  AVLNode* findPositionInTree(AVLNode* parent) {     struct AVLNode* new = NULL;          int found = 0;     do {         if (parent->value > value)          {             if (parent->left)              {                 parent = parent->left;             }             else              {                 new = &(parent->left);                 found = 1;             }         }         else if (parent->value < value)          {             if (parent->right)              {                 parent = parent->right;             }             else              {                 new = &(parent->right);                 found = 1;             }         }         else          {             found = 1;         }     } while (!found);          return new; } 0  

En este punto AVLNode* findPositionInTree(AVLNode* parent) { struct AVLNode* new = NULL; int found = 0; do { if (parent->value > value) { if (parent->left) { parent = parent->left; } else { new = &(parent->left); found = 1; } } else if (parent->value < value) { if (parent->right) { parent = parent->right; } else { new = &(parent->right); found = 1; } } else { found = 1; } } while (!found); return new; } 1 es AVLNode* findPositionInTree(AVLNode* parent) { struct AVLNode* new = NULL; int found = 0; do { if (parent->value > value) { if (parent->left) { parent = parent->left; } else { new = &(parent->left); found = 1; } } else if (parent->value < value) { if (parent->right) { parent = parent->right; } else { new = &(parent->right); found = 1; } } else { found = 1; } } while (!found); return new; } 2 para que no pueda usarlo para nada en el futuro, así que realmente no me gusta esa idea. Pero elimina las declaraciones de 2 AVLNode* findPositionInTree(AVLNode* parent) { struct AVLNode* new = NULL; int found = 0; do { if (parent->value > value) { if (parent->left) { parent = parent->left; } else { new = &(parent->left); found = 1; } } else if (parent->value < value) { if (parent->right) { parent = parent->right; } else { new = &(parent->right); found = 1; } } else { found = 1; } } while (!found); return new; } 3 Reducir así su complejidad. (Si está utilizando el bucle infinito, entonces el AVLNode* findPositionInTree(AVLNode* parent) { struct AVLNode* new = NULL; int found = 0; do { if (parent->value > value) { if (parent->left) { parent = parent->left; } else { new = &(parent->left); found = 1; } } else if (parent->value < value) { if (parent->right) { parent = parent->right; } else { new = &(parent->right); found = 1; } } else { found = 1; } } while (!found); return new; } 4 se convierte en un solo 99887776655443315 y AVLNode* findPositionInTree(AVLNode* parent) { struct AVLNode* new = NULL; int found = 0; do { if (parent->value > value) { if (parent->left) { parent = parent->left; } else { new = &(parent->left); found = 1; } } else if (parent->value < value) { if (parent->right) { parent = parent->right; } else { new = &(parent->right); found = 1; } } else { found = 1; } } while (!found); return new; } 6 es AVLNode* findPositionInTree(AVLNode* parent) { struct AVLNode* new = NULL; int found = 0; do { if (parent->value > value) { if (parent->left) { parent = parent->left; } else { new = &(parent->left); found = 1; } } else if (parent->value < value) { if (parent->right) { parent = parent->right; } else { new = &(parent->right); found = 1; } } else { found = 1; } } while (!found); return new; } 7 . Pero eso se siente asqueroso.)

 

Complexity

One method for determining how complex your code is, is called cyclomatic complexity. You basically count the number of branches in the code to determine its complexity. I count about 10 in the above code snippet. A cyclomatic complexity of 10 is often considered the maximum you should have in good readable code. (This is of course subjective.) By that standard, this code is fine. I do think the code could be made more clear, though.

Infinite Loops

I generally hate infinite loops in code unless it's some top-level thing like an event loop that realistically should never stop. The infinite loop you've created is not one of those cases. It has a very clear criteria for stopping. When the value is either greater than the greatest value along this path, or less than the minimum value along this path, or equal to any value along the path. Fixing that will make the code clearer, though I don't know if it will reduce the number of conditions to check. It might be worth breaking it out into a separate function. Something like this:

void whateverFunctionThisIs(AVLTree* avlt) {     //...     if (avlt->root == NULL) {         new = &(avlt->root);            parent = NULL;     }     else     {         new = findPositionInTree(avlt->root);     }          if (new == NULL) {         return;     }     // ... } 

That immediately reduces the complexity of that function from 10 to 3. Now we can rewrite the loop in its own function like this:

AVLNode* findPositionInTree(AVLNode* parent) {     struct AVLNode* new = NULL;          int found = 0;     do {         if (parent->value > value)          {             if (parent->left)              {                 parent = parent->left;             }             else              {                 new = &(parent->left);                 found = 1;             }         }         else if (parent->value < value)          {             if (parent->right)              {                 parent = parent->right;             }             else              {                 new = &(parent->right);                 found = 1;             }         }         else          {             found = 1;         }     } while (!found);          return new; } 

Even though we have the same number of if statements, it seems clearer to me without the break and return statements. And this function only has a cyclomatic complexity of 8.

Reducing ifs

You could reduce the number of if statements if you don't actually need to use parent after the loop ends by inverting the sense of the inner-most ifs. For example, instead of:

if (parent->right)  {     parent = parent->right; } else {     new = &(parent->right);     found = 1; } 

you could do this:

if (parent->right != NULL) {     new = &(parent->right);     found = 1; } parent = parent->right; 

At this point parent is NULL so you can't use it for anything in the future, so I really don't like that idea. But it does eliminate 2 if statements thereby reducing your complexity. (If you're using the infinite loop, then the found = 1; becomes just a break and parent is no longer NULL. But that feels gross to me.)

 
 

Relacionados problema

2  Parse la información de unión de Mach-O  ( Parse mach o binding info ) 
Escribí este programa C para abrir un ejecutable / marco de Mach-O y analizar los símbolos externos junto con su marco / biblioteca respectivos. Algunas cosas...

7  Generador de archivos de prueba binaria con suma de comprobación  ( Binary test file generator with checksum ) 
en la lectura Esta pregunta , se me ocurrió que sería útil crear archivos de prueba de acuerdo con la especificación del formato de archivo. Para recubrir, e...

9  Lectura de archivos binarios en formato XTF  ( Reading binary files in xtf format ) 
Tengo algunos miles de archivos binarios que tienen estructuras correspondientes en ellos, seguidas de cualquier número de bytes (este número exacto de bytes ...

4  Leer dimensiones JPEG correctamente  ( Read jpeg dimensions properly ) 
Necesito extraer las dimensiones (ancho y altura) de un archivo JPEG para insertar en un documento HTML. Según el Preguntas frecuentes de compresión de imáge...

7  Analizar un archivo WAV y exportar datos PCM  ( Parse a wav file and export pcm data ) 
Soy Newbie y yo escribimos un código que obtiene un archivo WAV y exporta un archivo RAW (solo PCM) a * .Raw Archivo. Pero estoy confundido acerca de la estru...

11  Código para llenar la tabla de direcciones de importación PE  ( Code to fill pe import address table ) 
Escribí un programa para probar los motores AV contra el cifrado. Cuando se ejecuta, calculará alguna clave, descifrará un ejecutable que tiene en su sección ...

4  Actualizando los registros de archivos de datos  ( Updating data file records ) 
Aprendí a codificar un largo, hace mucho tiempo. preocupaciones El enfoque existente es desordenado y será difícil de mantener. Los errores del sistema ...

2  Reemplace la primera aparición de patrón en el archivo  ( Replace first occurrence of pattern in file ) 
Aquí está mi intento de reemplazar la primera ocurrencia de pattern en el archivo con espacios. La eliminación efectiva, y con suerte me permita "eliminarlo...

0  Script de Analytics Ad-Hoc al módulo / Paquete  ( Ad hoc analytics script to module package ) 
Tengo un proceso de análisis de texto que complete para trabajar. Este proceso minas texto para diferentes cuentas de Twitter y encuentra patrones en los Twee...

4  C Programa que recupera los archivos JPEG perdidos  ( C program that recovers lost jpeg files ) 
Mi estrategia general es cargar un tamaño de bloque (512bytes) en la memoria y verifique si los bloques de los primeros 4 bytes coinciden con los primeros 4 b...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos