x*********w
发帖数: 533 | 1 delete node from BST.
不能直接copy value.
二爷来做一下吧... |
a********n
发帖数: 1287 | 2 void RemoveFromBST( BinaryTreeNode*& p, int key )
{
if( p )
{
if( key < p->m_Data )
{
RemoveFromBST( p->m_Left, key );
}
else if( key > p->m_Data )
{
RemoveFromBST( p->m_Right, key );
}
else
{
if( p->m_Right )
{
BinaryTreeNode* small = FindMinNode( p->m_Right );
p->m_Data = small->m_Data;
RemoveFromBST( p->m_Right, p->m_Data );
}
else if( p->m_Left )
{
BinaryTreeNode* temp = p;
p = p->m_Left;
delete temp;
temp = NULL;
}
else
{
delete p;
p = NULL;
}
}
}
}
是这样吗？ |
g*******s
发帖数: 2963 | 3 很多很基本的text book题逻辑简单，但写起来真的很难直接bug free。
这个题就是之一把。。。。还有什么heapify， non-recursive traversal 之类的 |
a********n
发帖数: 1287 | 4 是的，
否则也不要gdb了，写了就bug free.
【在 g*******s 的大作中提到】
: 很多很基本的text book题逻辑简单，但写起来真的很难直接bug free。
: 这个题就是之一把。。。。还有什么heapify， non-recursive traversal 之类的
|
x*********w
发帖数: 533 | 5
一个node有parent指针，
原型是remove_node(NODE* root, NODE* pNode2Remove)
【在 a********n 的大作中提到】
: void RemoveFromBST( BinaryTreeNode*& p, int key )
: {
: if( p )
: {
: if( key < p->m_Data )
: {
: RemoveFromBST( p->m_Left, key );
: }
: else if( key > p->m_Data )
: {
|
p*****2
发帖数: 21240 | 6
有parent没有必要要root吧？
【在 x*********w 的大作中提到】
:
: 一个node有parent指针，
: 原型是remove_node(NODE* root, NODE* pNode2Remove)
|
l*********8
发帖数: 4642 | 7 我写了个平铺直叙版的，代码稍长。
假设BST里面没有重复value
TreeNode * deleteNode(TreeNode * root, int target) {
if (!root)
return NULL;
if (target < root->val) {
root->left = deleteNode(root->left, target);
return root;
}
if (target > root->val) {
root->right = deleteNode(root->right, target);
return root;
}
TreeNode * newRoot;
if (root->left == NULL) {
newRoot = root->right;
delete root;
return newRoot;
}
if (root->right == NULL) {
newRoot = root->left;
delete root;
return newRoot;
}
newRoot = root->right;
if (newRoot->left == NULL) {
newRoot->left = root->left;
delete root;
return newRoot;
}
TreeNode * parent = newRoot;
while(newRoot->left != NULL){
parent = newRoot;
newRoot = newRoot->left;
}
parent->left = newRoot->right;
newRoot->left = root->left;
newRoot->right = root->right;
delete root;
return newRoot;
}
【在 x*********w 的大作中提到】
: delete node from BST.
: 不能直接copy value.
: 二爷来做一下吧...
|
l*********8
发帖数: 4642 | 8 哦，原型是这样啊。刚才没看到
【在 x*********w 的大作中提到】
:
: 一个node有parent指针，
: 原型是remove_node(NODE* root, NODE* pNode2Remove)
|
x*********w
发帖数: 533 | 9
不需要，你做做？
【在 p*****2 的大作中提到】
:
: 有parent没有必要要root吧？
|
p*****2
发帖数: 21240 | 10
把left和rightmerge一下，然后把结果覆盖自己就可以了。
因为有parent，所以可以很容易知道自己是parent的left还是right，set一下就可以了
。
【在 x*********w 的大作中提到】
:
: 不需要，你做做？
|
|
|
x*********w
发帖数: 533 | 11
复杂度太大了吧，有标准算法
【在 p*****2 的大作中提到】
:
: 把left和rightmerge一下，然后把结果覆盖自己就可以了。
: 因为有parent，所以可以很容易知道自己是parent的left还是right，set一下就可以了
: 。
|
x*********w
发帖数: 533 | 12 写了一个：
static public void transplant(NODE p1, NODE p2)
{
if (p1 == null || p2 == null || p1 == p2)
return;
p2.prt = p1.prt;
if (p1.prt != null)
{
if (p1 == p1.prt.lft)
p1.prt.lft = p2;
else
p1.prt.rgt = p2;
}
p2.prt = null;
}
static public NODE delete(NODE node)
{
if (null == node)
return null;
boolean bRoot = node.prt == null;
if (node.lft == null || node.rgt == null)
{
NODE tmp = node.lft == null ? node.rgt : node.lft;
transplant(node, tmp);
if (bRoot)
return tmp;
}
else
{
NODE p = node.rgt;
while (p.lft != null)
p = p.lft;
if (p.prt != node)
{
if (p.rgt != null)
p.rgt.prt = p.prt;
p.prt.lft = p.rgt;
p.rgt = node.rgt;
}
p.lft = node.lft;
node.lft.prt = p;
transplant(node, p);
if (bRoot)
return p;
}
return null;
} |
p*****2
发帖数: 21240 | 13
O(n)复杂度。算大吗？
【在 x*********w 的大作中提到】
: 写了一个：
: static public void transplant(NODE p1, NODE p2)
: {
: if (p1 == null || p2 == null || p1 == p2)
: return;
:
: p2.prt = p1.prt;
: if (p1.prt != null)
: {
: if (p1 == p1.prt.lft)
|
p*****2
发帖数: 21240 | 14
你这个不是也没有root做输入参数吗？
【在 x*********w 的大作中提到】
: 写了一个：
: static public void transplant(NODE p1, NODE p2)
: {
: if (p1 == null || p2 == null || p1 == p2)
: return;
:
: p2.prt = p1.prt;
: if (p1.prt != null)
: {
: if (p1 == p1.prt.lft)
|
s********y
发帖数: 11 | 15 Should the following code:
p->m_Data = small->m_Data;
RemoveFromBST( p->m_Right, p->m_Data );
to be:
p->m_Data = small->m_Data;
RemoveFromBST( p->m_Right, small->m_Data );
?
【在 a********n 的大作中提到】
: void RemoveFromBST( BinaryTreeNode*& p, int key )
: {
: if( p )
: {
: if( key < p->m_Data )
: {
: RemoveFromBST( p->m_Left, key );
: }
: else if( key > p->m_Data )
: {
|
p*****2
发帖数: 21240 | 16 merge=(node1, node2)->
return node2 if !node1
return node1 if !node2
node1.right=merge(node1.right,node2)
return node1
deleteNode=(root, val)->
if(root.val==val)
root=merge(root.left,root.right)
else if(val
root.left=deleteNode(root.left,val)
else
root.right=deleteNode(root.right,val)
return root |
x*********w
发帖数: 533 | 17
我靠，你这个写的也太随便了，O(n)还想当的不平衡
【在 p*****2 的大作中提到】
: merge=(node1, node2)->
: return node2 if !node1
: return node1 if !node2
: node1.right=merge(node1.right,node2)
: return node1
: deleteNode=(root, val)->
: if(root.val==val)
: root=merge(root.left,root.right)
: else if(val: root.left=deleteNode(root.left,val)
|
p*****2
发帖数: 21240 | 18
本来就是BST，不是red-black吧？
【在 x*********w 的大作中提到】
:
: 我靠，你这个写的也太随便了，O(n)还想当的不平衡
|
d**********x
发帖数: 4083 | 19 前几天不是有人恶心过了吗
【在 x*********w 的大作中提到】
: delete node from BST.
: 不能直接copy value.
: 二爷来做一下吧...
|
d**********x
发帖数: 4083 | 20 heapify很好写
这个难写因为corner case多
【在 g*******s 的大作中提到】
: 很多很基本的text book题逻辑简单，但写起来真的很难直接bug free。
: 这个题就是之一把。。。。还有什么heapify， non-recursive traversal 之类的
|
