w******j
发帖数: 185 | 1 来个java的吧，带parent pointer和不带的，preorder和inorder的
import java.util.NoSuchElementException;
import java.util.Stack;
public class BST {
private Node root;
private static class Node {
int key;
Node left, right, parent;
Node(int key) {
this.key = key;
}
}
public BST(){
}
public BSTIterator inorderIterator() {
return new InorderIterator();
}
public BSTIterator preorderIterator() {
return new PreorderI... 阅读全帖 |
|
b********h
发帖数: 119 | 2 bst的inorder traversal就是一个有序的list，但从一个有序list还原到bst不是唯一
的。最简单的可以遍历这个list，把每个元素加到bst的左边（原list按降序排列）或
右边（原list按升序排列）。但这样出来的bst的高度就是list的长度，所以是最差的
bst。好点的做法可以每次取list中间的元素作为root，然后递归的建左子树和右子树
。这两个的复杂度都是O（n）。 |
|
w****x
发帖数: 2483 | 3 //Merge two BST
//O(n) solution
//1. Change BST into linked list
//2. Merge 2 linked lists
//3. Change linked list into a balanced BST
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
////////////////////change BST to linked list///////////////////////////////
void _inner_chng_link(NODE* pNode, NODE*& ph, NODE*& pt)
{
if (NULL == pNode) return;
NODE* pLft1 = pNode;
NODE* pLft2 = pNode;
_inner_chng_link(pNode->pLft... 阅读全帖 |
|
n********r
发帖数: 719 | 4 很多BST的题都是recursion解法
套路是分支recursive
根据BST的性质做某个比较
< 的情况往左子树延伸
> 的情况往右子树延伸或者相反
那"="的情况一般怎么处理？会造成麻烦吗？有没有哪位总结过？
比方说吧，一个BST里可能有一些节点存的data相等， 然后写函数求该BST任意两个节
点的first common ancestor,但是你不知道该BST建立时遇到相等的数据的规则是存左
还是存右。这是个例子，想知道有没有什么general rules. |
|
b***a
发帖数: 6422 | 5 在用TexNiCenter。一般是在bibliographystyle那里定义bst，下面bibliography定义b
ib。
但是TexNiCenter自己的目录里就有bib和bst。比如IEEEfull.bib是干啥用的？貌似和在
IEEE网站下下来的一样，难道就是用来做模板的？另外大家是不是可以自己定义这个bi
b，因为看到有的人用的bib是用什么软件生成的。
这个bib, bst, bbl到底是啥关系，有点头晕。
====
而且另外貌似IEEE和系统自带的IEEEtran.bst本身有问题，比如处理URL啥的，说明文
件里提到鼓励大家自己做.bst。不知道我理解的对不对？ |
|
j**l
发帖数: 2911 | 6 要求in place就地转换
１．从BST转为sorted doubly-linked list可以用类似中序遍历的递归方法做，结果唯
一。
２．那么反过来，从sorted doubly-linked list转换为一棵BST, 结果不唯一，该如何
做才能尽可能的保证BST是平衡的呢(minimal height)？如果是从sorted array转为最
小高度的平衡BST，有类似binary search的思想。对双向链表，有什么好的思路？
1的白板代码如下
void TreeToList(Tree* root, Tree* &head, Tree* &tail)
{
// This is a very special case
if (root == NULL)
{
head = NULL;
tail = NULL;
return;
}
Tree* temp_head;
Tree* temp_tail;
if (root->left != NULL)
{
|
|
y*********e
发帖数: 518 | 7 Doubly Linked List to Balanced BST:
取LinkedList的中间Node，那就是BST的Root。LinkedList的前半部分，就是BST的Left
Child；后半部分，就是BST的
Right Child。用递归。
public BTree convert(LinkedList list) {
if (list.size() > 0) {
// partition it into three parts: left, middle, right
Partition parts = partition(list);
LinkedList leftList = parts.getLeftSubList();
LinkedList rightList = parts.getRightSubList();
LinkedListNode middle = parts.getMiddle();
BTree root = new BTree( |
|
h*****g
发帖数: 944 | 8 同样一组数，在做什么问题是做成heap比较好search, 做什么问题时做成BST比较好
search?
把一组数做成heap和BST,的time complexity都是O(n)吗？
能不能用o(logN)来实现一个heap或者BST?
谢了
BST = binary search tree |
|
Y********f
发帖数: 410 | 9 学习了，今天花时间仔细看了一下morris traversal，同时练习了一下，测试了一个
case。
Node *getNext(Node* &bst)
{
Node *cur = bst;
while(cur)
{
if (cur->lch == NULL)
{
bst = cur->rch;
return cur;
}
Node *prev = cur->lch;
while(prev->rch && prev->rch != cur)
prev = prev->rch;
if (!prev->rch)
{
prev->rch = cur;
cur = cur->lch;
}
else
{
prev->rch = NULL;
bst ... 阅读全帖 |
|
x***i
发帖数: 72 | 10 给一列整数，比如［5 6 1 2 4 3］， 和两个整数，
求的是， 如果先把这一列整数构造成BST， 那么所给的这两个整数的距离 （就是从一
个点走到另一个点经过的边的数目）
比如，给的数是2，6， 那么久返回3
我的做法很普通，就是一个一个整数的插入，生成bst, 然后求两个点的距离（可以先
求lowest ancestor)
但是结果11个test case只通过了8， 不知道是什么test case
整数在0和2^31之间， 整数的数量最多是2^31
请大侠直接，哪里可以优化
update:
谢谢大家回复
其实我的问题是，
有没有不explicitly构造bst也能求解 的办法。 如果input是2^31个integer的话，那
么我的bst就需要2^31 * 12(一个integer加上2个pointer）的memory, 这个大概是24g
，还是最保守的估算。是不是这样用的heap 内存太大，导致大的test case 不过？ |
|
b********6
发帖数: 35437 | 11 You probably do not need to construct the BST, and need to use property of
BST to figure out the result.
You know the root value and two points value, so you can traverse the array
from left to right to find the lowest ancestor without actually construct
BST.
To find the distance from ancestor to a node, you can also use the property
of BST.
So it can be an one pass in place solution. |
|
e***r
发帖数: 68 | 12 According to :
Joining of two BSTs at Page552:
Program 12.23 Joining of two BSTs
If either BST is empty, the other is the result. Otherwise, we combine the
two BSTs by (arbitrarily) choosing the root of the first as the root, root
inserting that root into the second, then (recursively) combining the pair
of left subtrees and the pair of right subtrees.
private Node joinR(Node a, Node b)
{ if (b == null) return a;
if (a == null) return b;
insertT(b, a.item); //把a插入到b |
|
m*********a
发帖数: 3299 | 13 int isBST(binaryTree *node){
return (isBSTUtil(node,INT_MIN,INT_MAX));
}
int isBSTUtil(binaryTree *node,int min,int max){
if (node==NULL) return 1;
if (node->key>=min && node->key
isBSTUtil(node->left,min,node->key)&&
isBSTUtil(node->right,node->key+1,max))
return 1;
else return 0;
}
主程序
if (isBST(root)) printf("It is a BST tree.n");
else printf("It is NOT a BST tree.");
然后就是NOT a BST.郁闷 |
|
I**A
发帖数: 2345 | 14 逻辑我没看懂。。
这个CODE肯定是有问题的。。
我测试了一下，自己创建了一个BST
（1）修改了ROOT的VALUE让其不是BST,可是返回TRUE
（2）修改了ROOT.LEFT的VALUE让其不是BST, 还是返回TRUE |
|
l*****g
发帖数: 685 | 15 heap适用于search最大或最下k个值；BST是适用于search任意一个值
如果数组有序，构成BST的time complexity是O(n); 如果无序，是O(nlogn);
如果数组有序，那该数组本身就是个heap (ascending --> min-heap; descending -->
max-heap), 无须再改变，no time complexity; 如果数组无序，构成heap是 O(
n);
好像没有O(logn)实现heap 和 BST 的方法 |
|
a***9
发帖数: 364 | 16 BST就是存排好序的一组数，而基于比较的排序算法没有低于O(nlogn)的。
建堆只需要O(n)，所以不能指望堆是有序的。
BST时间空间开销大，通常都是存所有的数据量，在预见需要保留所有数据
信息量的时候得用BST。堆信息量小一些，但是在处理海量数据或者流时不
好存所有数据，而且也不需要保留所有数据的信息量，只需要最大最小的k
个之类的，这时候用堆比较划算。 |
|
h****e
发帖数: 928 | 17 一道常见的面试题是print binary tree level by level。
现在有一道反过来的题目，就是给定每一层的结点，构造出
BST来。例如给出以下的vector >：
5
4 8
2 7 9
3 10
要求构造出相应的BST:
5
4 8
2 7 9
3 10
我的想法是可以把输入看作是一个一维的vector，一个个结点
地插入，这样可以得到相应的BST，复杂度是O(NlogN)吧。
问题是这种做法没有利用给出的结点已经分好层的特点，每次都从
根节点开始，似乎不是最有效的。
请问还有更好的办法吗？ |
|
a***a
发帖数: 739 | 18 Time: O(n), Space: O(1)应该能作到.
with Poster-Order process, recursively call on the left/right children,
which returns:
1. The largest BST size in this branch
2. The largest BST size in this branch starting with the root
3. The value range [min, max] of the BST in (2)
Based on this information returned from left/right children, the current
root can easily figure out the things it needs to return itself. |
|
x****g
发帖数: 39 | 19 leetcode easy BST LCA problem:
的 test case 里面的 BST 有 node 是 null,
[5,3,6,2,4,null,null,1], node with value 1, node with value 4
Output:
null
Expected:
3
[5, 3, 6, 2, 4] 是如下的 BST 吧？ null 插入到哪里呢？
5
3 6
2 4 |
|
j*****k
发帖数: 1198 | 20 Eg: BST1 B1, BST2 B2.
Choose the root which has bigger value to be the new BST's root,
then insert each node of the other BST into the new BST. If B1
has m nodes, B2 has n modes, it takes O(mn). That's not good. Is
there other more efficient way? |
|
h***n
发帖数: 36 | 21 I am wondering where should I put the customized bst file so that Miktex can
find it. I've tried
localtexmf/tex/latex/xxxx/xxxx.bst
localtexmf/bibtex/xxxx/xxxx.bst
none of them works and the error message always say "cannot find style file".
I will hate to put it in the texmf hierachy since that is not the default
installation. Anyone knows how to do it? Thanks a lot! |
|
l********r
发帖数: 175 | 22 I wrote a .bst file for one journal. Comparing it with the one available
online ( which is old and could not reach new requirements now), mine is
much better. I am thinking about send my .bst file to this journal so that
if anyone in the near future needs such kind of .bst file as i did before,
they could save a lot of energy. Is that good? I am hard to imagine what the
journal is going to react. |
|
b*******g
发帖数: 513 | 23 【 以下文字转载自 TeX 讨论区 】
发信人: birspring (bir), 信区: TeX
标 题: natbib里的plainnat.bst文件放在windows的winedt的那个文件下面？
发信站: BBS 未名空间站 (Mon Oct 31 16:26:27 2011, 美东)
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 ... 阅读全帖 |
|
g*****u
发帖数: 298 | 24 呵呵谢谢大家
这是不是就是说，先把两个BST转成linked list,再merge sort，再rotate成balanced
BST呢。 |
|
r*****t
发帖数: 712 | 25 in-order traverse both bst, merger the result, construct a new bst |
|
p********7
发帖数: 549 | 26 in-order traverse both bst, merger the result, construct a new bst不是么？ |
|
s********l
发帖数: 998 | 27 这个是bst to double link list
楼主在问如何dll变成 一个balanced bst~ |
|
i*o
发帖数: 149 | 28 link list 的 node (two pointers to prev, next)， 不可以直接用作BST的node (
three pointers to left, right and parent).
link-list -> BST 一定要从新allocate memory (free memory).
怎末定义你的in place呢？ |
|
l*********b
发帖数: 1541 | 29 就是一个递归。
每次递归返回三个值：以该节点为根的子树是否是bst, 子树的最小值和子树的最大值。
找子树的max and min是和check bst同时进行的，复杂度是N。 |
|
i**9
发帖数: 351 | 30 很多人给出的答案
int isBST(struct node* node) {
if (node==NULL) return(true);
// false if the max of the left is > than us
// (bug -- an earlier version had min/max backwards here)
if (node->left!=NULL && maxValue(node->left) > node->data)
return(false);
// false if the min of the right is <= than us
if (node->right!=NULL && minValue(node->right) <= node->data)
return(false);
// false if, recursively, the left or right is not a BST
if (!isBST(node->left) || !isBST(node->right))
... 阅读全帖 |
|
g*********s
发帖数: 1782 | 31 a bt is bst iff inorder travesal returns a strictly sorted array.
notice there's trap: if the bt has duplicate elements, it can't be a bst.
but if excluding duplicates, u can use mathematical induction to prove it.
order, |
|
r******r
发帖数: 700 | 32 写的另一个 iterative 的，就没有问题。这个调试了很久，就是不 work. 每次只是插
入重复插入第一个值。这是把 insert 定义在 BST class 里面。下面另一个
recursive 的，把 insert 定义在 node 里面，也没问题。 贴出我的 node 定义。
谁再看看，上面那个的问题在哪里 （注意，那个 insert 定义在 BST class 里面）？
private static class BSTNode>{
private T value_;
BSTNode left;
BSTNode right;
public BSTNode(T value){
value_ = value;
left = null;
right = null;
}
public void insert(T... 阅读全帖 |
|
g*********s
发帖数: 1782 | 33 bst insertion recursion should be easy ah.
the challenging part is balanced bst insertion. |
|
g**e
发帖数: 6127 | 34 我的意思是对一整棵BST来说的， 不是针对某个node。我觉得对一个BST来说，它的高
度和深度是一回事
个。
node.
has |
|
c**y
发帖数: 172 | 35 define two helper functions first.
1. min_BST(root)
2. succ_BST(curr)
then traverse the BST in the following way
for (node = min_BST(root); node; node = succ_BST(node)) {
// do something for each node
}
This is how a BST is traversed. |
|
f****4
发帖数: 1359 | 36 节点里面存the number of nodes of current tree/subtree是
clrs 14.1
BST min & BST Succ
clrs 12.2
clrs(Introduction to algorithms 2nd) |
|
g**********y
发帖数: 14569 | 37 heap to BST, 我只知道个不完美的答案，把heap sort后，依次填回heap结构中，用
successor()。
BST to heap, 有人给出答案：
public void bst2heap(int a[]) {
int n = a.length;
reverseArm(a, 0, n);
for (int i = 1; i < n / 2; i += 2)
reverseArm(a, i, n);
}
private void reverseArm(int a[], int from, int n) {
int to = from;
while (to * 2 + 2 < n)
to = to * 2 + 2;
while (to > from) {
int t = a[to];
a[to] = a[from];
a[from] = t... 阅读全帖 |
|
x****1
发帖数: 118 | 38 这应该是一道大公司面试常见题吧，网上没有找到满意的答案，所以发个贴讨论一下。
题目的意思是：pre-order travesal 一个 BST，将节点值保存在一个数组中。怎样通
过这个数组重建这棵BST。我能想到的最直接的方法就是一个节点一个节点的插入，复
杂度是nlog(n)。这题有没有O(n)解法？
void makeTree(int[] arr)
{
Node root = null;
for(int i = 0; i
insertNode(root, arr[i]);
}
}
void insertNode(Node treeNode, int value)
{
if (treeNode == null)
treeNode = new Node(value);
else if (value < treeNode.value)
insertNode(treeNode.left, value);
else
insertNode(tree... 阅读全帖 |
|
G**********s
发帖数: 70 | 39 最近系统做了BT/BST的题目，做过的最难的是 largest BST (木有subtree) in BT，那
个recursion真的很tricky，说到这道题，我想问一下，bottom-up来解这道题是不是就
是DP的应用，对应的top-down就是DC，对吧？看来是时候系统做DP/DC题目了。。。 |
|
w****x
发帖数: 2483 | 40 为啥不对, 这题就是把BST->linkedlist, merge linked list, construct balance
BST from linked list合起来 |
|
l*********8
发帖数: 4642 | 41 转换成linked list后是O(N)算法
直接从一个bst逐个取出node插入到另一个bst，是O(N*logN)算法 |
|
w***o
发帖数: 109 | 42 看到很多解法都是in-order遍历两个BST，merge两个array，然后再重构BST，为什么这
么啰嗦？
不能这样直接merge吗？基本思想就是，比较root1和root2，如果root2大的话，把
root2断为两个子树，一个的根是root2的左孩子，另一个是root2及其右子树。把root2
及其右子树与root1的右子树合并，把root2的左孩子与root1继续合并：
Node mergeBST(Node root1, Node root2) {
if (root1 == null || root2 == null)
return root1 == null? root2 : root1;
if (root1.data <= root2.data)
{
Node left = root2.left;
root2.left = null;
root1.right = mergeBST(root1.right, root2);
root1 = mergeBST(roo... 阅读全帖 |
|
w****x
发帖数: 2483 | 43
把bst化为linked list然后再用merge sort的逻辑打印, 前提是bst化为linked list的
递归栈空间不算 |
|
i******e
发帖数: 273 | 44 是呀。这不是和producer-consumer model有点类似吗？ 当一个线程遍历了一个结点之
后block自己同时signal另一个线程遍历另一BST的下一个结点然后比较直到两棵树都遍
历完。
如果有parent指针可以实现getNextNode()函数（O(1)操作）， 可以分别对两棵BST分
别扫描， 就不需要线程同步的方法了。
你说用iterative方法需要O(lgN)的space。 为什么？ |
|
w***o
发帖数: 109 | 45 只给preorder不能保证唯一的BST。
如果只是构建任意一个符合条件的BST，把
int index=-1;
改成
int index = end + 1;
就好了。 |
|
e****e
发帖数: 418 | 46 在面试中, BST和wiki上的定义弱相关，和面试官头脑里的定义强相关。。。我们现在
也不知道当时的情况，就姑且认为是有一个节点可以重复的树，其他节点满足BST?
be
node' |
|
c********p
发帖数: 1969 | 47 BST 定义是left可以等于root，但right必须大于root。
解recovery bst的时候，不考虑相等么？只有大于了才算它错，可是当root和right相
等，这个时候，也是错的吧！ |
|
s******n
发帖数: 20 | 48 这是Leetcode上的一篇文章：
leetcode.com/2010/09/saving-binary-search-tree-to-file.html
里面的重建BST代码我觉得有问题：
void readBSTHelper(int min, int max, int &insertVal,
BinaryTree *&p, ifstream &fin) {
if (insertVal > min && insertVal < max) {
int val = insertVal;
p = new BinaryTree(val);
if (fin >> insertVal) {
readBSTHelper(min, val, insertVal, p->left, fin);
readBSTHelper(val, max, insertVal, p->right, fin);
}
}
}
void readBST(BinaryTree *&root, ifstream &fin) {... 阅读全帖 |
|
r*********n
发帖数: 4553 | 49 What is the point of implementing hashtable in terms of bst?
When you generate hash value, you lose all order statistics. Then you insert
the hash value into a bst. Although the hash values are ordered, but it has
nothing to do with the ordering of the original values. |
|
q********c
发帖数: 1774 | 50 插入bst要 log(n)，为什么不直接插入数组O(1)?先搞清楚hashtable vs bst,再解题，
这种答案，直接就fail了。 |
|
