avl是什么意思(算法学习之AVL树)

引言 最近打算补充下算法方面的知识,开一个《算法学习》专栏。 熟悉OpenWRT Linux系统的朋友都知道,OpenWRT里有一个基础库叫libubox,libubox是一些常用的C库的**。 最常用的就是双向链表库...

引言

最近打算补充下算法方面的知识,开一个《算法学习》专栏。

熟悉OpenWRT Linux系统的朋友都知道,OpenWRT里有一个基础库叫libubox,libubox是一些常用的C库的**。 最常用的就是双向链表库”list.h”,和内核的链表头文件<linux/list.h>类似。此外还有md5、base64等常用工具库。 libubox中也有AVL库,本文基于libubox的AVL库代码,学习下AVL树的结构和相关操作。 当然不熟悉OpenWRT或libubox库完全不影响阅读本文。

什么是AVL树

什么是AVL树呢?AVL树是平衡二叉排序树,是以它的发现者Adelson-Velsky和Landis的名字命名的。

首先什么是二叉树:二叉树的每个节点至多只有两棵子树,并且子树有左右之分。

再看平衡二叉树:平衡二叉树的左子树和右子树都是平衡二叉树,且左右子树的深度之差的绝对值不超过1。(树的深度即从根节点到叶子节点的距离或步数)

再看二叉排序树:它的左子树如果不为空,则左子树上的所有节点的值均小于它的根节点的值;它的右子树如果不为空, 则右子树上所有节点的值均大于它根节点的值;它的左右子树也分别是二叉排序数。

二叉排序树又可以称为二叉查找树,所以平衡二叉排序树的英文全称可以是Balanced Binary Search Tree,简称BBST。

平衡二叉排序树通常用在动态数据表查找上。动态数据表的意思是要查找的数据表是动态生成的,不是一个静态的数据表。 这是因为对一个平衡二叉排序树的查找操作,类似于静态排序表的折半查找,效率是很高的,其时间复杂度为O(log n)。 这一点大家手画一个二叉排序树比划一下,就能感受出来。(严格数学证明不在本文范畴内^_^)

AVL树最大的特性是自平衡性。这里自平衡的意思是,当AVL树因为**一个节点而失去平衡时, 只需对节点进行有限且有规律地被称为“左旋”或“右旋”的操作,就可以使树再次平衡。

AVL库代码学习

代码基于libubox的AVL库:libubox/avl.h, libubox/avl.c

AVL树对象定义

先看下AVL树对象的定义:

//AVL节点对象struct avl_node { struct list_head list; //libubox的AVL库将所有节点串成一个双向链表 struct avl_node *parent; //指向父节点 struct avl_node *left; //左子节点 struct avl_node *right; //右子节点 const void *key; //节点存储的值 signed char balance; //平衡因子: 取值0 -1 +1 //-1表示左子树深度大1,+1表示右子树深度大1,0表示一样大 bool leader;};//AVL树对象typedef int (*avl_tree_comp) (const void *k1, const void *k2, void *ptr);struct avl_tree { struct list_head list_head; //libubox的AVL库将所有节点串成一个有序双向链表,方便遍历 struct avl_node *root; //树的根节点 unsigned int count; //树中节点的个数 bool allow_dups; //树中是否允许key相同的节点存在,libubox的AVL库支持**相同的节点 avl_tree_comp comp; //节点大小比较函数 void *cmp_ptr; //比较函数的第三个入参};

接下来看AVL树的3个主要方法:查找、**、删除。

查找节点 avl_find()

查找节点:avl_find()

//在一棵AVL树中,查找值为key的节点,找到则返回找到的节点,找不到则返回空struct avl_node *avl_find(const struct avl_tree *tree, const void *key) struct avl_node *node; int diff; if (tree->root == NULL) return NULL; //树为空则直接返回空 //递归查找节点。入参是节点、key值、比较函数,出参是比较值 node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff) int diff = (*comp) (key, node->key, cmp_ptr); //计算传入的key和节点的key的差值 if (diff < 0) //如果差值小于0,即匹配的key值应该在节点的左子树,继续去左子树寻找 if (node->left != NULL) return avl_find_rec(node->right, key, comp, cmp_ptr, cmp_result); else return node //如果没有左子树了,则返回这个叶节点 if (diff > 0) //如果差值大于0,即匹配的key值应该在节点的右子树,继续去右子树寻找 if (node->right != NULL) return avl_find_rec(node->right, key, comp, cmp_ptr, cmp_result) else return node //如果没有右子树了,则返回这个叶节点 return node //如果差值等于0,则返回这个匹配的节点 return diff == 0 ? node : NULL //如果差值不等于0,表示没找到匹配的节点,返回空**节点 avl_insert()

