C***y
发帖数: 2546 | |
p******r
发帖数: 2999 | 2 read the definition of bst
you will find out where the second largest is.
【在 C***y 的大作中提到】
: 这题logN的解法应该如何做？
|
a********e
发帖数: 80 | 3 如果有指向parent的指针，就可以很容易的找中序后继了。 |
C***y
发帖数: 2546 | 4 如果没有呢？
【在 a********e 的大作中提到】
: 如果有指向parent的指针，就可以很容易的找中序后继了。
|
a********e
发帖数: 80 | 5 先通过BST来二分查找到current_node。查找的过程中记录一系列祖先node。这个过程
的复杂度O(lgN)。
然后就可以找中序后继了，具体来讲：
1）如果有right child，就是right child的最左边node。
2）如果是parent的left child，那么就是parent。
3）否则，就沿着祖先nodes往上，直到走到一个node，它是它parent的left child. |
C***y
发帖数: 2546 | 6 改进一下
用个变量t记录向下查找的path中比输入值大的node中最小的那个
1.如果找到的node有right subtree，那么返回subtree中最左边的node
2.如果没有的话，返回t
这个方法好像可行
【在 a********e 的大作中提到】
: 先通过BST来二分查找到current_node。查找的过程中记录一系列祖先node。这个过程
: 的复杂度O(lgN)。
: 然后就可以找中序后继了，具体来讲：
: 1）如果有right child，就是right child的最左边node。
: 2）如果是parent的left child，那么就是parent。
: 3）否则，就沿着祖先nodes往上，直到走到一个node，它是它parent的left child.
|
a********e
发帖数: 80 | 7 嗯！好像是对的！
【在 C***y 的大作中提到】
: 改进一下
: 用个变量t记录向下查找的path中比输入值大的node中最小的那个
: 1.如果找到的node有right subtree，那么返回subtree中最左边的node
: 2.如果没有的话，返回t
: 这个方法好像可行
|
