我在面试时被问到这个问题.这是我的O(log n)解决方案.
找到节点的深度.重复搜索,但停在depth - n.
没有第二次通过,有没有办法做到这一点？
我有一个BinarySearchTree由节点组成的节点,这些节点都是dataType学生的模板类,其中student是一个具有名称和等级的私有变量的类.
目前我可以打印树,在树中查找名称和/或等级,但我在从树中删除节点时遇到问题.
我试图删除所有年级<50(因此失败)的学生.
删除节点后,需要执行以下任一操作:
我对此的理解是,如果这是树:
1
/ \
2 3
/ \ /\
4 5 6 7
如果2失败,即等级<50
你最终会得到
1
/ \
4 3
\ / \
5 6 7
4是左分支中的最高元素.
如果这是树:
1
/ \
2 3
\ / \
5 6 7
2失败了
你最终会得到
1
/ \
5 3
/ \
6 7
如果这是树:
1
/ \
2 3
/ \ / \
4 5 6 7
1失败了
你最终会得到
5
/ \
2 3
/ …我正在尝试构建一个脚本,它将动态排列照片,就像拼贴一样,与http://lightbox.com/explore#spotlight上的内容非常类似.
我当然可以编写代码,用不同的照片集来处理每个案例,但我更愿意拥有能够处理任意数量照片的算法.这里解释的算法http://www.hpl.hp.com/techreports/2008/HPL-2008-199.pdf在第4章中看起来与我需要做的非常相似.在我的情况下,垂直和水平比率总是相同的.我会定义一个边界框,每个节点可以分割多少个级别.边界框将具有相同的水平照片比例.如果算法不能适合所有图像,我会返回一个级别并将其留在那里或从可用照片池中选择另一张照片.
我的问题非常类似于这个算法在屏幕上排列图像,但我不知道如何前进.任何进一步的指导或伪代码都会非常有用.
class Node
{
public int data;
public Node left, right;
public Node(int data)
{
this.data = data;
left = null;
right = null;
}
}
class BinaryTreeImp
{
Node root;
static int count = 0;
public BinaryTreeImp()
{
root = null;
}
public Node addNode(int data)
{
Node newNode = new Node(data);
if (root == null)
{
root = newNode;
}
count++;
return newNode;
}
public void insertNode(Node root,Node newNode )
{
Node temp;
temp = root;
if (newNode.data < …Cross posted:需要对简洁数据结构算法有一个很好的概述
由于我了解简洁数据结构,因此迫切需要对该领域的最新发展进行良好的概述.
我谷歌搜索并阅读了很多文章,我可以在google结果的顶部看到我的头顶请求.我仍然怀疑我错过了一些重要的事情.
以下是我特别感兴趣的主题:
二进制树的简洁编码,具有获得父,左/右子,子树中元素数的有效操作.
这里的主要问题如下:我所知道的所有方法都假设以节点优先顺序枚举的树节点(就像在这个领域的先驱工作中Jacobson,G.J(1988).简洁的静态数据结构),它没有似乎适合我的任务.我处理深度优先布局中给出的巨大二叉树,深度优先节点索引是其他节点属性的关键,因此更改树形布局对我来说有一些成本,我想最小化.因此,有兴趣参考考虑其他BF树布局的工作.
外部存储器中的大型可变长度项目数组.数组是不可变的:我不需要添加/删除/编辑项目.唯一的要求是O(1)元素访问时间和尽可能低的开销,比直接的偏移和大小方法更好.以下是我收集的有关我的任务典型数据的一些统计信息:
典型的物品数量 - 数亿,高达数十万;
约30%的物品长度不超过1 位 ;
40%-60%的项目长度小于8位;
只有少数百分比的项目长度在32到255位之间(255位是限制)
平均项目长度~4位+/- 1位.
项目长度的任何其他分布在理论上是可能的,但所有实际上有趣的情况都具有接近上述的统计数据.
链接到任何复杂的文章,任何模糊的教程,或多或少记录的C/C++库, - 在类似的任务中对你有用的任何东西,或者你的教育猜测看起来像什么 - 所有这些都非常感谢.
更新:我忘了添加问题1:我正在处理的二叉树是不可变的.我没有改变它们的要求,我只需要以各种方式遍历它们,总是从节点移动到子节点或父节点,因此这种操作的平均成本是O(1).
此外,典型的树有毫秒的节点,不应完全存储在RAM中.
更新2如果有人感兴趣.我在https://cstheory.stackexchange.com/a/11265/9276上有几个很好的链接.
我是C编程的新手,我正在用C学习C算法.
这是我关于如何定义二叉树node数据结构的问题.
以下是用于定义Node数据结构的2个典型示例代码.
typedef struct binaryTreeNode_{
int key;
void *data;
binaryTreeNode_ *leftNode;
binaryTreeNode_ *rightNode;
} binaryTreeNode;
typedef struct binaryTreeNode_{
int key;
void *data;
binaryTreeNode_ *leftNode;
binaryTreeNode_ *rightNode;
binaryTreeNode_ *parentNode;
} binaryTreeNode;
显然,使用具有父节点指针的节点结构将使更多工作变得更加容易.像遍历节点/树,DFS/BFS与二叉树.所以我的问题是为什么有些解决方案基于没有父节点的结构？.
有历史原因吗？如果仅仅因为RAM/DISK容量的限制,我想我们可以放弃没有父节点的解决方案,不是吗？
就像链表和双向链表,我们应该使用双链表来实现Stack和Queue？
我知道你可以在给出它的顺序和前序遍历作为字符串时重建二叉树,但是只有在给定顺序遍历时才能找到后序和/或preoder遍历吗？
Node是一个非常简单的类,只有一个构造函数和一些变量:一个"名称"(实际上只是一个char)和两个名为"left"和"right"的子节点指针.
我刚刚开始编写一些需要放到最左边节点的代码,当我提出这个问题时我很高兴:
Node *current = this->root;
while (true) (current->left != nullptr) ? current = current->left : break;
看起来很简单:在无限循环中,检查当前是否有一个左子,如果是,将当前设置为该左子,如果没有,则跳出循环.这是一个很酷的小单行,不太难以理解.(我评论了它!)
好吧,我的编译器不喜欢它:
iterator.cpp:20:70: error: expected expression
while (true) (current->left != nullptr) ? current = current->left : break;
^
1 error generated.
而且,只是在while循环中抛出一些括号并将三元运算符移动到它自己的行上并没有帮助(不出所料).我不得不把它变成if/else让编译器接受它.
有人可以解释它是如何解释单线及其对象的原因吗？
给定一个BST和两个整数'a'和'b'(a <b),我们怎样才能找到节点的数量,一个<节点值<b,在O(log n)中？
我知道在LogN时间内可以很容易地找到a和b的位置,但是如何在不进行遍历的情况下计算其间的节点,即O(n)？