二叉排序树的插入和删除操作(python实现)

news/2025/2/22 21:13:52

二叉排序树的插入和删除操作都是在保持二叉排序树特性的前提下进行的。

插入操作:

在二叉排序树中插入一个新节点时,先比较新节点的值和当前节点的值的大小关系,若小于当前节点,则继续在当前节点的左子树中查找;若大于当前节点,则继续在当前节点的右子树中查找。重复该过程,直到找到一个空节点,将新节点插入到该位置上。

删除操作:

删除操作比较复杂,需要分类讨论。

若待删除节点为叶子节点,直接删除即可。
若待删除节点只有一个子节点,将其子节点替代自身即可。
若待删除节点有两个子节点,则需要寻找其右子树中的最小值节点或左子树中的最大值节点来替代自身,然后再将该最小值节点或最大值节点删除。

具体过程如下:

  • 在二叉排序树中查找待删除节点,并记录其父节点;
  • 对待删除节点进行分类讨论,若为叶子节点或只有一个子节点,则直接删除;
  • 若待删除节点有两个子节点,则找到其右子树中的最小值节点,或左子树中的最大值节点;
  • 将该最小值节点或最大值节点替代待删除节点,并将其子节点链接到其父节点上; 若待删除节点为根节点,则替换根节点。
  • 需要注意的是,在删除节点之后,为了保持二叉排序树的特性,需要对该节点的父节点及其祖先节点进行平衡调整。
python">class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.key = key

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root

def minValueNode(node):
    current = node
    while(current.left is not None):
        current = current.left
    return current

def deleteNode(root, key):
    if root is None:
        return root
    if key < root.key:
        root.left = deleteNode(root.left, key)
    elif(key > root.key):
        root.right = deleteNode(root.right, key)
    else:
        if root.left is None:
            temp = root.right
            root = None
            return temp
        elif root.right is None:
            temp = root.left
            root = None
            return temp
        temp = minValueNode(root.right)
        root.key = temp.key
        root.right = deleteNode(root.right, temp.key)
    return root


http://www.niftyadmin.cn/n/235514.html

相关文章

springboot全局异常处理学习

枚举项目错误信息 public enum CommonError {UNKOWN_ERROR("执行过程异常&#xff0c;请重试。"),PARAMS_ERROR("非法参数"),OBJECT_NULL("对象为空"),QUERY_NULL("查询结果为空"),REQUEST_NULL("请求参数为空");private St…

显存不够用?一种大模型加载时节约一半显存的方法

Loading huge PyTorch models with linear memory consumption 本文主要介绍了一种用于加载巨大模型权重时节约接近一半显存的方法 首先&#xff0c;创建一个模型: import torch from torch import nnclass BoringModel(nn.Sequential):def __init__(self):super().__init__…

如何借助无线通讯终端实现组态王与PLC之间通信?

本方案是基于Modbus RTU协议下实现的1主多从自组网无线通信形式&#xff0c;主站为组态王&#xff0c;从站为两台三菱FX5U PLC。在工厂里&#xff0c;组态王和plc所处位置距离较为分散&#xff0c;重新铺设电缆线工期长&#xff0c;成本高&#xff0c;故采用日系PLC专用无线通讯…

大力出奇迹——GPT系列论文学习(GPT,GPT2,GPT3,InstructGPT)

目录说在前面1.GPT1.1 引言1.2 训练范式1.2.1 无监督预训练1.2.2 有监督微调1.3 实验2. GPT22.1 引言2.2 模型结构2.3 训练范式2.4 实验3.GPT33.1引言3.2 模型结构3.3 训练范式3.4 实验3.4.1数据集3.5 局限性4. InstructGPT4.1 引言4.2 方法4.2.1 数据收集4.2.2 各部分模型4.3 …

RabbitMQ之介绍

1.1 MQ的相关概念 1.1.1 什么是MQ ​ MQ&#xff0c;从字面意思上看&#xff0c;本质是个队列&#xff0c;FIFO先入先出&#xff0c;只不过队列中存放的内容是message而已&#xff0c;还是一种跨进程的通信机制&#xff0c;用于上下游传递消息。在互联网架构中&#xff0c;MQ…

RBF-UKF径向基神经网络结合无迹卡尔曼滤波估计锂离子电池SOC(附MATLAB代码)RBF神经网络训练部分

1.清空变量 close all clear,clc 2.导入数据用以RBF神经网络训练&#xff0c;一共14组&#xff0c;训练数据P&#xff08;第一列为电压值&#xff0c;第二列为SOC值&#xff0c;第三列为电流值。&#xff09;&#xff0c;并将所有数据存储在变量PP中&#xff0c;所有电压数据…

聊聊架构方案选择

大家好&#xff0c;我是易安&#xff01; 在完成备选方案设计后&#xff0c;如何挑选最终的方案是一个很大的挑战&#xff0c;因为每个备选方案都是可行的。但是&#xff0c;没有哪个备选方案是完美的&#xff0c;因为每个方案都存在一些缺点或风险。此外&#xff0c;评价备选方…

如何编写REST API

编写REST API REST API规范 编写REST API,实际上就是编写处理HTTP请求的async函数,不过,REST请求和普通的HTTP请求有几个特殊的地方: REST请求仍然是标准的HTTP请求,但是,除了GET请求外,POST、PUT等请求的body是JSON数据格式,请求的Content-Type为application/json;…