Python 数据结构和算法实用指南（二）（3）https://developer.aliyun.com/article/1507562
插入节点
在二叉搜索树上实现的最重要的操作之一是在树中插入数据项。正如我们已经讨论过的，关于二叉搜索树的属性，对于树中的每个节点，左子节点应该包含小于其自身值的数据，右子节点应该包含大于其值的数据。因此，我们必须确保每当我们在树中插入一个项目时，二叉搜索树的属性都得到满足。
例如，通过在树中插入数据项5、3、7和1来创建一个二叉搜索树。考虑以下内容：
- 插入 5：我们从第一个数据项5开始。为此，我们将创建一个数据属性设置为5的节点，因为它是第一个节点。
- 插入 3：现在，我们想添加值为3的第二个节点，以便将数据值3与根节点5的现有节点值进行比较：
由于节点值3小于5，它将被放置在节点5的左子树中。我们的 BST 将如下所示：
树满足 BST 规则，即左子树中的所有节点都小于父节点。
- 插入 7：要向树中添加值为7的另一个节点，我们从值为5的根节点开始比较：
由于7大于5，值为7的节点被放置在此根节点的右侧。
- 插入 1：让我们添加另一个值为1的节点。从树的根开始，我们比较1和5：
这个比较表明1小于5，所以我们转到5的左节点，即值为3的节点：
当我们将1与3进行比较时，由于1小于3，我们向下移动到节点3的下一级并向左移动。然而，那里没有节点。因此，我们创建一个值为1的节点，并将其与节点3的左指针关联，以获得以下结构。在这里，我们有4个节点的最终二叉搜索树：
我们可以看到这个例子只包含整数或数字。因此，如果我们需要在二叉搜索树中存储字符串数据，在这种情况下字符串将按字母顺序进行比较。如果我们想在 BST 中存储自定义数据类型，我们必须确保我们的类支持排序。
给出了在 BST 中添加节点的insert方法的 Python 实现如下：
def insert(self, data): node = Node(data) if self.root_node is None: self.root_node = node else: current = self.root_node parent = None while True: parent = current if node.data < parent.data: current = current.left_child if current is None: parent.left_child = node return else: current = current.right_child if current is None: parent.right_child = node return
现在，让我们逐步理解insert函数的每条指令。我们将从函数声明开始：
def insert(self, data):
到目前为止，您已经习惯了我们将数据封装在节点中的事实。这样，我们将node类隐藏在客户端代码中，客户端只需要处理树：
node = Node(data)
首先将进行检查，以找出是否有根节点。如果没有，新节点将成为根节点（没有根节点的树是不允许的）：
if self.root_node is None: self.root_node = node else:
当我们沿着树向下走时，我们需要跟踪我们正在处理的当前节点以及其父节点。current变量总是用于此目的：
current = self.root_node parent = None while True: parent = current
在这里，我们必须进行比较。如果新节点中保存的数据小于当前节点中保存的数据，那么我们检查当前节点是否有左子节点。如果没有，这就是我们插入新节点的地方。否则，我们继续遍历：
if node.data < current.data: current = current.left_child if current is None: parent.left_child = node return
现在，我们需要处理大于或等于的情况。如果当前节点没有右子节点，那么新节点将被插入为右子节点。否则，我们向下移动并继续寻找插入点：
else: current = current.right_child if current is None: parent.right_child = node return
在 BST 中插入一个节点需要O(h)的时间，其中h是树的高度。
删除节点
BST 上的另一个重要操作是节点的删除或移除。在这个过程中，我们需要考虑三种情况。我们要删除的节点可能有以下情况：
- 没有子节点：如果没有叶节点，直接删除节点
- 一个子节点：在这种情况下，我们交换该节点的值与其子节点的值，然后删除该节点
- 两个子节点：在这种情况下，我们首先找到中序后继或前驱，与其交换值，然后删除该节点
第一种情况是最容易处理的。如果要删除的节点没有子节点，我们只需将其从其父节点中删除：
在上面的示例中，节点A没有子节点，所以我们将它从其父节点，即节点Z中删除。
另一方面，当我们要删除的节点只有一个子节点时，该节点的父节点被指向该节点的子节点。让我们看一下下面的图表，我们要删除节点6，它只有一个子节点，即节点5：
为了删除只有一个子节点的节点6，我们将节点9的左指针指向节点5。在这里，我们需要确保子节点和父节点的关系遵循二叉搜索树的属性。
当我们要删除的节点有两个子节点时，会出现更复杂的情况。考虑以下示例树，我们要删除节点9，它有两个子节点：
我们不能简单地用节点6或13替换节点9。我们需要找到节点9的下一个最大的后代。这是节点12。要到达节点12，我们移动到节点9的右节点，然后向左移动以找到最左边的节点。节点12被称为节点9的中序后继。第二步类似于查找子树中的最大节点。
我们用节点9的值替换节点9的值，并删除节点12。删除节点12后，我们得到了一个更简单的节点删除形式，这是之前讨论过的。节点 12 没有子节点，所以我们相应地应用了删除没有子节点的节点的规则。
我们的node类没有父节点的引用。因此，我们需要使用一个辅助方法来搜索并返回带有其父节点的节点。这个方法类似于搜索方法：
def get_node_with_parent(self, data): parent = None current = self.root_node if current is None: return (parent, None) while True: if current.data == data: return (parent, current) elif current.data > data: parent = current current = current.left_child else: parent = current current = current.right_child return (parent, current)
唯一的区别是在更新循环内的当前变量之前，我们用parent = current存储它的父节点。实际删除节点的方法始于这个搜索：
def remove(self, data): parent, node = self.get_node_with_parent(data) if parent is None and node is None: return False # Get children count children_count = 0 if node.left_child and node.right_child: children_count = 2 elif (node.left_child is None) and (node.right_child is None): children_count = 0 else: children_count = 1
我们将父节点和找到的节点分别传递给parent和node，使用parent, node = self.get_node_with_parent(data)。了解要删除的节点有多少个子节点是很重要的，我们在if语句中这样做。
在我们知道要删除的节点有多少个子节点之后，我们需要处理节点可以被删除的各种情况。if语句的第一部分处理了节点没有子节点的情况：
if children_count == 0: if parent: if parent.right_child is node: parent.right_child = None else: parent.left_child = None else: self.root_node = None
在要删除的节点只有一个子节点的情况下，if语句的elif部分执行以下操作：
elif children_count == 1: next_node = None if node.left_child: next_node = node.left_child else: next_node = node.right_child if parent: if parent.left_child is node: parent.left_child = next_node else: parent.right_child = next_node else: self.root_node = next_node
next_node用于跟踪单个节点，该节点是要删除的节点的子节点。然后，我们将parent.left_child或parent.right_child连接到next_node。
最后，我们处理了要删除的节点有两个子节点的情况：
... else: parent_of_leftmost_node = node leftmost_node = node.right_child while leftmost_node.left_child: parent_of_leftmost_node = leftmost_node leftmost_node = leftmost_node.left_child node.data = leftmost_node.data
在查找中序后继时，我们移动到右节点，使用leftmost_node = node.right_child。只要左节点存在，leftmost_node.left_child将计算为True，并且while循环将运行。当我们到达最左边的节点时，它要么是叶节点（意味着它将没有子节点），要么有一个右子节点。
我们使用node.data = leftmost_node.data来更新即将被删除的节点的值为中序后继的值：
if parent_of_leftmost_node.left_child == leftmost_node: parent_of_leftmost_node.left_child = leftmost_node.right_child else: parent_of_leftmost_node.right_child = leftmost_node.right_child
上述语句允许我们正确地将左子树节点的父节点与任何子节点连接起来。请注意等号右侧保持不变。这是因为中序后继只能有一个右子节点作为其唯一子节点。
remove操作的时间复杂度为O(*h*)，其中h是树的高度。
搜索树
二叉搜索树是一种树形数据结构，其中所有节点都遵循这样的属性：节点的左子树中的所有节点具有较低的键值，在其右子树中具有较大的键值。因此，搜索具有给定键值的元素非常容易。让我们考虑一个示例二叉搜索树，其中的节点为1、2、3、4、8、5和10，如下图所示：
在上述树中，如果我们想要搜索值为5的节点，则我们从根节点开始，并将其与根节点进行比较。由于节点5的值大于根节点值4，我们移动到右子树。在右子树中，我们有节点8作为根节点；我们将节点5与节点8进行比较。由于要搜索的节点的值小于节点8，我们移动到左子树。当我们移动到左子树时，我们将左子树节点5与值为5的所需节点进行比较。这是一个匹配，所以我们返回“找到项目”。
以下是二叉搜索树中searching方法的实现：
def search(self, data): current = self.root_node while True: if current is None: return None elif current.data is data: return data elif current.data > data: current = current.left_child else: current = current.right_child
在上述代码中，如果找到数据，我们将返回数据，如果未找到数据，则返回None。我们从根节点开始搜索。接下来，如果要搜索的数据项不存在于树中，则我们将返回None给客户端代码。我们也可能已经找到了数据，如果是这种情况，我们将返回数据。
如果我们要搜索的数据小于当前节点的数据，则我们向树的左侧移动。此外，在代码的else部分中，我们检查我们要查找的数据是否大于当前节点中保存的数据，这意味着我们向树的右侧移动。
最后，我们可以编写一些客户端代码来测试 BST 的工作原理。我们必须创建一棵树，并在1和10之间插入一些数字。然后，我们搜索该范围内的所有数字。存在于树中的数字将被打印出来：
tree = Tree() tree.insert(5) tree.insert(2) tree.insert(7) tree.insert(9) tree.insert(1) for i in range(1, 10): found = tree.search(i) print("{}: {}".format(i, found))
二叉搜索树的好处
二叉搜索树与数组和链表相比是更好的选择。对于大多数操作，如搜索、插入和删除，BST 都很快，而数组提供了快速的搜索，但在插入和删除操作上相对较慢。同样，链表在执行插入和删除操作时效率很高，但在执行搜索操作时速度较慢。在二叉搜索树中搜索元素的“最佳情况”运行时间复杂度为O(log n)，而“最坏情况”时间复杂度为O(n)，而在列表中搜索的“最佳情况”和“最坏情况”时间复杂度均为O(n)。
以下表格提供了数组、链表和二叉搜索树数据结构的比较：
| 属性 | 数组 | 链表 | BST |
| 数据结构 | 线性。 | 线性。 | 非线性。 |
| 易用性 | 创建和使用都很容易。搜索、插入和删除的平均情况复杂度为O(n)。 |
插入和删除很快，特别是使用双向链表。 | 元素访问、插入和删除都很快，平均情况复杂度为O(log n)。 |
| 访问复杂度 | 访问元素容易。复杂度为O(1)。 |
只能进行顺序访问，所以很慢。平均和最坏情况下的复杂度是O(n)。 |
访问很快，但当树不平衡时很慢，最坏情况下的复杂度为O(n)。 |
| 搜索复杂度 | 平均和最坏情况下的复杂度是O(n)。 |
由于顺序搜索，所以很慢。平均和最坏情况下的复杂度是O(n)。 |
搜索的最坏情况复杂度是O(n)。 |
| 插入复杂度 | 插入很慢。平均和最坏情况下的复杂度是O(n)。 |
平均和最坏情况下的复杂度是O(1)。 |
插入的最坏情况复杂度是O(n)。 |
| 删除复杂度 | 删除很慢。平均和最坏情况下的复杂度是O(n)。 |
平均和最坏情况下的复杂度是O(1)。 |
删除的最坏情况复杂度是O(n)。 |
让我们举个例子来理解何时使用二叉搜索树来存储数据是一个好选择。假设我们有以下数据节点——5，3，7，1，4，6和9。如果我们使用列表来存储这些数据，最坏的情况将需要我们搜索整个包含七个元素的列表来找到这个项目。因此，在这个数据节点中，需要七次比较来搜索项目9：
然而，如果我们使用二叉搜索树来存储这些值，如下图所示，在最坏的情况下，我们需要三次比较来搜索项目9：
然而，重要的是要注意搜索效率也取决于我们如何构建二叉搜索树。如果树没有被正确构建，它可能会很慢。例如，如果我们按照{1，3，4，5，6，7，9}的顺序将元素插入到树中，如下图所示，那么树将不会比列表更有效：
因此，选择自平衡树有助于改善搜索操作。在这里，我们应该注意，二叉搜索树在大多数情况下是更好的选择；然而，我们应该尝试平衡树。
平衡树
我们已经在前一节中看到，如果节点按顺序插入到树中，它会变得很慢，行为上更像一个列表；也就是说，每个节点恰好有一个子节点。为了提高树数据结构的性能，我们通常希望尽可能减少树的高度，通过填充树中的每一行来平衡树。这个过程称为平衡树。
有不同类型的自平衡树，如红黑树、AA 树和替罪羊树。这些树在修改树的每个操作期间平衡树，比如插入或删除。还有一些外部算法来平衡树。这些方法的好处是你不需要在每次操作中都平衡树，可以在需要时再进行平衡。
表达树
算术表达式由操作数和运算符的组合表示，其中运算符可以是一元或二元。算术表达式也可以使用二叉树表示，称为表达式树。这种树结构也可以用于解析算术和布尔表达式。在表达式树中，所有叶节点包含操作数，非叶节点包含运算符。我们还应该注意，表达式树的子树（右子树或左子树）在一元运算符的情况下将为空。
例如，3 + 4的表达式树如下所示：
对于稍微复杂的表达式(4 + 5) * (5-3)，我们将得到以下结果：
算术表达式可以用三种符号表示（即中缀、后缀和前缀），如前一节中关于树遍历的讨论所述。因此，对于给定的算术表达式，评估表达式树变得容易。逆波兰符号提供更快的计算。我们将在以下小节中向您展示如何构建给定后缀符号的表达式树。
解析逆波兰表达式
现在，我们将为后缀表示法中的表达式构建树。然后，我们将计算结果。我们将使用一个简单的树实现。为了保持简单，因为我们将通过合并较小的树来增加树，我们只需要一个树节点实现：
class TreeNode: def __init__(self, data=None): self.data = data self.right = None self.left = None
为了构建树，我们将使用堆栈列出项目。让我们创建一个算术表达式并设置我们的堆栈：
expr = "4 5 + 5 3 - *".split() stack = Stack()
由于 Python 是一种试图具有合理默认值的语言，其split()方法默认在空格上拆分。（如果您考虑一下，这很可能是您所期望的。）结果将是expr是一个包含值4、5、+、5、3、-和*的列表。
expr列表的每个元素将是运算符或操作数。如果我们得到一个操作数，那么我们将其嵌入树节点并将其推送到堆栈上。另一方面，如果我们得到一个运算符，那么我们将运算符嵌入树节点，并将其两个操作数弹出到节点的左右子节点中。在这里，我们必须确保第一个弹出进入右子节点；否则，我们将在减法和除法中出现问题。
以下是构建树的代码：
for term in expr: if term in "+-*/": node = TreeNode(term) node.right = stack.pop() node.left = stack.pop() else: node = TreeNode(int(term)) stack.push(node)
请注意，在操作数的情况下，我们执行了从string到int的转换。如果您希望支持浮点操作数，可以使用float()。
在此操作结束时，我们应该在堆栈中有一个单一元素，并且该元素包含完整的树。如果我们想要评估表达式，我们将构建以下小函数：
def calc(node): if node.data is "+": return calc(node.left) + calc(node.right) elif node.data is "-": return calc(node.left) - calc(node.right) elif node.data is "*": return calc(node.left) * calc(node.right) elif node.data is "/": return calc(node.left) / calc(node.right) else: return node.data
在上述代码中，我们将一个节点传递给函数。如果节点包含操作数，那么我们只需返回该值。如果我们得到一个运算符，那么我们将在节点的两个子节点上执行运算符表示的操作。然而，由于一个或多个子节点也可能包含运算符或操作数，我们在两个子节点上递归调用calc()函数（要记住每个节点的所有子节点也都是节点）。
现在，我们只需要从堆栈中弹出根节点并将其传递给calc()函数。然后，我们应该得到计算的结果：
root = stack.pop() result = calc(root) print(result)
运行此程序应该产生结果18，这是(4 + 5) * (5 - 3)的结果。
堆
堆数据结构是树的一种特殊形式，其中节点以特定方式排序。堆分为max堆和min堆。
在max堆中，每个父节点的值必须始终大于或等于其子节点。由此可知，根节点必须是树中最大的值。考虑以下最大堆的图表，其中所有节点的值都大于其子节点的值：
在min堆中，每个父节点必须小于或等于其两个子节点。因此，根节点包含最小值。考虑以下最小堆的图表，其中所有节点的值都小于其子节点的值：
堆用于许多不同的事情。首先，它们用于实现优先级队列。还有一种非常高效的排序算法，称为堆排序，它使用堆。我们将在后续章节中深入研究这些内容。
三元搜索树
三元树是一种数据结构，树的每个节点最多可以包含3个子节点。与二叉搜索树相比，它不同之处在于二叉树中的节点最多可以有2个子节点，而三元树中的节点最多可以有3个子节点。三元树数据结构也被认为是字典树数据结构的特殊情况。在字典树数据结构中，当我们使用字典树数据结构存储字符串时，每个节点包含 26 个指向其子节点的指针，而在三元搜索树数据结构中，我们有 3 个指向其子节点的指针。
三元搜索树可以表示如下：
- 每个节点都存储一个字符
- 它具有指向存储与当前节点相等值的节点的等指针
- 它具有指向存储小于当前节点值的节点的左指针
- 它具有指向存储大于当前节点值的节点的右指针
- 每个节点都有一个标志变量，用于跟踪该节点是否是字符串的结尾
为了更好地理解三元搜索树数据结构，我们将通过一个示例来演示，其中我们将字符串PUT，CAT，SIT，SING和PUSH插入到一个空的三元树中，如下图所示：
将值插入三元搜索树与在二叉搜索树中进行的方式非常相似。在三元搜索树中，我们遵循以下步骤将字符串插入三元搜索树：
- 由于树最初为空，我们首先创建根节点，其中包含第一个字符P，然后我们为字符U创建另一个节点，最后是字符T。
- 接下来，我们希望添加单词CAT。首先，我们将第一个字符C与根节点字符P进行比较。由于不匹配，并且它小于根节点，我们在根节点的左侧为字符C创建一个新节点。此外，我们创建了字符A和T的节点。
- 接下来，我们添加一个新单词SIT。首先，我们将第一个字符S与根节点字符P进行比较。由于不匹配，并且字符S大于字符P，我们在右侧为字符S创建一个新节点。此外，我们创建了字符I和T的节点。
- 接下来，我们将单词SING插入到三叉搜索树中。我们首先将第一个字符S与根节点进行比较。由于不匹配，并且字符S大于根节点P，我们查看右侧的下一个字符，即S。这里，字符匹配，因此我们比较下一个字符I；这也匹配。接下来，我们将字符N与树中的字符T进行比较。这里，字符不匹配，因此我们移动到节点T的左侧。在这里，我们为字符N创建一个新节点。此外，我们为字符G创建另一个新节点。
- 然后，在三叉搜索树中添加一个新节点PUSH。首先，我们比较单词的第一个字符，即P，与根节点。由于匹配，我们查看三叉树中的下一个字符。这里，字符U也与单词的下一个字符匹配。因此，我们查看单词的下一个字符，即S。它与树中的下一个字符T不匹配。因此，我们在节点T的左侧为字符S创建一个新节点，因为字符S小于T。接下来，我们为下一个字符H创建另一个节点。
请注意，三叉树中的每个节点都通过使用标志变量来跟踪哪个节点是叶节点或非叶节点。
三叉搜索树非常适用于字符串搜索相关的应用，比如当我们希望搜索所有以特定前缀开头的字符串，或者当我们希望搜索以特定数字开头的电话号码，拼写检查等等。
总结
在本章中，我们研究了树数据结构及其用途。特别是我们研究了二叉树，这是树的一个子类型，其中每个节点最多有两个子节点。我们还看了二叉树如何作为可搜索的数据结构与 BST 一起使用。广度优先和深度优先搜索遍历模式也通过使用队列递归在 Python 中实现。
我们还看了二叉树如何用来表示算术或布尔表达式。然后，我们构建了一个表达式树来表示算术表达式。之后，我们向您展示了如何使用栈来解析以逆波兰表示法编写的表达式，构建表达式树，并最终遍历它以获得算术表达式的结果。
最后，我们提到了堆，这是树结构的一种特殊形式。我们在本章至少尝试奠定了堆的理论基础，以便在接下来的章节中为不同的目的实现堆。
在下一章中，我们将讨论哈希表和符号表的细节。
