c********p
发帖数: 1969 | 1 不是说每个bucket挂一个bst吧？而是说整个的是一个bst？ |
|
r*********n
发帖数: 4553 | 2 你每个bucket可以再挂一个小的hashtable，对于所有hash collision的元素重新hash
一遍（用不同的hash function）, 然后2nd-level hashtable的每个bucket用数组，不
要用linked list，因为数组能存到cpu cache里面去，比linked list快很多。所以最
后的结果还是O(1)。
另外用bst，每个node有left, right children pointer，其实根本不省内存
memory average search hit
Balanced BST 64N 1.39lgN
Hashtable 32N~128N <2.5
cited from pp. 487 <> by Sedgewick |
|
y*****3
发帖数: 451 | 3 Convert Sorted List to BST那道题的O(N)解法看了一整天了还没看懂，用java写的话
，为什么head = head.next 那个赋值不行啊？？为什么必须要手动修改head的值啊？
还有，如果不考虑时间复杂度的话，就单纯从技术上讲，这种bottom to top的方法
build bst应该完全可以应用在sorted array那道题上吧？可为什么我sorted array那
道题这样build tree就不成呢？？看来还是没搞明白head=head.next那句话到底是怎么
回事。请哪位大牛给讲解一下吧！实在是想破了头了，多谢了！！ |
|
t******d
发帖数: 1383 | 4 optimal bst ?那个词汇频率来建造bst的那个题目么 |
|
s********l
发帖数: 998 | 5 最大bst是说个数最多吗？
我觉得不用extra space把~
从底向上 返回每个node下 最大bst的个数 要是
有新的最大值就更新max
这样应该可以把~ |
|
A*******e
发帖数: 2419 | 6 给的BST节点没有父指针。然后有下面的要求：
Note: next() and hasNext() should run in average O(1) time and uses O(h)
memory, where h is the height of the tree.
试着写了一个版本，直接周游BST，把结果存在数组里，然后hasNext()和next()都是O(
1)和O(1)，居然也过了。感觉在作弊。 |
|
A*******e
发帖数: 2419 | 7 这里的BST没有父指针，怎么返回下一个节点？
另外BST的节点当然不会是无数个。 |
|
发帖数: 1 | 8 有一个bst，当中两个node被交换了，现在要 恢复BST
大家什么想法 |
|
m*********a
发帖数: 3299 | 9 程序是对的，通不过是因为前面写了一个BST mirror程序，低级错误啊。
想了一天，写了3个版本，最后才想到了这个mirror程序。
下面的三个都是对的
int isBST(binaryTree *node){
return (isBSTUtil2(node,INT_MIN,INT_MAX));
}
int isBSTUtil1(binaryTree *node,int min,int max){
if (node==NULL) return 1;
if (node->keykey>max) return 0;
int ans=1;
ans=ans&&isBSTUtil1(node->left,min,node->key);
ans=ans&&isBSTUtil1(node->right,node->key+1,max);
return ans;
}
int isBSTUtil2(binaryTree *node,int min,int max){
if (node==NULL) return 1... 阅读全帖 |
|
b*********n
发帖数: 173 | 10 个人理解，不一定正确：
bib - 文献库文件
bst - 文献格式文件
bbl - Latex根据bib和bst,compile生成的文献文件 |
|
b*******g
发帖数: 513 | 11 natbib里的plainnat.bst文件放在windows的winedt的那个文件下面？主要是想在里面
改个东西，好让在bibliography 里的引用里作者的last name 在前，first name 的
abbreviation 在后，例如看下面这段话：
Open the imsi.bst file. Go
downto find the FUNCTION fformat.namesg code. You will see a line similar to
"{vv~}{ll}{ f{}}{ jj}".
The letter vv is the von part (e.g., von Neumann), ll is the last name part,
ff is the first name part,
and jj is the junior part. A double letter (e.g., ll) takes full name while
a singe letter (e.g., f)
abbreviates full name. Thus the... 阅读全帖 |
|
b*******g
发帖数: 513 | 12 我后来用了miktex的texworks,在miktex中的plainnat.bst文件中照哪个英文说明那样
改了plainnat.bst文件，但还是不行。为什么？感觉应该可以的。
to
part,
while |
|
s******9
发帖数: 283 | 13 赐教一个问题，不知道版上有高人知道不：
Illumina在cluster generation protocol里，1st strand synthesis用Taq，然后
cluster generation时换成了Bst。为什么不简单点都用Bst？ |
|
b*******g
发帖数: 513 | 14 我后来用了miktex的texworks,在miktex中的plainnat.bst文件中照哪个英文说明那样
改了plainnat.bst文件，但还是不行。为什么？感觉应该可以的。
to
part, |
|
H*M
发帖数: 1268 | 15 这个不对吧,
你看这个BST:
insert order: 8 6 5 4 7 9 10 11 12
这个会stuck在右边9-10-11-12那块
你编译code就知道了. 用上面这个做test case
只有post order比较好写,in和pre的比较不好写
stack version. |
|
g*****u
发帖数: 298 | 16 合并两个BST要求O(n+m)时间，n和m为两棵树的大小。有什么好的解法么？ |
|
c****p
发帖数: 32 | 17 what's the point?
只是要O(n+m)的时间，又没限定空间，直接copy，然后建一个bst不就完了？
balanced |
|
r****o
发帖数: 1950 | 18 光凭in-order traversal result怎么construct a new bst? |
|
y*c
发帖数: 904 | 19 首先没说是balanced, 直接用递归插就行了。
如果要balanced, 就算知道DSW, 你能写出来code么？能保证对么？我被面过这道题，
用的是多于空间,traverse, merge and construct方法，是可以写出来的。窃以为面试
就足够了，当然，你可以说，如果不要多余space,就用rotation -> right deep
然后 折半rotation变成balanced bst. |
|
K******g
发帖数: 1870 | 20 construct a new BST, 不是要求nlogn 么？那就根本不对了，人家要求O(m+n) |
|
K******g
发帖数: 1870 | 21 请问排过序的list组建一个bst，怎么做呢，复杂度是多少？谢谢 |
|
D****6
发帖数: 278 | 22 1. inorder traverse tree A and B, save sorted values in two arrays. (m+n)
2. merge two arrays into a bigger sorted array. (m+n)
3. use recursive binary search algorithm on the big sorted array, to
construct the new BST. (log(m+n))
so, total running time (m+n)
对吗? |
|
L****t
发帖数: 924 | 23 ind median of a BST, with out any extra memory and with out using any
gloabal
or static variables. |
|
b******v
发帖数: 1493 | 24 哪些是hash table能做，而BST不能做的
反之呢？ |
|
K******g
发帖数: 1870 | 25 请问排过序的list组建一个bst，怎么做呢，复杂度是多少？谢谢 |
|
r****c
发帖数: 2585 | 26 haha
你应该告诉面试的人
一直放rchild, haha
degenerated bst |
|
g*******y
发帖数: 1930 | 27 consider a sub-tree in BST, in general, all the nodes in the subtree must
have
values within a range: [min, max] |
|
I**A
发帖数: 2345 | 28 这个我大致看过
int minValue(struct node* node) {
struct node* current = node;
/* loop down to find the leftmost leaf */
while (current->left != NULL) {
current = current->left;
}
return(current->data);
}
int maxValue(struct node* node) {
struct node* current = node;
/* loop down to find the leftmost leaf */
while (current->right != NULL) {
current = current->left;
}
return(current->data);
}
这俩function，肯定有一个有问题。。。
再说了，这样求max and min也不make sense，因为只要在保证left or right是BST的
情况下才能 |
|
b********e
发帖数: 693 | 29 那位大侠给一个?
再给一个linked list to balance BST的code吧
thanks |
|
y*********e
发帖数: 518 | 30 BST to Doubly Linked List:
public LinkedList convert(BTree tree) {
LinkedList list = new LinkedList();
convert(tree, list);
return list;
}
private void convert(BTree tree, LinkedList list) {
if (tree != null) {
convert(tree.getLeftChild(), list);
LinkedListNode node = new LinkedListNode(tree.getValue());
list.add(node); // append to tail
convert(tree.getRightChild(), list);
}
}
看起来很眼熟把？就是in-order的tree traverse而已。
至于LinkedList的实现。。
public cl |
|
b*****n
发帖数: 221 | 31 如果不是sorted linked list,为什么不用linked list的root当BST的root?
Left |
|
y*********e
发帖数: 518 | 32 因为题目说了，要是 Balanced 的 BST |
|
K******g
发帖数: 1870 | 33 如果面试被问到，在已知的BST里insert一个节点，请问这个怎么回答啊
好像简单点的就是，每次insert都产生一个新的leaf，也可以在中间产生一个新的node
。中间产生一个新的node一般是用在RB tree里吧？ |
|
d**e
发帖数: 6098 | 34 不是很明白……
插入一个节点，不管它是leaf还是中间节点，只要它保持是BST就行了吧
node |
|
l*****a
发帖数: 14598 | 35 Binary search tree
From Wikipedia, the free encyclopedia
In computer science, a binary search tree (BST) or ordered binary tree
is a node-based binary tree data structure which has the following
properties:
The left subtree of a node contains only nodes with keys less than the
node's key.
The right subtree of a node contains only nodes with keys greater than
the node's key.
Both the left and right subtrees must also be binary search trees. |
|
d**e
发帖数: 6098 | 36 最简单的应该是inorder，如果递增就是bst |
|
|
s*****n
发帖数: 5488 | 38 要写一个 industrial 强度的代码，这个还差一些。
第一
assert (v1 <= v2);
special cases:
data == v1,
data == v2;
&& v1 =v2; this reduces to bst search and what if there is no data == v1 (v2
)?
both algorithms will die in the final special case.
one : infinite loop
another: return with nothing ( ususally, cc will help you with a warning as
error). |
|
M7
发帖数: 219 | 39 和BST没有关系，只要是tree traversal都应该是O(N), where N is the size of the
tree. |
|
f*z
发帖数: 34 | 40 careercup上看到的，没有想到好的办法。
题目：
Convert a min heap to BST without changing its structure and
of course no extra space |
|
S******n
发帖数: 1009 | 41 min heap->linkedlist->BST
structure and |
|
f*z
发帖数: 34 | 42 我觉得意思是heap跟BST都是binary tree, 保持structure只是保持树形，里面的内容
当然移动了。 |
|
g*********s
发帖数: 1782 | 43 then how to ensure the heap operations' complexity is still O(logN)? for
linked list you can't randomly access the element.
why not assuming the heap is also a binary tree? the array format of heap
is just a compact representation of heap.
even if the input heap is represented as an array, we can still store the
newly bst to the array. but it would need O(1) space for array element
swap. i think this is OK. |
|
f*z
发帖数: 34 | 44 这个链接是二叉树的链接法，就是node有left child, right child, parent指针。
所以operation仍然是O(logN).
对于用array表示的heap和BST, 怎么样来转换呢？ |
|
v*******7
发帖数: 187 | 45
对，如果heap用binary tree来表示，那么需要有parent指针的信息，in place可以做
，我这里刚
才想了一个算法，是O(nlgn)的做法，可以做到。
我在想用array表示的heap转换成array 表示的BST要怎么做。 |
|
t****0
发帖数: 235 | 46 this is more like
heap -> sorted array -> bst |
|
S******n
发帖数: 1009 | 47 you mean you can use array to represent bst? |
|
b*******s
发帖数: 5216 | 48 heap sorting O(nlogn)
然后就可以说这是BST了
root是n/2的点
左child是 n/4 ,右child是3n/4
一路二分下去
仅仅是各层节点没有按顺序存放而已 |
|
f*******4
发帖数: 1401 | 49 如果是用array，排序后，怎么不用额外空间构建BST？ |
|
f*******4
发帖数: 1401 | 50 对 但是sort后怎么倒腾成表示bst的array？
比如
1 2 3 4 5 6 7
变成
4 2 6 1 3 5 7
？ |
|
