avl-tree_编程技术问答社区_程序员问答知识库

以下是关于 avl-tree 的编程技术问答

所以情况是: 我有数百万我试图解析并放入一个分类结构的字符串，可以说我有5,000,000个字符串. 我正在尝试编写一个快速程序，该程序可以将所有这些字符串从未分类的向量放入有序的数据结构中，该数据结构也可以快速搜索结构，因此AVL树的理由(最终我计划使用哈希表A-Z的查找速度更快，但以后出现).我首先将所有字符串都放入矢量，但它们都混乱，未分类和不同的长度. 我不希望我的树中有任何重复的字符串，因此，如果程序找到字符串" Hello"和" Hello"，它将只有一个AVL条目，并且会为该字符串出现的频率增加一个整数支架. 所以我的问题是:首先对向量进行排序会更快(使用诸如多线程QuickSort之类的快速或其他内容)，然后将其输入AVL树，然后将所有单词与其他单词与其他单词进行排序之后同样的单词，或者只能将所有数据从未分类向量放入AVL树中，并持续检查AVL树是否已经存在一个单词，然后将其递增. 以下是两种情况: CASE A: > Get input/par

0 2023-05-24 编程技术问答社区 c++ performance sorting vector avl-tree

在AVL树上的二进制搜索树

据我所知， avl avl 树木和 binary搜索树平均情况相同，在最坏情况下，AVL击败BST.这给了我一个暗示，即AVL始终比BST优越，以各种可能的方式与它们互动，也许在平衡实施方面增加了一些复杂性. 是否有任何人首先使用BST代替AVL的原因? 解决方案首先，获得最佳性能是不是编程的最终目标.因此，即使选项B总是比A更快，并且消耗的内存少于A，也不意味着它总是更好的选择，即使它更复杂.更复杂的代码需要更长的时间来写作，很难理解，并且更有可能包含错误.因此，如果更简单但效率较低的选项A对您来说足够好，则意味着它是更好的选择. 现在，如果您想将AVL树与简单的二进制搜索树(BST)进行比较而不平衡，那么AVL将消耗更多的内存(每个节点都必须记住其平衡因子)，并且每个操作都可以较慢(因为您需要保持平衡因子，有时会执行旋转). 正如您所说，BST没有平衡的情况很差(线性)最差的情况.但是，如果您知道这种最坏的情况不会发生在您身上，或者如果在极少数情况下操作很

0 2023-05-23 编程技术问答社区 performance data-structures tree binary-search-tree avl-tree

从AVL树上获取中位数？

如果您有一棵AVL树，那么从中获得中位数的最佳方法是什么?中位数将定义为具有索引CEIL(N/2)(索引以1)的元素定义. 所以如果列表为 1 3 5 7 8 中位数为5.如果列表为 1 3 5 7 8 10 中值是5. 如果您可以增强树，我认为最好让每个节点知道子树的大小(节点数)(即1 +左.Size + size + right.size).使用此方法，我可以想到的最好的方法使中位数搜索O(lg n)时间，因为您可以通过比较索引来穿越. 有更好的方法吗? 解决方案如果需要优化中位数查询，则将AVL树增强以存储子树大小通常是最佳方法.它需要时间o(log n)，这很快. 如果您要多次计算中位数，则可能会使用增强树并缓存中位数，以便您可以在时间上读取它(1).每次进行插入或删除时，您都可能需要在时间O(log n)中重新计算中位数，这会减慢一些速度，但不会影响渐近成本. 另一个选项是通过树中的节点进行双关联列表，以便您可以在

6 2023-05-23 编程技术问答社区 performance algorithm data-structures median avl-tree

C-比较来自不同分配的指针？

我已经在C中实现了一个AVL树.直到后来我才读到指针比较仅在同一数组中的对象之间有效.在实施中，我进行了某些平等测试.例如，为了测试节点是否是父母的正确孩子，我可能会测试node==node->parent->right.但是，根据需要分配节点，而不是在连续的块中分配.这个行为定义了吗?如果不是，您将如何编写此代码? 解决方案对于平等和不平等，在标准中(ISO/IEC 9899:2011)§6.5.9平等操作员¶6说: 两个指针比较时，并且仅当两者都是无效的指针时，两个指针都是对对象的指针(包括对象的指针和一个函数)或功能，两者都是对一个超过最后一个元素的指针相同的数组对象，或一个是一个指向一个数组对象末端的指针，而另一个是指向不同数组对象的开始的指针，该指针恰好在地址空间中立即遵循第一个数组对象. 将指针与平等或不平等无关的对象进行比较时没有不确定的行为. 相比之下，§6.5.8关系运营商¶5说: 比较两个指针时，结果取决于指向对象的地址空间中的相对位