**节点:avl_insert()。本节包含AVL树的左旋或右旋操作,是AVL树的关键特性所在。

int avl_insert(struct avl_tree *tree, struct avl_node *new) //对要**new节点除了key属性以外的其它属性赋初值 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) //new节点直接**树中 tree->root = new //树的根节点指向这个new节点 tree->count = 1 //此时树的节点个数变为1 return 0 //递归查找与new节点相同或相近的节点node node = avl_find_rec(tree->root, new->key, tree->comp, tree->cmp_ptr, &diff); last = node; //遍历last的next节点,即如果有key值相同的节点,取所有相同key值节点的最后一个 while (!list_is_last(&last->list, &tree->list_head)) { next = avl_next(last); if (next->leader) break; last = next; diff = (*tree->comp) (new->key, node->key, tree->cmp_ptr); //再次计算差值,这一步是多余的? if (diff == 0) if (!tree->allow_dups) return -1; //不允许**相同key值节点时,直接返回-1 new->leader = 0; //leader置0表示已存在相同key值的节点 avl_insert_after(tree, last, new); //将此节点**双向链表 return 0; if (node->balance == 1) //节点的平衡度为1,表示右子树深度大。此时直接将new节点**node节点左侧即可 avl_insert_before(tree, node, new); node->balance = 0; //**new节点后node节点左右深度相同 new->parent = node; node->left = new; //将new节点**到node节点左侧 return 0; if (node->balance == -1) //节点的平衡度为-1,表示左子树深度大。此时直接将new节点**node节点右侧即可 avl_insert_after(tree, last, new); node->balance = 0; //**new节点后node节点左右深度相同 new->parent = node; node->right = new; //将new节点**到node节点的右侧 return 0; if (diff < 0) { //new节点小于node节点,**node节点左侧 avl_insert_before(tree, node, new); node->balance = -1; //左子树深度变大 new->parent = node; node->left = new; //将new节点**到node节点左侧 post_insert(tree, node); //**后处理,后面专门看这个函数 return 0; //new节点大于node节点,**node节点右侧 avl_insert_after(tree, last, new); node->balance = 1; new->parent = node; node->right = new; post_insert(tree, node); //**后处理/* 总结下**逻辑: 在没有相同节点的情况下,**分两大类。 大类一:node节点平衡因子不为0,**new后node节点的平衡因子变为0,不需要后处理 大类二:node节点平衡因子为0,**new后node节点平衡因子不为0,需要后处理 *///接下来看下后处理函数,这里是AVL树最具特点的地方,//即**一个新节点后,如果二叉树不再平衡,只需要特定的左旋右旋操作,二叉树就可再次平衡static void post_insert(struct avl_tree *tree, struct avl_node *node) struct avl_node *parent = node->parent; //**node节点的父节点 if (parent == NULL) return //如果父节点为空,说明node节点就是整个AVL树的根节点,此时什么都不用做 if (node == parent->left) //如果node节点在左侧,即**的new节点在父节点的左子树 parent->balance--; //父节点左侧深度** if (parent->balance == 0) return; //如果父节点左右深度相同,则什么都不用做 if (parent->balance == -1) //如果左子树深度大1,递归调用post_insert,也就是修改所有父节点的balance为-1 post_insert(tree, parent); return; //函数走到此,说明parent->balance=-2,父节点不再平衡,需要旋转操作 if (node->balance == -1) //如果node节点左子树深度大1,则进行右旋操作,后面单独看旋转操作函数 avl_rotate_right(tree, parent); return; //如果node节点右子树大1,则先左旋,再右旋 avl_rotate_left(tree, node); avl_rotate_right(tree, node->parent->parent); return; //以下是node节点在parent节点右侧的情况,与上面的代码对称 parent->balance++; //父节点的右侧深度** if (parent->balance == 0) return; //如果父节点左右深度相同,则什么都不用做 if (parent->balance == 1) //如果左子树深度大1,递归调用post_insert,也就是修改所有父节点的balance为1 post_insert(tree, parent); return; //函数走到此,说明parent->balance=2,父节点不再平衡,需要旋转操作 if (node->balance == 1) //如果node节点右子树深度大1,则进行左旋操作 avl_rotate_left(tree, parent); return; //如果node节点左子树大1,则先右旋,再左旋 avl_rotate_right(tree, node); avl_rotate_left(tree, node->parent->parent);//接下来看一下旋转操作的代码//左旋static void avl_rotate_left(struct avl_tree *tree, struct avl_node *node) struct avl_node *right, *parent; right = node->right; //记录node节点的右节点和父节点 parent = node->parent; right->parent = parent; //右节点和node节点互换位置 node->parent = right; if (parent == NULL) //如果父节点是空,则修改树的根节点 tree->root = right; else //将父节点的子节点node修改为right if (parent->left == node) parent->left = right; else parent->right = right; node->right = right->left; //right的左节点赋给node右节点 right->left = node; //node置为right节点的左节点 if (node->right != NULL) node->right->parent = node; //如果node的右节点不为空,改一下其父节点 node->balance -= 1 + avl_max(right->balance, 0); //修正平衡因子,至少减1,即右子树深度至少减1 right->balance -= 1 - avl_min(node->balance, 0);//右旋。与左旋相反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节点互换 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);删除节点 avl_delete()

