最近我一直在编码了一堆不同的二叉搜索树实现(AVL,扇,树堆),并很好奇,如果有一个特别"好"的方式来写一个迭代器遍历这些结构.我现在使用的解决方案是让BST中的每个节点都存储指向树中下一个和前一个元素的指针,这会将迭代减少到标准的链表迭代.但是,我对这个答案并不满意.它通过两个指针(下一个和前一个)增加每个节点的空间使用量,在某种意义上它只是作弊.
我知道的构建,通过使用堆栈跟踪前沿节点的探索以后用0-1(H)的辅助存储空间(其中,h为树的高度),二叉搜索树迭代器的方式,但我由于内存的使用,我们拒绝对此进行编码.我希望有一些方法来构建一个只使用常量空间的迭代器.
我的问题是 - 有没有办法在具有以下属性的二叉搜索树上设计迭代器？
next()和hasNext()查询在O(1)时间内运行.为了更方便,它的罚款,如果你认为迭代(即没有插入,删除或旋转)在树形结构不改变形状,但如果有,确实可以处理这样的解决方案将是真的很酷.
我们有一个整数
int x = 50;
在二进制中,它是
00110010
如何以编程方式更改第四(第4)位？
我正在编写一个模板类,在我的代码中的某一点上,我希望能够在栈上对参数化类型的对象进行值初始化.现在,我正在通过写一些这样的效果来实现这一目标:
template <typename T> void MyClass<T>::doSomething() {
T valueInitialized = T();
/* ... */
}
此代码有效,但(除非编译器是智能的)它需要不必要的创建和销毁临时T对象.我想写的是以下内容,我知道这是不正确的:
template <typename T> void MyClass<T>::doSomething() {
T valueInitialized(); // WRONG: This is a prototype!
/* ... */
}
我的问题是,是否有一种很好的方法来初始化自动对象,而不必显式构造临时对象并将其分配给自动对象.可以这样做吗？或者它是T var = T();如此好？
存在具有重复超过N/2个时间的元素的阵列(大小为N),并且阵列中的其余元素也可以重复,但是仅重复一个元素超过N/2次.找到号码.
我可以想到几种方法:
无法想到更好的解决方案,必须有.
是size_t编译代码的机器的字大小？
用g ++解析,我的编译器视图size_t为long unsigned int.在编译器被调用之前,编译器是否在内部选择某个预处理器宏的大小size_t,或者size_t实际上是stddef.h在字大小内设置的？
还是我偏离轨道？
所以我自学了AVL树,我理解它背后的基本思想,但我只是想确保我实际实现它的直觉是有效的:
我会用左旋转检查它 -
所以,以下情况很简单:
8
/ \
7 10
/
6
/
3
当我们添加3时,树重新平衡为:
8
/ \
6 10
/ \
3 7
但轮换是基于3的增加还是根据7的子树的不平衡？它甚至是基于植根于8的树的不平衡吗？
在我看来,以下示例是事情变得有点毛茸茸的地方:
9
/ \
7 10
/ \
6 8
/
3
因此,在这种情况下,当添加3时,7处的子树很好,因此子树不需要旋转.然而,9处的树是不平衡的,加上3,所以我们将旋转基于9.我们得到:
7
/ \
6 9
/ / \
3 8 10
因此,在编写我的代码时,我很快就会编写以下代码,从小子树开始,使用更大的子树来完成这个工作？
伪代码:
function balanceTree(Node n){
if (n is not null){
balanceTree(n.rightchild);
balanceTree(n.leftchild);
}
if (abs(balanceFactor(n))>1){
rotateAsNeeded(n);// rotate based on balance factor
}
}
提前致谢!
algorithm rotation avl-tree binary-search-tree data-structures
我开始在学校最后一年开始之前检查数据结构和算法,以确保我掌握一切.一个评论问题说"使用链表或动态数组实现堆栈并解释为什么你做出了最好的选择".
对我来说,使用带有尾指针的列表来实现堆栈似乎更直观,因为它可能需要经常调整大小.对于大量数据来说,列表是更好的选择,因为动态数组重新调整大小是一项昂贵的操作.此外,使用列表,您不需要分配比实际需要更多的空间,因此它更节省空间.
但是,动态数组肯定允许更快地添加数据(除非需要调整大小).但是,我不确定使用数组是否整体更快,或者只是不需要调整大小.
该书的解决方案说"存储非常大的对象,列表是一个更好的实现",但我不明白为什么.
哪种方式最好？应该使用哪些因素来确定哪种实施方式"最佳"？还有,我的逻辑是什么？
performance stack linked-list dynamic-arrays data-structures
为了纪念7月4日,我有兴趣找到一种以编程方式检测图片中的美国国旗.关于在图像中找到可口可乐罐头的问题有一个较早且流行的问题,虽然我不确定它们是否适用于旗帜,
是否有任何标准的图像处理或识别技术特别适合这项任务？
我查看了C++ 0x标准,发现要求make_heap不应超过3*N比较.
即堆积无序集合可以在O(N)中完成
/* @brief Construct a heap over a range using comparison functor.
为什么是这样？
来源没有给我任何线索(g ++ 4.4.3)
while(true)+ __parent == 0不是线索,而是对O(N)行为的猜测
template<typename _RandomAccessIterator, typename _Compare>
void
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
const _DistanceType __len = __last - __first;
_DistanceType __parent = (__len - 2) / 2;
while (true)
{
_ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
__comp);
if (__parent == 0)
return;
__parent--;
}
}
__adjust_heap看起来像一个log N方法:
while ( __secondChild < (__len - 1) …