왜냐하면.. 많은 변종이 있고,

단일의 알고리즘이 없어

그래서 llm이 제대로 못 만들겠데

ㅎㅎ

그러나...

FreeBSD에 weak avl 트리 구현되어 있는게 있거든.

        #include <sys/tree.h>

        #include <err.h>

        #include <stdio.h>

        #include <stdlib.h>

        struct node {

                RB_ENTRY(node) entry;

                int i, sum;

        };

        int

        intcmp(struct node *e1, struct node *e2)

        {

                return (e1->i < e2->i ? -1 : e1->i > e2->i);

        }

        int

        sumaug(struct node *e)

        {

                e->sum = e->i;

                if (RB_LEFT(e, entry) != NULL)

                        e->sum += RB_LEFT(e, entry)->sum;

                if (RB_RIGHT(e, entry) != NULL)

                        e->sum += RB_RIGHT(e, entry)->sum;

        }

        #define RB_AUGMENT(entry) sumaug(entry)

        RB_HEAD(inttree, node) head = RB_INITIALIZER(&head);

        RB_GENERATE(inttree, node, entry, intcmp)

        int testdata[] = {

                20, 16, 17, 13, 3, 6, 1, 8, 2, 4, 10, 19, 5, 9, 12, 15, 18,

                7, 11, 14

        };

        void

        print_tree(struct node *n)

        {

                struct node *left, *right;

                if (n == NULL) {

                        printf("nil");

                        return;

                }

                left = RB_LEFT(n, entry);

                right = RB_RIGHT(n, entry);

                if (left == NULL && right == NULL)

                        printf("%d", n->i);

                else {

                        printf("%d(", n->i);

                        print_tree(left);

                        printf(",");

                        print_tree(right);

                        printf(")");

                }

        }

        int

        main(void)

        {

                int i;

                struct node *n;

                for (i = 0; i < sizeof(testdata) / sizeof(testdata[0]); i++) {

                        if ((n = malloc(sizeof(struct node))) == NULL)

                                err(1, NULL);

                        n->i = testdata[i];

                        RB_INSERT(inttree, &head, n);

                }

                RB_FOREACH(n, inttree, &head) {

                        printf("%d\n", n->i);

                }

                print_tree(RB_ROOT(&head));

                printf("Sum of values = %d0, RB_ROOT(&head)->sum);

                printf("\n");

                return (0);

        }