10 2023-04-19 编程技术问答社区 c pointers dynamic-memory-allocation avl-tree

工作面试问题使用树，要保存什么数据？

我正在解决以下工作面试问题，并解决了大部分问题，但在最后要求失败. Q:构建支持以下功能的数据结构: Init - 初始化的空ds. o(1)时间复杂性. SetPositiveInDay(d,x) - 添加到DS中，在d x新人中被COVID -19感染. o(log n)时间复杂性. WorseBefore(d) - 从插入DS的日子和 Last 的，它比d更新的人. o(log n)时间复杂性. 例如: Init() SetPositiveInDay(1,10) SetPositiveInDay(2,20) SetPositiveInDay(3,15) SetPositiveInDay(5,17) SetPositiveInDay(23,180) SetPositiveInDay(8,13) SetPositiveInDay(13,18) WorstBefore(13) // Returns day #2 SetPositiveInDay(10

18 2023-04-13 编程技术问答社区 algorithm data-structures tree time-complexity avl-tree

向空的AVL树添加N个元素的运行时间

"高度为avl树的最小节点h"的公式是递归的: n(0)= 1，n(1)= 2 n(h)= 1+n(h-1)+n(h-2) 另一方面，我在Internet中发现了这一点，以解释将n元素添加到空的AVL树的复杂性: Well, imagine the tree being built. One by one, the elements go through the tree nodes, and chose their abode by taking either a left or a right. The tree balances itself every time the heights are too skewed. Of course, the cost of balancing the tree is an O(1) operation, so I do not consider that in the complexity analysi

12 2023-04-13 编程技术问答社区 data-structures time-complexity avl-tree

维基百科的不平衡AVL树的例子是如何做到不平衡的？

