全部博文（51）
分类： C/C++
2016-08-25 15:06:30
源码来自OpenWrt，本文对avl的init，插入，删除相关代码进行分析；最后给出了一个例子，来说明插入/删除node时，状态转变过程的截图；
主要结构如下：
|
/** * This element is a member of a avl-tree. It must be contained in all * larger structs that should be put into a tree. */ struct avl_node { /** * Linked list node for supporting easy iteration and multiple * elments with the same key. * * this must be the first element of an avl_node to * make casting for lists easier */ struct list_head list;
/** * Pointer to parent node in tree, NULL if root node */ struct avl_node *parent;
/** * Pointer to left child */ struct avl_node *left;
/** * Pointer to right child */ struct avl_node *right;
/** * pointer to key of node */ const void *key;
/** * balance state of AVL tree (0,-1,+1) */ signed char balance;
/** * true if first of a series of nodes with same key */ bool leader; }; /** * This struct is the central management part of an avl tree. * One of them is necessary for each avl_tree. */ struct avl_tree { /** * Head of linked list node for supporting easy iteration * and multiple elments with the same key. */ struct list_head list_head;
/** * pointer to the root node of the avl tree, NULL if tree is empty */ struct avl_node *root;
/** * number of nodes in the avl tree */ unsigned int count;
/** * true if multiple nodes with the same key are * allowed in the tree, false otherwise */ bool allow_dups;
/** * pointer to the tree comparator * * First two parameters are keys to compare, * third parameter is a copy of cmp_ptr */ avl_tree_comp comp;
/** * custom pointer delivered to the tree comparator */ void *cmp_ptr; }; |
avl_init(&services, avl_strcmp, false, NULL);
|
/** * Initialize a new avl_tree struct * @param tree pointer to avl-tree * @param comp pointer to comparator for the tree * @param allow_dups true if the tree allows multiple * elements with the same //是否可以复用，多个nodes使用同样的key * @param ptr custom parameter for comparator */ void avl_init(struct avl_tree *tree, avl_tree_comp comp, bool allow_dups, void *ptr) { INIT_LIST_HEAD(&tree->list_head); tree->root = NULL; tree->count = 0; tree->comp = comp; tree->allow_dups = allow_dups; tree->cmp_ptr = ptr; } |
|
int avl_strcmp(const void *k1, const void *k2, void *ptr) { return strcmp(k1, k2); } 若str1=str2，则返回零；
若str1 若str1>str2，则返回正数。 |
avl_insert(&services, &s->avl);
关于node->balance，初值为0；
若节点左侧加入新node，则node->balance--;
若节点右侧加入新node，则node->balance++;
|
/** * Inserts an avl_node into a tree * @param tree pointer to tree * @param new pointer to node * @return 0 if node was inserted successfully, -1 if it was not inserted * because of a key collision */ int avl_insert(struct avl_tree *tree, struct avl_node *new) { struct avl_node *node, *next, *last; int diff;
new->parent = NULL;
new->left = NULL; new->right = NULL;
new->balance = 0; new->leader = true;
if (tree->root == NULL) { list_add(&new->list, &tree->list_head); tree->root = new; tree->count = 1; return 0; }
node = avl_find_rec(tree->root, new->key, tree->comp, tree->cmp_ptr, &diff); //查找new的插入点；
last = node;
while (!list_is_last(&last->list, &tree->list_head)) { //拥有同样key值的链表； next = avl_next(last); if (next->leader) { break; } last = next; }
diff = (*tree->comp) (new->key, node->key, tree->cmp_ptr);//再次比较key值
if (diff == 0) { if (!tree->allow_dups) //不允许复用key值 return -1;
new->leader = 0;
avl_insert_after(tree, last, new); //允许复用key值； return 0; } //node为最末尾的节点，若它存在左子树或者右子树，那么new插入到空的一边就可以了 if (node->balance == 1) { avl_insert_before(tree, node, new); //插入到node左面
node->balance = 0; new->parent = node; node->left = new; return 0; }
if (node->balance == -1) { avl_insert_after(tree, last, new); //插入到last右面
node->balance = 0; new->parent = node; node->right = new; return 0; }
if (diff < 0) { //插入到左面 avl_insert_before(tree, node, new);
node->balance = -1; new->parent = node; node->left = new; post_insert(tree, node); return 0; }
avl_insert_after(tree, last, new); //插入到右面
node->balance = 1; new->parent = node; node->right = new; post_insert(tree, node); return 0; } |
|
static void avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node) { list_add(&node->list, &pos_node->list); tree->count++; } |
|
static void avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node) { list_add_tail(&node->list, &pos_node->list); tree->count++; } |
|
static void post_insert(struct avl_tree *tree, struct avl_node *node) { struct avl_node *parent = node->parent;
if (parent == NULL) //node为root node return;
if (node == parent->left) { //node为左子树 parent->balance--; //减一
if (parent->balance == 0) //已平衡； return;
if (parent->balance == -1) { //parent node为-1，继续判断上层节点是否平衡； post_insert(tree, parent); return; }
if (node->balance == -1) { //parent->balance == -2 & node->balance == -1 ; LL type avl_rotate_right(tree, parent); return; } //parent->balance == -2 & node->balance ==1; LR type avl_rotate_left(tree, node); avl_rotate_right(tree, node->parent->parent); return; }
parent->balance++; //node is right child;
if (parent->balance == 0) //ok return;
if (parent->balance == 1) { //判断上层是否平衡 post_insert(tree, parent); return; }
if (node->balance == 1) { //parent->balance == 2&& node->balance==1; RR type avl_rotate_left(tree, parent); return; }
avl_rotate_right(tree, node); //parent->balance == 2&& node->balance== -1 ;; RL type avl_rotate_left(tree, node->parent->parent); } |
|
static void avl_rotate_right(struct avl_tree *tree, struct avl_node *node) { struct avl_node *left, *parent;
left = node->left; parent = node->parent;
left->parent = parent; node->parent = left;
if (parent == NULL) tree->root = left;
else { if (parent->left == node) parent->left = left;
else parent->right = left; }
node->left = left->right; left->right = node;
if (node->left != NULL) node->left->parent = node;
node->balance += 1 - avl_min(left->balance, 0); left->balance += 1 + avl_max(node->balance, 0); }
static void avl_rotate_left(struct avl_tree *tree, struct avl_node *node) { struct avl_node *right, *parent;
right = node->right; parent = node->parent;
right->parent = parent; node->parent = right;
if (parent == NULL) tree->root = right;
else { if (parent->left == node) parent->left = right;
else parent->right = right; }
node->right = right->left; right->left = node;
if (node->right != NULL) node->right->parent = node;
node->balance -= 1 + avl_max(right->balance, 0); right->balance -= 1 - avl_min(node->balance, 0); } |
返回一个node和cmp_result，
若相等cmp_result == 0，存在；
若cmp_result < 0，添加到node left侧；
若cmp_result > 0，添加到node right侧；
|
static struct avl_node * avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *cmp_ptr, int *cmp_result) { int diff;
diff = (*comp) (key, node->key, cmp_ptr); *cmp_result = diff;
if (diff < 0) { if (node->left != NULL) //key较小，则在左侧递归查找 return avl_find_rec(node->left, key, comp, cmp_ptr, cmp_result);
return node; }
if (diff > 0) { if (node->right != NULL) //key较大，则在右侧递归查找 return avl_find_rec(node->right, key, comp, cmp_ptr, cmp_result);
return node; }
return node; } |
|
/** * Remove a node from an avl tree * @param tree pointer to tree * @param node pointer to node */ void avl_delete(struct avl_tree *tree, struct avl_node *node) { struct avl_node *next; struct avl_node *parent; struct avl_node *left; struct avl_node *right; if (node->leader) { //key值复用，若删除节点为首个节点 if (tree->allow_dups && !list_is_last(&node->list, &tree->list_head) && !(next = avl_next(node))->leader) { //存在相同key的其他节点 next->leader = true; next->balance = node->balance;
parent = node->parent; left = node->left; right = node->right;
next->parent = parent; next->left = left; next->right = right;
if (parent == NULL) tree->root = next;
else { if (node == parent->left) parent->left = next;
else parent->right = next; }
if (left != NULL) left->parent = next;
if (right != NULL) right->parent = next; }
else avl_delete_worker(tree, node); //拥有唯一key值 }
avl_remove(tree, node); //删除key值相同的，非首个node } |
|
static void avl_delete_worker(struct avl_tree *tree, struct avl_node *node) { struct avl_node *parent, *min;
parent = node->parent;
if (node->left == NULL && node->right == NULL) { //node 为叶子节点 if (parent == NULL) { tree->root = NULL; return; }
if (parent->left == node) { //左叶子节点 parent->left = NULL; parent->balance++;
if (parent->balance == 1) return;
if (parent->balance == 0) { avl_post_delete(tree, parent); return; }
if (parent->right->balance == 0) { avl_rotate_left(tree, parent); return; }
if (parent->right->balance == 1) { avl_rotate_left(tree, parent); avl_post_delete(tree, parent->parent); return; }
avl_rotate_right(tree, parent->right); avl_rotate_left(tree, parent); avl_post_delete(tree, parent->parent); return; }
if (parent->right == node) { parent->right = NULL; parent->balance--;
if (parent->balance == -1) return;
if (parent->balance == 0) { avl_post_delete(tree, parent); return; }
if (parent->left->balance == 0) { avl_rotate_right(tree, parent); return; }
if (parent->left->balance == -1) { avl_rotate_right(tree, parent); avl_post_delete(tree, parent->parent); return; }
avl_rotate_left(tree, parent->left); avl_rotate_right(tree, parent); avl_post_delete(tree, parent->parent); return; } }
if (node->left == NULL) { //非叶子node，左子树为空 if (parent == NULL) { tree->root = node->right; node->right->parent = NULL; return; }
node->right->parent = parent;
if (parent->left == node) parent->left = node->right;
else parent->right = node->right;
avl_post_delete(tree, node->right); return; }
if (node->right == NULL) { //右子树为空 if (parent == NULL) { tree->root = node->left; node->left->parent = NULL; return; }
node->left->parent = parent;
if (parent->left == node) parent->left = node->left;
else parent->right = node->left;
avl_post_delete(tree, node->left); return; }
min = avl_local_min(node->right); //左右子树非空；右子树上选择最小节点； avl_delete_worker(tree, min); //从avl数中删除min node； parent = node->parent;
min->balance = node->balance; //使用node节点，替换掉node min->parent = parent; min->left = node->left; min->right = node->right;
if (min->left != NULL) min->left->parent = min;
if (min->right != NULL) min->right->parent = min;
if (parent == NULL) { tree->root = min; return; }
if (parent->left == node) { parent->left = min; return; }
parent->right = min; } |
左孩子的右子树+1，
两次旋转；先左在右；
上图中balance有错误；
5->balance = -1; 8->balance=-2
4->balance = -1;
