AVL树在C中带有迭代插入

Question

我正在编码一般的avl树是对我自己的挑战，如果我能正确地做到的其他CS学生的资源。

通常，我首先实现了有效的递归插入函数。但是，由于效率，我尝试实现相同的功能，但是迭代。我在网上搜索并找到了很多实现，但其余的代码总是与我的不同，这使我继续尝试从头开始创建实施。

这些是相关的定义类型：

typedef struct info {
    int id;
    char name[200];
} data;
typedef struct avl_node {
    void * data;
    struct avl_node * left;
    struct avl_node * right;
    int height;
} * avl_node_t;
typedef struct avl_tree {
    avl_node_t root;
    int num_nodes;
    int (*less)(const void * first, const void * second);
    int (*key)(const void * data);
} * avl_t;

，如下所示是迭代插入函数（不按预期工作）：

avl_node_t
avl_insert(avl_node_t node, void * data)
{
    long key1 = 0, key2 = 0;
    avl_node_t aux = NULL;
    while (1) {
        if (node == NULL) {
            node = avl_node_create(data);
            break;
        }
        key1 = key((void*)&data);
        key2 = key((void*)&(node->data));
        aux = node;
        if (less((void*)&key1, (void*)&key2))
            node = node->left;
        else
            node = node->right;
    }
    if (aux != NULL) {
        if (less((void*)&key1, (void*)&key2))
            aux->right = node;
        else if (less((void*)&key2, (void*)&key1))
            aux->left = node;
    }
    node = avl_balance(node);
    return node;
}

avl_balance函数被定义为这样的：

static short
balance(avl_node_t node)
{
    if (node == NULL)
        return 0;
    return avl_node_height(node->left) - avl_node_height(node->right);
}
static avl_node_t
avl_balance(avl_node_t node)
{
    short balance_factor;
    if (node == NULL)
        return node;
    balance_factor = balance(node);
    if (balance_factor > 1)
        if (balance(node->left) >= 0)
            node = avl_rotRight(node);
        else
            node = avl_rotLeftRight(node);
    else if (balance_factor < -1)
        if (balance(node->right) <= 0)
            node = avl_rotLeft(node);
        else
            node = avl_rotRightLeft(node);
    else
        update_height(node);
    return node;
}

这是我用来测试AVL树的代码：

int main()
{
    data d1 = { 1, "we are number one" };
    data d2 = { 2, "boneless pizza" };
    data d3 = { 3, "hehe" };
    data d4 = { 4, "achoo" };
    data d5 = { 5, "I like C" };
    data d6 = { 6, "Assembly is cool too" };
    data d7 = { 7, "SIGSEGV" };
    avl_t tree = avl_create();
    avl_node_t root = tree->root;
    root = avl_insert(root, (void*)&d1);
    traverse(root);
    root = avl_insert(root, (void*)&d2);
    traverse(root);
    root = avl_insert(root, (void*)&d3);
    root = avl_insert(root, (void*)&d4);
    root = avl_insert(root, (void*)&d5);
    root = avl_insert(root, (void*)&d6);
    root = avl_insert(root, (void*)&d7);
    traverse(root);
    free(tree);
    exit(0);
}

在其中定义了traverse：

void visit(void * d)
{
    data * my_data = (data*)d;
    printf("I am element number %d named %sn", (*my_data).id, (*my_data).name);
    fflush(stdout);
}
void traverse(avl_node_t node)
{
    if (node == NULL)
        return;
    traverse(node->left);
    traverse(node->right);
    visit(node->data);
}

最后，这是我从此测试中获得的输出：

I am element number 1 named we are number one
I am element number 2 named boneless pizza
I am element number 7 named SIGSEGV

预先感谢您。

Answer 1

如果您不介意，我在C 版本中实现了它。

// In the view of C, just omit the template declaration and replace the class with struct
template<typename T>
class AVL_tree{
    private:
        class AVL_Node{  
            public:
                T val;
                AVL_Node* left;
                AVL_Node* right;
                AVL_Node* parent; 
                int height;
                
                // Node Constructor -
                AVL_Node():left{nullptr}, right{nullptr}, parent{nullptr}, val{}, height{0}{}
                AVL_Node(T val): left{nullptr}, right{nullptr}, parent{nullptr}, height{0}, val{val}{}
        };
        AVL_Node* root;
        short (*cmp_func)(T, T);
        