上图来自" wikipedia在avl树上的条目" . 这棵树如何无法平衡? 这是文章的报价: 节点的平衡因子是其右子树的高度减去其左子树的高度和平衡因子1、0或-1的节点被认为是平衡的.具有任何其他平衡因素的节点被认为是不平衡的，需要重新平衡树.平衡因子要么直接存储在每个节点上，要么是从子树高度计算的. 左和右子树的高度为4.左树的右子树的高度为3，仍然小于1. 解决方案要保持平衡，树上的每个节点都必须，没有孩子，(成为"叶子"节点) 有两个孩子. 或，如果只有一个孩子，那个孩子必须是叶子. 在您发布的图表中，9、54和76违反了最后的规则. 正确平衡，树看起来像: Root: 23 (23) -> 14 & 67 (14) -> 12 & 17 (12) -> 9 (17) -> 19 (67) -> 50 & 72 (50) -> 54 (72) -> 76 更新:(将近9年后，我为图形创建了一个很酷的在线图表，请例如，

18 2023-04-13 编程技术问答社区 data-structures binary-tree avl-tree

查找AVL树的中位数

我已经搜索了一下，找到了一个相关文章:从avl树中获得中位数? 但是我对响应不太满意. 我对解决此问题的想法: 如果平衡因子为0，请返回根否则请继续移除根，直到树完全平衡，并计算出您刚刚去除的根的中值假设AVL树将保持平衡(根据定义?) 我已经看到一些答案，暗示了及上的遍历并找到中位数，但我认为我需要更多的空间和时间. 有人可以确认或纠正我的想法吗?谢谢！解决方案您建议的方法中有两个问题: 您在此过程中销毁树(或占用"备份"副本的两倍) 在最坏的情况下，您需要大量的根部清除才能获得一棵完全平衡的树(我认为在最糟糕的情况下，它将接近2^(n-1)-1 emovals)...而且您仍然需要从中计算中位数. 您链接的问题中的答案是正确且最佳的.解决此问题的常用方法是构造订购统计范围每个节点的左和右子树.请注意，如果发生AVL树的旋转，您必须相应补偿数字. 请参阅IVLAD的答案在这里.由于AVL树可以保证O(log n) 搜索操作和

18 2023-03-24 编程技术问答社区 median avl-tree

在AVL树中找到中位数

我有一个AVL树，我想在其中返回o(1)中的中间元素. 我知道每次插入新元素而不更改插入时间时(通过节省子树的大小并进行遍历，直到找到N/2'th尺寸subtree). 但是我想知道我是否可以使用一个事实来做到这一点.在每个插入中，中值都在"向右移动"，并且中间的每个删除都会"向左移动". 更通用的方式:如何使用前身和后继者在AVL树中跟踪I'th元素? 解决方案给定一个AVL(自平衡的二进制搜索树)，找到中位数.请记住，即使树是平衡的，也不能仅仅采用根部元素，因为即使树平衡，您也不知道中位数是左或右儿子的根元素.迭代算法用于找到AVL的中位数.该算法基于每个AVL树的属性，您可以使用术语遍布术语，以获取包含该树元素的排序集合.使用此属性，我们可以得到分类的节点集合，然后找到中位数.该算法的复杂性顺序是o(n)的时间和空间术语，其中n是树中的节点的数量. public class AvlTreeMedian { BinaryTreeInOrder bina

24 2023-03-24 编程技术问答社区 median avl-tree

平衡二叉树(AVL)

好吧，这是理论领域的另一个CS家伙. 在90年代，我在实施BST方面做得很好.我唯一无法抓住我的头是平衡二进制树(AVL)的算法的复杂性. 你们能帮我吗? 解决方案替罪羊树可能具有最简单的平衡确定算法.如果任何插入导致新节点太深，它可以通过查看重量平衡而不是高度平衡来发现一个可以重新平衡的节点.是否在删除上重新平衡的规则也很简单.它不会在节点中存储任何奥术信息.证明它是正确的很难，但是您不需要理解算法... 但是，与AVL不同，它始终不是高度平衡.就像红黑一样，其不平衡是有限的，但是与红黑不同，它可以用参数调谐，因此，对于大多数实际目的，它看起来像您需要的一样平衡.我怀疑，如果您的调整太紧，但是对于最差的插入而言，它的结局比AVL糟糕或更糟糕. 回答问题编辑我将为理解AVL树提供个人道路. 首先，您必须了解树的旋转是什么，因此请忽略您听过的AVL算法并理解这一点的所有其他内容.直接进入您的头部，这是正确的旋转，是左旋转，每个人对树的作用，否

12 2023-03-23 编程技术问答社区 algorithm computer-science binary-tree theory avl-tree

用AVL树实现Bentley-Ottmann算法

我在Java中实现此方法时遇到了问题.我专门在计算几何形状中使用AVL BST树在计算几何版中实现算法FINDINTERSECTIONS.书中的描述如下所示: 我遇到的问题是在HANDLEEVENTPOINT中实现步骤5.当事件点是一个交叉点时，状态不再在那里完全订购，因为对于相交线，它们在交叉点越过，需要在状态中交换.由于我正在使用的BST是AVLTREE，因此删除方法失败了，因为重新平衡方法需要正确排序元素(即，删除方法假设将树正确订购，并对订单执行旋转以维护日志(n)高度).另外，我正在使用的状态将数据存储在节点中，而不是图中所示的叶子.如果我正确理解，这本书说可以使用两种树. 解决方案首先使用平衡二进制搜索树的叶子版本，无论是红黑还是AVL.我使用了红色. 获取Peter Brass关于高级数据结构的书，因为您将在几乎所有标准算法/数据结构书籍中找到这些叶树上的任何东西.我相信它们也被称为外源树. http://www-cs.engr.ccny.cun

42 2023-03-23 编程技术问答社区 java algorithm computational-geometry avl-tree

完美平衡的二进制搜索树

我有一个关于Balanced BST的理论问题. 我想从常规unbalanced BST构建具有2^k - 1节点的Perfect Balanced Tree.我能想到的最简单的解决方案是使用分类的Array/Linked list并递归将数组分为子阵列，然后与之构建Perfect Balanced BST. 但是，在一个极大的树大小的情况下，我需要以相同大小创建一个Array/List，因此此方法会消耗大量内存. 另一个选择是使用AVL旋转功能，通过元素插入元素，并根据树的平衡因子平衡树 - 左和右子树的三个高度. 我的问题是，我对自己的假设是正确的吗?还有其他方法可以从不平衡的BST? 中创建完美的BST 解决方案我还没有发现需要一个完美平衡的搜索树的情况.如果您的案子确实需要它，我想听听.通常，拥有几乎平衡的树是更好，更快的. 如果您有一个大型搜索树，则扔掉所有现有结构通常不是好主意.使用旋转功能是在保留大多数现有结构的同时获得更平衡树的好方法

14 2023-03-05 编程技术问答社区 c algorithm linked-list binary-search-tree avl-tree

实现AVL树

我正在尝试按照在这里.我一直在遇到一些问题.目前，我在插入的"正确情况"中遇到此错误.特别是在此行: // Right Right Case if (balance root->right->data) leftRotate(root); 我遇到的错误是: Exception thrown: read access violation. root._Mypair._Myval2->right._Mypair._Myval2 was nullptr. 如果有人可以帮助我解决这个问题，我真的很感激. 这是我的代码: #include #include #include #include #include #include struct Node { int data; int he

18 2023-03-02 编程技术问答社区 c++ c++11 avl-tree

计算avl树中一个节点的平衡系数

我想在不使用任何递归过程的情况下计算AVL树节点的平衡因子.我怎样才能做到这一点?请告诉我方法或提供C ++代码段. 解决方案您可以将平衡因子作为每个节点保存的信息的一部分保存. 具体来说，您可以保存左右子树的高度，并在插入/删除路径上的每个插入/删除中更新值. 示例: class Node { public: // stuff... int GetBF() { return lHeight - rHeight; } private: int data; Node* right; Node* left; Node* parent; // optional... int rHeight; // Height of the right subtree int lHeight; // Height of the left subtree }; 其他解决方案没有递归，它可能有些复杂，但是您可

62 2023-03-02 编程技术问答社区 c++ algorithm data-structures avl-tree

红黑树和AVL树之间的区别

有人可以解释这两个数据结构之间的主要区别是什么?我一直在尝试在线找到一个来源的来源，以突出显示差异/相似性，但是我没有发现任何内容丰富的信息.在什么情况下，一个比对方更喜欢?哪些实际情况使一个"更好"使用的情况比另一个"更好"? 解决方案 AVL树比红黑树保持更僵化的平衡. AVL树中从根到最深的叶子的路径最多为〜1.44 lg(n+2)，而在红色的黑树中，最多是〜2 lg(n+1). 因此，AVL树中的查找通常更快，但这是以较慢的插入和删除为代价，这是由于更多的旋转操作而导致的.因此，如果您期望查找数量可以主导该树的更新数量，请使用AVL树. 其他解决方案对于小数据: 插入:RB树和Avl树具有恒定的最大旋转数量，但RB树的速度会更快，因为平均而言，RB树使用较少的旋转. 查找:AVL树更快，因为AVL树的深度较小. delete :RB树具有恒定的最大旋转数量，但AVL树可以具有o(log n)旋转时间为最坏.平均而言，RB树的旋转数量也较少

10 2023-02-26 编程技术问答社区 data-structures tree language-agnostic avl-tree red-black-tree

平衡一个AVL树（C++）。

我有最困难的时间试图弄清楚如何平衡我的班级的AVL树.我已经插入了: Node* Tree::insert(int d) { cout data) { insert(current->lchild, d); if (height(current->lchi

30 2023-02-25 编程技术问答社区 c++ algorithm data-structures binary-tree avl-tree

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

假设我有两棵AVL树，并且第一棵树的每个元素都比第二个树的任何元素小.将它们连接到一棵AVL树中的最有效方法是什么?我到处搜索，但没有发现任何有用的东西. 解决方案假设您可能会破坏输入树: 删除左树的最右元素，并使用它来构造一个新的根节点，其左孩子是左树，右孩子是右树:o(log n) 确定并设置该节点的平衡因子:O(log n).在(临时)违反不变的情况下，平衡因子可以超出范围{-1、0、1} 旋转以使平衡因子恢复到范围:o(log n)旋转:o(log n) 因此，可以在O(log n)中执行整个操作. 编辑:在第一次思考中，更容易理解以下算法中的旋转.它也很可能更快: 确定两棵树的高度:o(log n). 假设右树高(另一种情况是对称的): 从left树中删除最右边的元素(如有必要，旋转并调整其计算高度).令n成为该元素. o(log n) 在右树中，向左导航，直到您到达subtree最多比left高1个的节点.令r为那个节点. o(lo

20 2023-02-24 编程技术问答社区 c++ c algorithm data-structures avl-tree

在AVL树中搜索一个平衡系数为-2的节点

我知道如何在AVL树中搜索使用特定键的节点.但是我想知道如何在平衡因子为-2 的AVL树中搜索这是我尝试过的代码. void searchForUnrequiredBalanceFactor(avlnode *n , avlnode *r) { avlnode *ptr ; ptr = n ; if (ptr==NULL) return; else { if (ptr ->balFact == -2) { r = ptr ; return ; } else { searchForUnrequiredBalanceFactor(ptr->left,r); searchForUnrequiredBalanceFactor(ptr->right,r);

8 2023-02-04 编程技术问答社区 c data-structures avl-tree

在AVL树上的旋转，有完整的可重复的例子C

我一直在此功能上停留了2天，所以我试图弄清楚它. 下面的代码是我的尝试(感谢User3386109)在通用节点上制作一个totrotate. 我认为要接近，但问题是当我运行代码时，旋转会进行，但是当我打印值时，实际上似乎什么也没有发生. #include #include typedef struct tree mynode; struct tree{ // node struct int value; int key; char color; struct tree *left; struct tree *right; }; //allocate memory, set color, key, value and NULL sons mynode* red_node_create(int Key, int Value) { mynode*

20 2023-02-04 编程技术问答社区 c binary-search-tree 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->righ

18 2023-02-04 编程技术问答社区 c algorithm data-structures avl-tree