将数组表示为AVL树

Question

简介

你好，我正在尝试使用AVL树实现快速插入和删除的数组，也就是说，我有由键（索引）和分配给它们的值组成的AVL树。但我在插入/删除后更新索引时遇到问题。

我想实现什么

我很想实现在

insert()

中工作的函数

delete()

和

O(log(n))

，但我不知道如何更新索引，也就是说，如果我有 10 个元素并且我想在索引处插入新元素3 如何将旧索引 3..10 更新为 4..11？

我尝试了什么

我尝试以递归方式更新它们，但问题是，在递归中，您只能遍历树的一部分，而另一部分仍然过时，如果我想遍历另一部分，我可能会失去我的

O(log(n))

时间复杂度。

Answer 1

Čuchám čuchám neplechu，ProgTest je samostatná práce！