        // Utility -
        void add_child(AVL_Node* prev_nd, AVL_Node* chd_nd){
            if(prev_nd == nullptr){
                this->root = chd_nd;
                return;
            }
                
            // update parent pointer first.
            switch(cmp_func(chd_nd->val, prev_nd->val)){
                case 1:
                    prev_nd->right = chd_nd;
                    break;
                case 0:
                    prev_nd->left = chd_nd;
                    break;
                case -1:
                    cerr << "Warning : The element should not be duplicate." << endl;
                    return;
                default:
                    cerr << "ERROR_MESSAGE : The self-defin compare func should return triple value (1, 0, -1)." << endl;
                    return;
            }
            // update parent pointer of child node
            chd_nd->parent = prev_nd;
        }
        AVL_Node* find_node(T val){
            AVL_Node* prev_ptr = nullptr;
            for(AVL_Node* tmp_ptr = this->root ; tmp_ptr != nullptr ; ){
                prev_ptr = tmp_ptr;
                switch(cmp_func(val, tmp_ptr->val)){
                    case 1:
                        tmp_ptr = tmp_ptr->right;
                        break;
                    case 0:
                        tmp_ptr = tmp_ptr->left;
                        break;
                    case -1:
                        return prev_ptr;
                }
            }
            // for not find the node, return their parent node.
            return prev_ptr;
        }
        int get_max(int a, int b){ return (a >= b) ? a : b; }
        int get_height(AVL_Node* ptr_nd){
            if(ptr_nd == nullptr)
                return -1;
            return ptr_nd->height;
        }
        int cal_balance(AVL_Node* nd_ptr){ return get_height(nd_ptr->left) - get_height(nd_ptr->right); }
        AVL_Node* Right_rotate(AVL_Node* curr_nd){
            AVL_Node* lft_chd = curr_nd->left;
            AVL_Node* rgt_suc = lft_chd->right;
            // Perform rotation
            lft_chd->right = curr_nd;
            curr_nd->left = rgt_suc;
            // update parent pointer of current pointed node and child node 
            lft_chd->parent = curr_nd->parent;
            curr_nd->parent = lft_chd;
            if(rgt_suc != nullptr)
                rgt_suc->parent = curr_nd;
        
            // Update heights
            lft_chd->height = get_max(get_height(lft_chd->left), get_height(lft_chd->right)) + 1;
            curr_nd->height = get_max(get_height(curr_nd->left), get_height(curr_nd->right)) + 1;
            return lft_chd;
        }
        AVL_Node* Left_rotate(AVL_Node* curr_nd){
            AVL_Node* rgt_chd =  curr_nd->right;
            AVL_Node* lft_suc = rgt_chd->left;
        
            // Perform rotation
            rgt_chd->left = curr_nd;
            curr_nd->right = lft_suc;
            // update parent pointer of current pointed node and child node 
            rgt_chd->parent = curr_nd->parent;
            curr_nd->parent = rgt_chd;
            if(lft_suc != nullptr)
                lft_suc->parent = curr_nd;
            // Update heights
            rgt_chd->height = get_max(get_height(rgt_chd->left), get_height(rgt_chd->right)) + 1;
            curr_nd->height = get_max(get_height(curr_nd->left), get_height(curr_nd->right)) + 1;
            return rgt_chd;
        }
        void splice(AVL_Node* ptr_nd){
            /* remove node confirm that the ptr_nd have successor in single side.
                                                                   Case 1.   ;    Case 2.   */
            AVL_Node* succsor_nd = (ptr_nd->left != nullptr) ? ptr_nd->left : ptr_nd->right;
            
            if(ptr_nd == this->root){  // for remove the root.
                this->root = succsor_nd;
            }else{              
                AVL_Node* par_nd = ptr_nd->parent;
                if(par_nd->left == ptr_nd)
                    par_nd->left = succsor_nd;
                else
                    par_nd->right = succsor_nd;
                if(succsor_nd != nullptr) succsor_nd->parent = par_nd;
            }
        }
    public:
        enum Order{  // for the order traversal.
            pre_order,
            post_order,
            in_order
        };
        // Constructor -
        AVL_tree():root{nullptr}, cmp_func{&defau_cmp<T>}{}
        AVL_tree(short (*def_cmp_func)(T, T)):root{nullptr}, cmp_func{def_cmp_func}{}
        
        // Operation - 
        void insert(T val){
            // BST insertion operation
            AVL_Node* prev_nd = find_node(val);  
            AVL_Node* chd_nd = new AVL_Node(val);
            add_child(prev_nd, chd_nd);
            
            // Balance the tree
            for(AVL_Node* nd_ptr = prev_nd ; nd_ptr != nullptr ; nd_ptr = nd_ptr->parent){
                const int& bf = cal_balance(nd_ptr);
                
                // Left bias unbalance
                if( bf > 1 ){       
                    if(val > nd_ptr->left->val)
                        nd_ptr->left = Left_rotate(nd_ptr->left);
                    // update parent's pointer
                    AVL_Node* par_ptr = nd_ptr->parent;
                    if(par_ptr != nullptr && par_ptr->right == nd_ptr)
                        par_ptr->right = Right_rotate(nd_ptr);
                    else if(par_ptr != nullptr && par_ptr->left == nd_ptr)
                        par_ptr->left = Right_rotate(nd_ptr);
                    else
                        Right_rotate(nd_ptr);
                    
                // Right bias unbalance
                }else if(bf < -1){      
                    if(val < nd_ptr->right->val)
                        nd_ptr->right = Right_rotate(nd_ptr->right);
                    // update parent's pointer
                    AVL_Node* par_ptr = nd_ptr->parent;
                    if(par_ptr != nullptr && par_ptr->right == nd_ptr)
                        par_ptr->right = Left_rotate(nd_ptr);
                    else if(par_ptr != nullptr && par_ptr->left == nd_ptr)
                        par_ptr->left = Left_rotate(nd_ptr);
                    else  // nd_ptr equal root 
                        Left_rotate(nd_ptr);
                // else, the sub-tree is already balanced
                }else{  
                    nd_ptr->height = get_max(get_height(nd_ptr->left), get_height(nd_ptr->right)) + 1;
                } 
                // finally update the new root pointer 
                if(nd_ptr->parent == nullptr)
                    this->root = nd_ptr;
            }
        }
        // remove operation is still working on it though.
        // Smart_queue just like a queue offer general interface, you can use stl-container.
        void BF_print(){
            Smart_queue<AVL_Node*> nd_que(this->root);
            while(!nd_que.is_empty()){
                AVL_Node* tmp_ptr = nd_que.pop();
                if(tmp_ptr == nullptr)
                    continue;
                cout << tmp_ptr->val << " ";
                nd_que.push(tmp_ptr->left);
                nd_que.push(tmp_ptr->right);
            }
        }
};