Tag: avl tree

C语言中的AVL树

我目前正在做一个需要使用AVL树的项目，我为avl编写的插入函数似乎不起作用，它最多可用于3或4个节点; 我真的很感谢你的帮助尝试如下 Tree insert(Tree t,char name[80],int num) { if(t==NULL) { t = (Tree)malloc(sizeof(struct node)); if(t! = NULL) { strcpy(t->name,name); t->num = num; t->left = NULL; t->right = NULL; t->height = 0; } } else if(strcmp(name,t->name)left = insert(t->left,name,num); if((height(t->left)-height(t->right))==2) if(strcmp(name,t->left->name)name)>0) { t->right = insert(t->right,name,num); if((height(t->right)-height(t->left))==2) if(strcmp(name,t->right->name)>0) t = s_rotate_right(t); else t = d_rotate_right(t); } t->height = […]

完美平衡的二进制搜索树

我有关于Balanced BST的理论问题。 我想构建具有2^k – 1节点的Perfect Balanced Tree ，来自常规的unbalanced BST 。 我能想到的最简单的解决方案是使用排序的Array/Linked list并递归地将数组划分为子数组，并从中构建Perfect Balanced BST 。 但是，在树大小非常大的情况下，我需要创建一个相同大小的Array/List ，因此这种方法会占用大量内存。 另一种选择是使用AVL旋转function，逐个元素插入并根据树平衡因子平衡树和旋转 – 左和右子树的三个高度。 我的问题是，我对我的假设是对的吗？ 还有其他方法可以从不平衡的BST创建完美的BST吗？

AVL树中平衡因子的重新计算

在执行旋转以平衡AVL树之后，在插入后立即如何更改所有父节点的平衡因子（适当地，通过-1或1）？ AVL树的每个节点具有以下结构： typedef struct _avlTree { nutbolt part; int balanceFactor; struct _avlTree *left,*right; } *avlTree; 我根据维基百科上给出的定义设置了平衡因子。 我是否需要在每个节点中都有一个指向父节点的指针？

如何生成最大不平衡的AVL树

我编写了一个AVL树的C语言库作为通用分类容器 。 出于测试目的，我希望有一种方法来填充树，使其最大程度地不平衡，即，使其具有包含的节点数的最大高度。 AVL树具有很好的属性，如果从空树开始，按升序（或降序）顺序插入节点，则树始终是完全平衡的（即，对于给定数量的节点，它具有其最小高度）。 从空树T 0开始，为每个节点数n生成精确平衡的AVL树T n的一个整数键序列就是简单的 k 1 = 0 k n + 1 = k n +1，即k n = n-1 我正在寻找一个（希望很简单的）整数键序列，当插入最初空的树T 0时 ，生成最大不平衡的AVL树T 0 ，…，T n 。 我也感兴趣的是一种解决方案，其中只有最后一棵树T n最大程度地不平衡（节点数n将是算法的参数）。 满足约束的解决方案 max（k 1 ，…，k n ） – min（k 1 ，…，k n ）+1≤2n 是可取的，但不是严格要求的。 4 n而不是2 n的关键范围可能是合理的目标。 我无法在互联网上找到关于通过插入生成最大高度的AVL树的任何内容。 当然，我正在寻找的生成树的序列将包括所有所谓的Fibonacci树，它们是具有最小节点数的给定深度的AVL树。 有趣的是，英语维基百科甚至没有在AVL树的文章中提到斐波那契树（也不是斐波那契数字！），而德语维基百科有一篇非常好的文章完全致力于它们。 但对于我的问题，我仍然处于黑暗中。 C语言有点刺耳的黑客是受欢迎的。

连接/合并/连接两个AVL树

假设我有两个AVL树，并且第一个树中的每个元素都小于第二个树中的任何元素。 将它们连接成一个单独的AVL树的最有效方法是什么？ 我到处搜索，但没有找到任何有用的东西。