Re: AVL tree silently accept duplicate keys

[Andrew Makhorin]

On Mon, 2020-08-10 at 14:28 +0200, Domingo Alvarez Duarte wrote:
> Hello !
> 
> Replacing usages of AVL tree by SplayTree I found that AVL tree
> silently 
> accepts duplicate keys on "avl_insert_node" see example bellow, there
> is 
> only one way to find by key "avl_find_node" which make it prone to
> write 
> incorrect code:
> 

AVL routines are not intended to be used on API level. Formally, these
routines are not available to the user.

Both AVL and splay trees take logarithmic time, so there is not much
sense to use the latter. To really reduce the search time it would be
better to use hashing.


PS: Please post messages not related to bug reports to help-glpk rather
than to bug-glpk. Thanks.


> ====
> 
> #include <stdio.h>
> #include <stdlib.h>
> #include "avl.h"
> 
> int main(int argc, char *argv[])
> {
>      AVL *tree = avl_create_tree(avl_strcmp, NULL);
>      AVLNODE *node1 = avl_insert_node(tree, "one");
>      printf("node1 = %p\n", node1);
>      AVLNODE *node2 = avl_insert_node(tree, "one");
>      printf("node2 = %p\n", node2);
>      AVLNODE *node3 = avl_insert_node(tree, "one");
>      printf("node3 = %p\n", node3);
>      AVLNODE *node = avl_find_node(tree, "one");
>      printf("node = %p\n", node);
>      avl_delete_node(tree, node1);
>      node = avl_find_node(tree, "one");
>      printf("node = %p\n", node);
>      avl_delete_node(tree, node2);
>      node = avl_find_node(tree, "one");
>      printf("node = %p\n", node);
>      avl_delete_tree(tree);
>      return 0;
> }
> 
> ====
> 
> Build:
> 
> ====
> 
> gcc -g -o test-avl test-avl.c -I../src/misc -I../src
> ../src/.libs/libglpk.a
> 
> ====
> 
> Output:
> 
> =====
> 
> ./test-avl
> node1 = 0x55f599e6d908
> node2 = 0x55f599e6d940
> node3 = 0x55f599e6d978
> node = 0x55f599e6d940
> node = 0x55f599e6d940
> node = 0x55f599e6d978
> 
> =====
> 
> Cheers !
> 
> 
>