Re: AVL tree silently accept duplicate keys

On Mon, Aug 10, 2020 at 10:25 AM Erwin Kalvelagen <erwin@amsterdamoptimization.com> wrote:

Operator error!!
----------------------------------------------------------------
Erwin Kalvelagen
Amsterdam Optimization Modeling Group
erwin@amsterdamoptimization.com
https://www.amsterdamoptimization.com
----------------------------------------------------------------

On Mon, Aug 10, 2020 at 9:41 AM Andrew Makhorin <mao@gnu.org> wrote:
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 !
>
>
>

From:	Erwin Kalvelagen
Subject:	Re: AVL tree silently accept duplicate keys
Date:	Mon, 10 Aug 2020 10:27:49 -0400