伪code和删除一个节点在二叉搜索树的条件 [英] Pseudo Code and conditions for deleting a Node in Binary Search Tree

问题描述

我想编写一个函数来从二叉树中删除一个节点。我还没有codeD功能着呢，我试图去思考不同的情况，我应该考虑删除节点。我猜测可能的条件是：

I'm trying to write a function to remove a node from a binary tree. I haven't coded the function yet, and I am trying to think about the different conditions I should consider for removing a node. I am guessing that the possible conditions are:

1. 该节点没有孩子

1. The node has no children

节点有一个子

节点有2个孩子

在每一种情况下，这将是该算法执行删除功能？

In each of these cases what would be the algorithm to perform a delete function?

推荐答案

这是你会发现在关于算法的任何标准的教科书，但是让我们假设你感兴趣的不平衡情况（平衡树通常执行一些再平衡操作称为旋转去除后），并使用明显的数据结构（A tree_node 结构中保存价值和两个指向其他 tree_node ）：

This is something you would find in any standard textbook about algorithms, but let's suppose you are interested in the unbalanced case (balanced trees usually performs some rebalancing operations called "rotations" after a removal) and you use the "obvious" datastructure (a tree_node structure that holds the value and two pointers to other tree_node):

1. 否儿童：由节点释放内存持有，并设置指向它 NULL 父项的子链接;
2. 一名儿童：由节点释放内存持有，并设置指出，作为其唯一的孩子的地址父项的子链接;
3. 两个孩子：这确实是复杂的情况。发现左子的最右边的节点（或右孩子的最左边的节点），取它的值，将其删除（它是盒1，所以很容易和可以递归进行）和当前节点的值设定为该节点中的一个。这是 O（tree_height）= 0（n）的，但它不是（至少在理论上）的一个问题，因为这将是neverthless所述找到的节点的复杂性。

1. No children: release the memory hold by the node and set the parent's child link that pointed to it as NULL;
2. One child: release the memory hold by the node and set the parent's child link that pointed to it as the address of its unique child;
3. Two children: this is indeed the "complicated" case. Find the rightmost node of the left child (or the leftmost node of the right child), take its value, remove it (it is "case 1", so it is easy and can be done recursively) and set the current node's value as the one of that node. This is O(tree_height) = O(n), but it is not a problem (at least in theory) because this would be neverthless the complexity of finding a node.

这篇关于伪code和删除一个节点在二叉搜索树的条件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！