无法理解二进制搜索树删除
Not able to understand Binary Search Tree Delete
我试图从这个 link BinarySearchTree 中理解 BST。但是我在其他部分感到困惑
/* Functions to delete data */
public void delete(int k)
{
if (isEmpty())
System.out.println("Tree Empty");
else if (search(k) == false)
System.out.println("Sorry "+ k +" is not present");
else
{
root = delete(root, k);
System.out.println(k+ " deleted from the tree");
}
}
private BSTNode delete(BSTNode root, int k)
{
BSTNode p, p2, n;
if (root.getData() == k)
{
BSTNode lt, rt;
lt = root.getLeft();
rt = root.getRight();
if (lt == null && rt == null)
return null;
else if (lt == null)
{
p = rt;
return p;
}
else if (rt == null)
{
p = lt;
return p;
}
else
{
p2 = rt;
p = rt;
while (p.getLeft() != null)
p = p.getLeft();
p.setLeft(lt);
return p2;
}
}
if (k < root.getData())
{
n = delete(root.getLeft(), k);
root.setLeft(n);
}
else
{
n = delete(root.getRight(), k);
root.setRight(n);
}
return root;
}
我无法理解找到右子树的最左边节点然后分配给该节点的其他部分。
但是这里既没有将该节点设为 null 也没有返回正确的节点,这对我来说没有意义。我希望这是一个正确的实现。
有人可以帮助我了解这里发生的事情吗。
关键概念是您在谈论二叉搜索树。如您所知,BST 是有序结构,这意味着对于每棵树,左子树中包含的元素都小于或等于树根。
此代码中的最后一个 else 块涵盖了删除具有两个 children 的节点的情况。
代码似乎做的是:
- 找到in-order后继节点(即右子树中最左边的节点)
- 将整个原始左子树附加到此节点
- 返回原权child作为树的新根
尽管这种迭代实现对我来说似乎是正确的,但我猜想经过几次删除操作后,您最终会得到一个不平衡的树。
删除操作的 recursive 实现,虽然一开始很难理解,但通常读起来更优雅。
我试图从这个 link BinarySearchTree 中理解 BST。但是我在其他部分感到困惑
/* Functions to delete data */
public void delete(int k)
{
if (isEmpty())
System.out.println("Tree Empty");
else if (search(k) == false)
System.out.println("Sorry "+ k +" is not present");
else
{
root = delete(root, k);
System.out.println(k+ " deleted from the tree");
}
}
private BSTNode delete(BSTNode root, int k)
{
BSTNode p, p2, n;
if (root.getData() == k)
{
BSTNode lt, rt;
lt = root.getLeft();
rt = root.getRight();
if (lt == null && rt == null)
return null;
else if (lt == null)
{
p = rt;
return p;
}
else if (rt == null)
{
p = lt;
return p;
}
else
{
p2 = rt;
p = rt;
while (p.getLeft() != null)
p = p.getLeft();
p.setLeft(lt);
return p2;
}
}
if (k < root.getData())
{
n = delete(root.getLeft(), k);
root.setLeft(n);
}
else
{
n = delete(root.getRight(), k);
root.setRight(n);
}
return root;
}
我无法理解找到右子树的最左边节点然后分配给该节点的其他部分。 但是这里既没有将该节点设为 null 也没有返回正确的节点,这对我来说没有意义。我希望这是一个正确的实现。 有人可以帮助我了解这里发生的事情吗。
关键概念是您在谈论二叉搜索树。如您所知,BST 是有序结构,这意味着对于每棵树,左子树中包含的元素都小于或等于树根。
此代码中的最后一个 else 块涵盖了删除具有两个 children 的节点的情况。
代码似乎做的是:
- 找到in-order后继节点(即右子树中最左边的节点)
- 将整个原始左子树附加到此节点
- 返回原权child作为树的新根
尽管这种迭代实现对我来说似乎是正确的,但我猜想经过几次删除操作后,您最终会得到一个不平衡的树。
删除操作的 recursive 实现,虽然一开始很难理解,但通常读起来更优雅。