avl樹幫助字典實現

Question

我目前正在學習c和算法。 我已經實現了一個模擬字典作爲一棵樹，並想進一步採取我的課程工作，並使用avl樹。

#include <stdio.h> 
#include <stdlib.h> 
#include <ctype.h> 
#define __USE_BSD 
#include <string.h> 

#include "speller.h" 
#include "dict.h" 

typedef struct node * tree_ptr; 
struct node { 
    Key_Type element; // only data is the key itself 
    tree_ptr left, right; 
    // add anything else that you need 
}; 

struct table { 
    tree_ptr head; // points to the head of the tree 
    // add anything else that you need 
}dictable; 

Table initialize_table(/*ignore parameter*/) { 
Table pointtable = malloc(sizeof(struct table)); 
return pointtable; 
} 
//// 


void insertnew(tree_ptr node, Key_Type element) 
{ 
    Key_Type current = node->element; 
    if(strcmp(element,current) < 0)//left 
    { 
     if(node -> left == NULL) 
     { 
     typedef struct node *pointsobject; 
     //new sobject 
    pointsobject structsobject; 
    // memory alocated 
    structsobject = malloc(sizeof(*structsobject)); 
    structsobject-> element = element; 
    structsobject-> left = NULL; 
    structsobject-> right = NULL; 
    node->left = structsobject; 
     } 
     else 
     insertnew(node->left , element); 
     } 
     else if(strcmp(element,current) > 0)//right 
     { 
     if(node -> right == NULL) 
     { 
     typedef struct node *pointsobject; 
     //new sobject 
    pointsobject structsobject; 
    // memory alocated 
    structsobject = malloc(sizeof(*structsobject)); 
    structsobject-> element = element; 
    structsobject-> left = NULL; 
    structsobject-> right = NULL; 
    node->right = structsobject; 
     } 
     else 
     insertnew(node->right, element); 
     } 

} 



Table insert(Key_Type element,Table dictable) { 
    if (dictable -> head == NULL) 
    { 
    typedef struct node *pointsobject; 
    //new sobject 
    pointsobject structsobject; 
    // memory alocated 
    structsobject = malloc(sizeof(*structsobject)); 
    structsobject-> element = element; 
    structsobject-> left = NULL; 
    structsobject-> right = NULL; 
    dictable->head = structsobject; 
    } 
    else 
    { 
    insertnew(dictable->head,element); 
    } 
    return dictable; 
} 

Boolean find(Key_Type element, Table dictable) { 
return FALSE;; 
} 


void printtab(tree_ptr node) 
{ 
    if (node->left != NULL) 
    printtab(node->left); 
    if (node->right != NULL) 
    printtab(node->right); 
    printf("%s",node->element); 
} 

void print_table(Table dictable) { 
printtab(dictable->head); 
} 


void print_stats (Table dictable) { 
} 

我試圖尋找一個在線實現，並找到解釋相當混亂。 有人可以指出我在正確的方向如何將這個樹結構變成一個avl樹結構。

感謝

Answer 1

你可以抓住一些想法here

，我認爲wikipedia解釋顯然不夠了解AVL樹開始