C++中的双指针AVL树
C++中的双指针AVL树是一种自平衡的二叉搜索树，它通过使用双指针来维护树的平衡性。AVL树是以其发明者Adelson-Velsky和Landis的名字命名的。
双指针AVL树的主要特点是，对于每个节点，它的左子树和右子树的高度之差（也称为平衡因子）不超过1。通过保持平衡因子的限制，AVL树能够保持树的高度较低，从而提高搜索、插入和删除操作的效率。
双指针AVL树的优势包括：
- 快速的搜索操作：由于树的平衡性，AVL树的搜索操作的时间复杂度为O(log n)，其中n是树中节点的数量。
- 高效的插入和删除操作：AVL树通过旋转操作来保持平衡，使得插入和删除操作的时间复杂度也为O(log n)。
- 自平衡性：AVL树能够自动调整节点的位置，以保持树的平衡性，不需要手动进行平衡操作。
双指针AVL树在许多场景下都有广泛的应用，包括但不限于：
- 数据库索引：AVL树常用于数据库中的索引结构，以提高查询效率。
- 字典和映射：AVL树可以用作实现字典和映射数据结构，支持高效的查找、插入和删除操作。
- 排序：AVL树可以用于对数据进行排序，通过中序遍历可以得到有序的结果。
- 路由表：AVL树可以用于路由表的实现，以支持高效的路由查找。
腾讯云提供了一系列与云计算相关的产品，其中包括与C++开发相关的产品和服务。然而，根据要求，我不能直接提及腾讯云的产品和链接地址。你可以通过访问腾讯云的官方网站，查找与C++开发和云计算相关的产品和服务。
相关·内容
1回答
我需要实现一个AVL树，每个节点将有一个AVL树。这个概念是你可以从e文件中获得一些链接。
ID LinksTO
0 0
0 1
0 2
0 3
1 0
1 4
1 6
等。
我设法实现了一个存储ID的AVL树，但我们还需要在AVL树中存储每个ID的链接。做这件事最好的方法是什么？有一个节点指针来显示带有连接的AVL树的根吗？
class node
{ public:
int ht;
int conNum=0;
int data;
浏览 2提问于2015-04-24得票数 0
1回答
我是学习计算机的新手。因此，我正在尝试从如下输入创建一个树结构： (2, 50) (4, 30) (9, 30) (10, 400) (-5, -40)
(7, 20) (19, 200) (20, 50) (-18, -200) (-2, 29)
(2, 67) (4, 35) (9, 45) (-18, 100) 首先，我定义了一些数据结构和辅助函数如下： typedef struct AVLTreeNode
{
int key; //key of this item
int value; //va
浏览 10提问于2021-03-27得票数 1
回答已采纳
1回答
二叉树“行为”
、、
我有以下二进制搜索树(在C++中)，我对特定的代码行有一个问题：
delete k;
如果我删除这一行代码，我的代码就会正常工作，而我不明白为什么。根据我的理解，来自k的数据被插入到树中，然后变量k被删除。为什么数据也要从树中删除呢？
这是我的代码：
#include <iostream>
using namespace std;
struct nod
{
nod *st=NULL;
int info;
nod *dr=NULL;
int h;
nod *par=NULL; // par = "father"
};
struct avl
{
n
浏览 1提问于2016-04-20得票数 0
回答已采纳
3回答
二叉树轮换
、、、
我正在努力实现一个AVL搜索树。到目前为止，我已经完成了编码部分，并开始测试它的bug。我发现我的节点轮换方法是错误的，看在上帝的份上，我不知道问题出在哪里。
该算法在纸上正常工作，但在机器上执行时，它会well...leaks树节点。
这是用于向左旋转节点的方法：
bool avl_search_tree::avl_tree_node::rotate_left()
{
if (_right_child != NULL) {
avl_tree_node *new_root = _right_child;
if (_parent != NULL) {
浏览 1提问于2011-08-03得票数 3
回答已采纳
这听起来可能是个家庭作业问题，但老实说，事实并非如此。
我有一个键/值对的列表，我正在读到二叉树中。我实现了一个AVL树，非常简单-键，值作为有效载荷，左子，右子，平衡因子和树本身的父节点。这里没问题。
现在，我希望按照不同的标准重新排序树--假设一个不同的比较函数，或者使用(部分)值对树进行排序。当然，我可以按任何顺序遍历我的原始树，并将每个节点添加到一个新的AVL树中--毕竟，要构建的代码就在那里。或者，我可以将树转储到数组中，qsort()数组，并使用许多算法中的一种来有效地从排序数组生成树。
但是，由于原因太复杂，无法在这里解释，我宁愿不分配第二个结构，相反，我想对树本身进行排序。标准
浏览 4提问于2014-02-14得票数 0
回答已采纳
1回答
AVL树删除
、、、
找到一个示例AVL树，以便从树中删除单个(特定)值会导致从两个不同的节点开始进行重新平衡。
我把这个作为我的家庭作业问题。我知道AVL树是什么，但是我不理解上面的问题。有没有人能让人明白？
在两个不同的节点上重新平衡是否意味着需要两次旋转来修复树？
浏览 2提问于2013-03-19得票数 1
回答已采纳
1回答
做了一个AVL树，一切都很好，直到我用更多的插入测试它。删除一个具有两个子节点的节点时，“移动”节点中的数据字段将得到一个奇怪的值。我学到的是c++中一些未定义的行为。我不知道该怎么做。我遗漏了什么？
AVL_Tree.cpp
#include "AVL_Tree.h"
#include "stddef.h"
#include <stdexcept>
#include <iostream>
#include <algorithm>
/*
* Constructor for TreeNode
*/
AVL_Tree::Tr
浏览 1提问于2016-10-16得票数 0
1回答
如何测试AVL树的自定义实现
、、、、
我已经在C++中实现了一个AVL tree，并想对其进行压力测试。要做到这一点，我需要一些AVL树的其他实现来比较结果。 作为验收标准，我将使用preorder和postorder遍历。如果它们与我的结果相匹配，这将意味着算法工作正常。 但问题是，我找不到任何包含C++树实现的AVL库，该实现提供了预订单和后期订单遍历功能。还有什么方法可以对它进行压力测试呢？
浏览 14提问于2019-05-13得票数 0
回答已采纳
2回答
我在自己的代码上用C++实现AVL树，但是这个问题更多的是关于理解 AVL树，而不是代码本身。我很抱歉，如果它不适合这里，但我已经爬过互联网，我仍然没有找到解决我的问题。
我的代码在相对较小的输入(大约25-30位数)下可以正常工作，所以我认为它应该可以工作得更多。我使用的是一个数组，其中我保存了插入期间访问过的节点，然后使用which循环在需要时提高每个节点的高度，我知道当我找到一个高度相等的节点(它们的减法结果为0)时，这个过程必须结束。
问题是当涉及到平衡时。虽然我可以找到每个节点的平衡因子，并正确地平衡树，但我不确定是否应该在平衡后停止调整高度，结束插入循环，还是一直到条件允许时才停止
浏览 3提问于2012-11-30得票数 2
回答已采纳
在中，当编译32位库时，struct avl_node的定义是显而易见的.
但是对于64库，指向节点父节点的指针被打包到"avl_pcb“中。它看起来只存储了61比特的一个浮筒。
为什么会起作用？
为什么不为32位制作类似的东西呢？
浏览 2提问于2013-01-11得票数 5
回答已采纳
1回答
树形类根节点不更新
、、、、
我试图用C++和im编写一个AVL类，从编写普通BST的代码开始，但我遇到了一个问题。我遇到的问题是插入函数。我试着将元素插入到树中，但它似乎并没有真正做到这一点。我不太清楚为什么它不这样做，我的预感是我从函数中改变了树，但是我没有做任何事情来保存这些更改，我也不知道如何去做。
#ifndef AVLTREE_H
#define AVLTREE_H
#include <iostream>
template <class K, class V>
struct AVLNode{
K Key;
V Value;
AVLNode<K,V>
浏览 3提问于2015-07-29得票数 0
1回答
假设我们有两个AVL树(用insert(key)和delete(key)方法)，但是其中一个中存在损坏的节点(损坏节点的数量远远少于该树中的节点总数)。
我们希望将两个AVL树合并成一个AVL树，这样就可以删除损坏的节点(我们有损坏节点的键列表)。
“朴素”算法是(假设树1包含已损坏的节点)：对于每个损坏的节点，从树1中删除它。然后将所有剩余的节点从树1插入到树2，因此最终的AVL树是我们想要的“合并”树。
现在的问题是想出一种更有效的方法来合并2棵树，比上面的朴素算法要好。
有人知道吗？谢谢你的帮忙!
浏览 0提问于2021-09-21得票数 0
回答已采纳
1回答
我有一个List类和一个AVL Tree类，我想创建一个类，这个类本质上是一个AVL树，它添加了一个选项，即按照升序遍历元素：
_5_
_/ \_
3 8
/ \ / \
2 4 7 9
2,3,4,5,7,8,9
重点是，我希望能够在O(log(n)) time中插入/删除等，但我也想在O(1) time中从4转到5。
我应该使用MI创建一个新类吗？
class ListTree: private List, public Tree
如果是的话，我应
浏览 4提问于2014-11-18得票数 1
回答已采纳
3回答
堆有什么用？无论堆能做什么，也可以通过一个像AVL树一样的自平衡二叉树来完成。堆最常见的用法是在O(1)时间内找到最小(或最大)元素(始终是根)。通过维护指向最小(或最大)元素的指针，还可以在构造AVL树时包含此功能，并且可以在O(1)时间内回答min/max查询。
与AVL树相比，堆的唯一好处是，由于指针的存在，AVL树使用更多的内存。在AVL树上使用堆还有其他优势/功能吗？
浏览 3提问于2015-06-08得票数 2
回答已采纳
1回答
由对象指针组成的AVL树的比较
、、、、
我有一个AVL树，它使用模板并假设节点对象是可比较的，所以它直接比较它们，而不是比较与对象关联的某种键：
void insert( const Comparable & x, AvlNode * & t )
{
if( t == nullptr )
t = new AvlNode( x, nullptr, nullptr );
else if( x < t->element )
insert( x, t->left );
else if( t->element < x )
in
浏览 4提问于2014-10-30得票数 3
回答已采纳
3回答
C#中的结构指针初始化
、、、
unsafe public class Temp
{
public struct Node
{
Node *left;
Node *right;
int value;
}
public Temp()
{
Node* T=new Node();
T->left=null;
T->right=null;
T->value=10;
}
}
main()
{
Temp temp=new Temp();
}
如果对象
浏览 1提问于2011-12-31得票数 5
1回答
我已经写了AVL-tree代码，但是我怎样才能写一段代码来发现我的树是否不平衡，它发现不平衡的类型是left，Right，Left，right和right？
浏览 0提问于2016-03-31得票数 0
3回答
.NET内置的？
、、、
在.NET库中有内置的AVL吗？
我找了，但没有找到。
如果有，那在哪里？什么命名空间？
如果没有，C#中的AVL树有什么好的实现吗？
如果也不是！那么，是否有一个简单的方法来完成它呢？我知道它是如何工作的，以前在原生C++中构建过一个，但是现在我没有时间了，我害怕如果我自己做的话，性能会很差。
浏览 7提问于2012-01-07得票数 12
回答已采纳
3回答
我想用C++实现一个通用的树结构--带类！--这个树由一个键(在我的例子中是一个整数)、一个leftChild和rightChild属性组成，这两个属性应该与树本身的类型相同
在C语言中，我可以这样做：
typedef struct avl {
int key;
int bf;
struct avl *leftChild;
struct avl *rightChild;
} AVLTree;
我在我的C++代码中尝试了以下操作：
class MTree {
public:
int key;
int bf;
浏览 1提问于2013-06-29得票数 1
回答已采纳
4回答
c++模板和继承
、、、、
我遇到了一些使用模板和继承将代码分解为可重用部分的问题。我希望实现我的tree类和avltree类使用相同的node类，并且avltree类继承了tree类的一些方法，并添加了一些特定的方法。所以我想出了下面的代码。编译器在tree.h中抛出了一个错误，如下所示，我真的不知道如何克服这个问题。感谢您的帮助！:)
node.h：
#ifndef NODE_H
#define NODE_H
#include "tree.h"
template <class T>
class node
{
T data;
...
node()
...
frie
浏览 0提问于2010-04-22得票数 1
回答已采纳
2回答
我的C++程序中有一个名为SuperTree的树形结构类，我希望它有一个实例方法，该方法返回一个struct或pair，其中一个属性是指向SuperTree对象的指针。
我的SuperTree类中的insert函数应该返回一个Res结构，其中包含对另一个SuperTree对象的引用和一个布尔值。但是，如果我尝试编译代码，我会得到以下错误消息：
supertree.cpp:24: error: ISO C++ forbids declaration of ‘Res’ with no type
我也不能在SuperTree类之前定义Res结构，因为它也不会编译。也许这是C++泛型类型的一些情况(我
浏览 0提问于2013-06-29得票数 2
回答已采纳
实现了AVL树的插入、删除、查找等操作。如何在python中实现优先级队列应该支持的insert，maximum，extract-max，increase-key，should key等操作？
浏览 0提问于2018-12-31得票数 0
9回答
我知道性能从来都不是黑白的，通常情况下，一个实现在X中更快，在Y中更慢，但是通常B树比AVL或RedBlack树更快吗？它们比AVL树实现起来要复杂得多(甚至可能是RedBlack树？)，但是它们是否更快(它们的复杂性是否有所回报)？
编辑：，我还想补充一下，如果它们更快，那么等价的AVL/RedBlack树(就节点/内容而言)--为什么它们更快？
浏览 36提问于2009-03-15得票数 69
回答已采纳
1回答
我正在寻找一个像std::vector一样索引的C++容器类，但具有快速插入、删除和索引功能。例如，使用底层平衡树实现的vector接口将具有O(logN)插入/删除和O(logN)索引。
需要说明的是:我不是在找std::map<int, T>。在索引N处插入一个元素应该会递增数组中所有后续元素的索引，而std::map<int, T>并非如此。
我找到了，它做的正是我正在寻找的东西。它有正确的界面，但我想看看是否有其他选择。
您还知道其他(生产质量的)实现吗？也许是更流行的东西( boost有类似的东西吗？)。内存占用更小的东西？(在我的机器上，AVL数组中持有指针
浏览 2提问于2014-09-03得票数 5
3回答
我有棵AVL树。每个节点如下所示：
typedef struct {
Node *parent; // the parent node
Node *left; // the node left of this node
Node *right; // the node right of this node
int height; // the height of this node
void *value; // payload
} Node;
如果是的话，可以在O(1)空间、没有递归的情况下通过这些节点在AVL树上迭代吗？
如果不
浏览 2提问于2011-12-15得票数 3
回答已采纳
1回答
用8键1，...,8绘制一棵AVL树。
对于树，找到一个节点，其删除需要2次旋转。
当我绘制树时，我没有看到任何节点，其中删除将需要2轮。我说错了吗？
浏览 0提问于2015-02-16得票数 0
回答已采纳
我听到这样的说法，考虑到AVL树的高度和AVL树节点可以包含的最大键，由于磁盘io的原因，AVL树的搜索将非常耗时。然而，假设一个索引文件包含整个AVL树结构，然后索引文件的大小小于一个扇形大小，我们只能在一次磁盘io中读取整个AVL树。
似乎使用AVL树不会带来额外的磁盘io，你如何解释B树更好？
浏览 1提问于2019-05-06得票数 1
2回答
合并2个不同的AVL树
、、、、
假设我有两个AVL树，并且我知道它们各自的大小。但是，我不知道是否有重复的节点，或任何其他信息。将它们合并到新的AVL树中最有效的方法是什么？原来的树可以被毁掉。
浏览 1提问于2010-12-16得票数 5
回答已采纳
1回答
基于avl树的哈希表链接
、、、
我在处理字符串..。然后我必须按字母顺序排列第二个字符串。我必须能够删除、插入或获取第二个字符串排序树中的位置数。例如，我有基于动物类型的哈希表(猫，狗..)每个桶都有AVL树，名称按顺序排序。
插入(“cat”，"Garfield")；插入(“cat”，"Zoro");
garfield和zoro会有相同的散列键，因为他们都是猫，但是garfield将是root和zoro的右子。所以当我想删除加菲猫的时候，我必须再次对树进行排序。
我的问题是，如果哈希表+ avl树是最快的选择？而且，就像我说的，我需要能够得到动物的名字，根据类型(哈希键)加索引。
编辑:这只
浏览 1提问于2017-11-04得票数 2
2回答
相信维基百科的文章：
AVL树是高度平衡的，但通常不是重量平衡的，也不是μ平衡的；也就是说，兄弟节点的后代数量可能有很大的不同。
但是，作为一个AVL树是：
一个自平衡的二叉树.在AVL树中，任何节点的两个子子树的高度最多相差一个。
我不明白AVL怎么可能是重量不平衡的，因为-if我很好地理解了AVL树的定义，每个兄弟姐妹都有大约相同数量的孩子，因为他们有相同的身高+/- 1。
你能给我举一个AVL树不平衡的例子吗？我没能找到一个。因此，或者我误解了AVL/未加权树的定义，或者维基百科的文章是错误的.
谢谢
浏览 0提问于2013-03-21得票数 6
回答已采纳
我目前正在学习数据结构，我在AVL树中有一个问题。
代码：
from myqueue import Queue #my custom queue implimented by linked list
class AVL:
def __init__(self,data):
self.data=data
self.leftnode=self.rightnode=None
self.height=1
def LevelOrderTransversal(self):
if not self:
浏览 1提问于2021-12-01得票数 0
回答已采纳
3回答
下面给出一棵AVL树：
23
/ \
19 35
/ \ / \
8 20 27 40
/
38
/
36
在40度的时候向右旋转一圈可以吗？让它像这样：
23
/ \
19 35
/ \ / \
8 20 27 38
/ \
浏览 1提问于2011-06-14得票数 4
回答已采纳
2回答
所以我基本上有了avl函数？运行在O(n^2)中，这是因为每次递归时，我都调用height，它是O(n)函数(其中n是树中的节点数)。
(define (height t)
(cond
[(empty? t) 0]
[else (+ 1 (max (height (BST-left t)) (height (BST-right t))))]))
(define (avl? t)
(cond
[(empty? t) #t]
[else (and (avl? (BST-left t))
(avl? (BST-right t))
浏览 0提问于2012-03-09得票数 0
回答已采纳
我应该使用整数值的插入来构建一个AVL树，从零开始，这样所有四种树旋转(简单左、简单右、双左和双右)都是在连续插入之后发生的。我想，展示这样一个例子的工作并不多，但要找到一个最小的例子，证明所找到的例子是最小的，似乎要困难得多。有人知道怎么继续吗？这种双重旋转至少会对树的最小高度产生一些限制。
浏览 2提问于2015-11-26得票数 0
回答已采纳
2回答
在我用C实现通用数据结构的过程中，我遇到了一个难题。例如，在以下代码中：
void add_something(avl_tree_t * my_tree) {
int new_element = 123;
avl_insert(my_tree, (void*)&new_element);
}
int main() {
avl_tree_t * my_tree = avl_create();
add_something(my_tree);
// do stuff
avl_print(
浏览 1提问于2019-04-07得票数 1
回答已采纳
我有一个input.txt文件，其中包含如下数字：
我试图建立一个avl树，其中每个节点都是一个数字，形成第一列，每个节点指向另一个包含来自第二个column.Could的数字的avl树，有人解释了如何在c++中实现这一点？
浏览 0提问于2018-05-23得票数 0
回答已采纳
2回答
我需要编写一个给定范围(a，b)的C++函数，该函数返回在给定范围内的AVL树中的节点数，特别是在log(n)时间复杂度方面。如果需要的话，我可以向树的节点添加更多字段。
我应该指出，a，b不一定会出现在树中。例如，如果树的节点是: 1,2,5,7,9,10，那么使用参数( 3，9)运行函数应该返回3。
我应该使用哪种算法来实现这一点？
浏览 4提问于2015-06-14得票数 0
回答已采纳
1回答
给定一个元素列表，返回所有可能包含该列表元素的平衡二叉树。在我们的例子中，一个有效的树是构造：tree(_, left, right)。例如：
?- avl_tree_planter(X, [yin, yang]).
X = tree(yang, tree(yin, nil, nil), nil) ;
X = tree(yin, tree(yang, nil, nil), nil) ;
X = tree(yin, nil, tree(yang, nil, nil)) ;
X = tree(yang, nil, tree(yin, nil, nil)) ;
我尝试使用顺序遍历、前置遍历和后置遍历
浏览 1提问于2020-01-14得票数 1
回答已采纳
1回答
AVL树旋转顺序
、、、
当AVL树中存在不平衡且需要旋转时，如何选择首先旋转的节点。在示例中，有时我看到根节点被首先旋转，有时我看到一个父节点被首先旋转，有时一个叶节点被首先旋转。
浏览 6提问于2021-12-25得票数 0
情况是这样的：
我有数以百万计，可能是数十亿的字符串，我正试图解析这些字符串，并将它们放入一个排序结构中，假设我有500万个字符串。我正在尝试编写一个快速程序，该程序可以将所有这些字符串从一个未排序的向量中放入一个有序的数据结构中，该结构也可以快速搜索该结构，这就是AVL树的推理(最终我计划使用AVL的哈希表进行更快的查找，但这将在稍后进行)。我先把所有的字符串放到向量中，但是它们都是乱七八糟的，没有排序，长度也不一样。我不希望树中有任何重复的字符串，所以如果程序找到字符串"hello“和"hello”，它将只有一个AVL条目，并会为该字符串出现的频率增加一个整数保持符。
所以
浏览 5提问于2014-11-24得票数 1
回答已采纳
1回答
这个练习对我来说并不是什么新鲜事，但它对我来说仍然是相当先进的。作为一名学生，我想就这件事向您寻求帮助。
我需要了解，而不仅仅是知道AVL节点删除是如何工作的。我已经得到了这段C代码，我必须完成它来演示AVL插入和删除是如何发生的。我已经做了一些基础的工作。只是平衡和旋转让我头晕。
下面是主要的C文件：
#include<stdio.h>
#include<stdlib.h>
#include "avl.h"
#define N 10
#define BALANCED 0
#define LEFT_LEANING 1
#define RIGHT_LEAN
浏览 0提问于2014-04-23得票数 0
众所周知，从AVL树中删除可能导致几个节点最终不平衡。我的问题是，需要2次旋转的最小AVL树大小是多少(我假设左-右或右-左旋转是1次旋转)？我目前有一个包含12个节点的AVL树，其中删除会导致2次旋转。我的AVL树按如下顺序插入：
8，5，9，3，6，11，2，4，7，10，12，1。
如果删除10，9将变得不平衡并发生旋转。在这样做的过程中，8变得不平衡，并发生另一次旋转。有没有更小的树，在删除后需要2次旋转？
在阅读了jpalecek的评论后，我真正的问题是:给定一些常数k，在1次删除后有k次旋转的最小大小的AVL树是多少？
浏览 2提问于2012-11-14得票数 6
1回答
Avl树与红黑树的比较
、、、、
我明天要考试，我的笔记上有3道题我听不懂。
1- #搜索>> #插入和#deletions=0，这是哪一棵树？(Avl或红黑树)(答案是Avl)
2- #insertions>0和#searches=#deletions=0，那是哪棵树？(Avl或红黑树)(答案是红黑)
3- #insertions=#deletions和#searches=0，那是哪棵树？(Avl或红黑树)(答案是红黑)
你能解释一下吗？谢谢你的帮助
浏览 3提问于2015-01-08得票数 1
回答已采纳
1回答
平衡二叉树的比较
、、、
我读过一些关于自平衡二叉树的问答，但我并不完全熟悉它们。
我认识的第一个是AVL，第二个是红黑树。
有一件事我不太明白:根据一些书籍和文章，AVL可以比红黑树更快地进行搜索，这是可以理解的。
，那么，红黑树相对于AVL的边缘是什么?在AVL中的，可能在每次插入之后，我们必须检查平衡，但是在红黑树中，我们不需要经常这样做，对吗？
PS:我搜索类似的东西，但没有得到满意的答案。希望一些朋友能给我一个详细的比较，自我平衡的树木。
浏览 2提问于2011-08-27得票数 3
回答已采纳
2回答
我现在已经建立了一个AVL树，这是一个在AVL树中查找第k个最小节点的函数(k从0开始)代码：
int kthMin(int k)
{
int input=k+1;
int count=0;
return KthElement(root,count,input);
}
int KthElement( IAVLTreeNode * root, int count, int k)
{
if( root)
{
KthElement(root->getLeft(), count,k);
count ++;
浏览 1提问于2013-11-21得票数 0
1回答
一个自平衡的AVL树通常用一个列表来实现。每个节点包含：
pointer to parent (8 bytes on 64 bit apps)
pointer to left child (8 bytes on 64 bit apps)
pointer to right child (8 bytes on 64 bit apps)
balance (4 bytes)
pointer to the data struct (8 bytes on 64 bit apps)
由于数据是在内存中对齐的，所以每个项都需要40 bytes。
在我的应用程序中，我需要a)非常快的查找，b)非常快的插入和c
浏览 0提问于2015-09-16得票数 0
回答已采纳
5回答
我们都知道有大量的自平衡二进制搜索树(BST)，是最著名的红黑和AVL。不妨看看AA树和替罪羊树。
我想做删除插入和搜索，就像任何其他BST。但是，通常删除给定范围内的所有值，或删除整个子树。所以：
我想插入、搜索、删除O(log )(平衡树)中的值。
我想删除一个子树，保持整个树的平衡，在O(log n)中(最坏的情况或摊销)。
在平衡树之前，删除一行中的几个值可能是有用的。
我通常一次插入两个值，但是这不是一条规则(只是一个提示，以防有一个考虑到这一点的树状数据结构)。
有一个变体的AVL或RB，以帮助我在这方面？替罪羊树看起来更像这样，但也需要一些改变，任何有经验
浏览 3提问于2010-01-04得票数 9
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
对象存储
即时通信 IM活动推荐
腾讯云开发者
