标签: avl-tree

我想在不使用任何递归过程的情况下计算avl树中节点的平衡因子.我怎样才能做到这一点？请告诉我方法或提供C++代码片段.

今天我正在研究数据结构中的 AVL 树，但在理解 LR 和 RL 旋转方面陷入了困境。LL 和 RR 轮换非常直观且容易记住，但在我看来 LR 和 RL 轮换不符合常识，所以我很难记住它们。这些旋转是否应该被塞满或者有什么方法可以理解它们？我正在阅读的书（Seymoure Lipschutz 的《数据结构》）说 LR 旋转是 RR 旋转和 LL 旋转的组合。但我无法连接它。这是那本书中描绘的图片：

在第二张图片和最后一张图片之间发生了什么，如果可能，请用这张图片解释一下。我想如果我理解 LR，那么就会自动理解 RL，因为两者都是彼此的镜像。

考虑以下使用二叉搜索树对 n 个元素的列表进行排序的算法：

initialise t to be an empty binary search tree
for each element x in the list,
  add x to t
while t is not empty,
  remove and print the smallest element of t

如果使用以下方法实现树，则该算法的最坏情况时间复杂度是多少：

a) 普通的二叉搜索树？
b) AVL 树？

我的解决方案：我认为解决方案是，对于 AVL 树：O(Log N) 而对于 BST，它将是 O(N)

所以我最近发布了这个,但我仍然因为出了什么问题而感到茫然.具体来说,我似乎无法弄清楚是什么导致我的AVL树需要这么长时间来排序.我读了一个包含500,000个随机,未分类数字的文件,通过在for循环中使用向量来对树进行排序,一次为数字提供一个数字.现在,我也使用普通的BST进行了测试,因为有人提到必须一次创建一个节点,这可能就是为什么花了这么长时间,但是只用了5秒就完成了,因为只有12,164个节点被跳过了重复.我的AVL树需要花费3个小时才能对列表中的一半进行排序,因此必定会出现问题.任何人都可以弄明白它是什么？据我所知,重新平衡和插入逻辑是正确的,因为每当我运行一堆测试用例时,它们都很好.我似乎无法追查问题所在.这是我想要查看的所有人的完整代码.由于我为检测目的而包含的所有内容(如跟踪循环),Main现在有点混乱,但大部分都将在最终版本中消失.

编辑:

这个问题已得到解答.

#include <iostream>
#include<iomanip>
#include <time.h>
#include <vector>
#include <fstream>
using namespace std;

vector<int> numbers;

struct node
{
public:
    int data, height;
    node *leftChild, *rightChild;
};

node* root = NULL;

int findMin(node *p) // finds the smallest node in the tree
{
    while (p->leftChild != NULL)
        p = p->leftChild;
    return p->data;
}
int findMax(node *p) // finds the largest node in the tree
{
    while(p->rightChild != NULL)
        p = p->rightChild;
    return p->data;
}
int max(int a, int b) …