删除节点avl_delete()

//删除节点逻辑也比较长,这里只介绍下梗概void avl_delete(struct avl_tree *tree, struct avl_node *node) //如果node是一个重复节点,则直接删除,不涉及二叉树结构的变动 //真正从二叉树删除一个节点 avl_delete_worker(tree, node) //node是叶子节点时: if (node->left == NULL && node->right == NULL) //根据node父节点的平衡因子,进行后处理和旋转操作 //node的左节点为空时: if (node->left == NULL) //将node的右节点代替node节点,并调用avl_post_delete //node的右节点为空时: if (node->right == NULL) //将node的左节点代替node节点,并调用avl_post_delete //node的左右节点都不为空时 min = avl_local_min(node->right); //取node右子树的最小值节点min,此节点要么是叶子节点要么左节点为空 avl_delete_worker(tree, min); //嵌套调用avl_delete_worker,删除这个min节点 //用min节点代替node节点,从而删除了node节点遍历节点

libubox的AVL库已经把所有的节点串成了一个有序的双向链表,所以对AVL树的遍历就变成了对双向链表的遍历。 AVL库对外提供了很多遍历宏,而这些宏的最终调用的是 avl_for_element_range avl_for_element_range_safe avl_for_element_range_reverse avl_for_element_range_reverse_safe

我们来看一下avl_for_element_range

//这里入参first和last是指向包含avl_node结构的大结构体的指针,即遍历的起始大结构体和结束大结构体//element是指向每一个遍历到的大结构体,node_member是avl_node结构体在大结构体中的成员名#define avl_for_element_range(first, last, element, node_member) \ for (element = (first); \ element->node_member.list.prev != &(last)->node_member.list; \ element = avl_next_element(element, node_member))//avl_next_element,即取avl_node.list->next,然后利用container_of取到大结构体#define avl_next_element(element, node_member) \ container_of((&(element)->node_member.list)->next, typeof(*(element)), node_member.list)

再看下全节点遍历avl_for_each_element

//全节点遍历即调用avl_for_element_range,然后入参是AVL树的第一个节点和最后一个节点//即从树的第一个节点 遍历到树的最后一个节点#define avl_for_each_element(tree, element, node_member) \ avl_for_element_range(avl_first_element(tree, element, node_member), \ avl_last_element(tree, element, node_member), \ element, node_member)AVL库实际使用举例

如文章开头提到的AVL树非常适合用在动态数据表查找上,查找的时间复杂度是O(log n)。 我们以有1000个数据的数据表举例,如果这个数据表用线性链表存储,查找一个数据最大可能搜索1000次; 如果用AVL树存储,最大只需要搜索10次。

OpenWRT中有一个重要的**间通信组件ubus,就是用的AVL树维护ubus总线上各对象的信息。

这样在ubus总线上,即使有很多**注册了很多ubus对象,ubusd内部可以根据目标对象ID或名称字符串, 在AVL树上很快搜索到目标对象。

//ubus/ubusd_proto.cstatic int ubusd_handle_lookup() char *objpath; objpath = blob_data(attr[UBUS_ATTR_OBJPATH]); ... obj = avl_find_element(&path, objpath, obj, path) //AVL树查找 ...

  • 发表于 2022-12-02 23:38:18
  • 阅读 ( 117 )
  • 分类:科技

0 条评论

请先 登录 后评论
浏览:99
浏览:99

553 篇文章

你可能感兴趣的文章

相关问题