当前位置： 首页 > article >正文

数据结构与算法分析——你真的理解查找算法吗——二叉查找树（代码详解）

article 2024/10/31 7:28:01

一、算法描述

在内存中进行二分查找的效率我们已经看到了,非常高效。但是,当查找集合频繁地变动时,二分查找的效率退化得非常产重。如果需要处理动态的数据集合,我们需要采用一种不同的数据结构来得到可以接搜的查找性能。
要存储动态的查找数据集合的话,查找树可能是最常用的数据结构了。无论是在内存中还是在二级存储器上,查找树的性能都非常优秀,最经常使用的查找树是二叉查找树,其每一个内部节点都有两个子节点。另外一种查找树——B树,是一棵元树,是属于磁盘上的数据结构。
使用了查找树之后的输入和输出和二分查找的一样。集合C中每一个元素e都将被存储到查找树中,并且这些元素都需要有一个或者更多的属性能够作为键值,这些键值决定了全集U。元素也必须有能够区分它们的属性。查找树将会存储C中的元素。
二叉查找树（Binary Search Tree, BST）是一种特殊的二叉树，具有以下性质：对于每个节点，左子树中的所有节点值都小于该节点的值，右子树中的所有节点值都大于该节点的值。以下是二叉查找树的基本操作过程，包括插入、查找和删除。

1. 插入操作

步骤：
  1. 从根节点开始比较要插入的值与当前节点的值。
  2. 如果要插入的值小于当前节点的值，则向左子树递归插入；如果大于，则向右子树递归插入。
  3. 当找到一个空位置时，将新值插入到该位置。

2. 查找操作

步骤：
  1. 从根节点开始比较要查找的值与当前节点的值。
  2. 如果相等，返回当前节点。
  3. 如果要查找的值小于当前节点的值，则向左子树递归查找；如果大于，则向右子树递归查找。
  4. 如果找到空节点，说明该值不存在。

3. 删除操作

删除操作稍微复杂，分为三种情况：

  1. 删除叶子节点：直接删除该节点。
  2. 删除有一个子节点的节点：将其子节点直接替代该节点。
  3. 删除有两个子节点的节点：找到该节点的后继节点（右子树中最小的节点），用后继节点的值替代当前节点的值，然后删除后继节点。

4. 遍历操作

常见的遍历方式有：

  • 前序遍历：访问当前节点 -> 递归访问左子树 -> 递归访问右子树。
  • 中序遍历：递归访问左子树 -> 访问当前节点 -> 递归访问右子树（得到升序排列）。
  • 后序遍历：递归访问左子树 -> 递归访问右子树 -> 访问当前节点。

二、复杂度分析

二叉查找树（Binary Search Tree, BST）是一种特殊的二叉树，具有以下性质：
1.每个节点最多有两个子节点，即左子节点和右子节点。
2.左子树中的所有节点的值都小于其父节点的值。
3.右子树中的所有节点的值都大于其父节点的值。
4.左右子树也分别为二叉查找树。
5.不能有重复的节点值（这个性质有时可以放宽）。
二叉查找树的复杂度分析涉及各种操作，包括搜索、插入、删除和遍历等。以下是对这些操作的复杂度分析：
搜索（Search）
1.最坏情况时间复杂度：O(n)，即当树退化为链表（即每个节点只有左子节点或右子节点）时，搜索需要遍历整个树。
2.平均情况时间复杂度：O(log n)（假设树是平衡的），即在平衡的二叉查找树中，每次搜索都可以排除一半的可能性，类似于二分查找。
3.最好情况时间复杂度：O(1)，即当搜索的节点是根节点时，只需要一次比较。
插入（Insert）
1.最坏情况时间复杂度：O(n)，即当树退化为链表时，需要遍历整个树以找到插入位置。
2.平均情况时间复杂度：O(log n)（假设树是平衡的），即在平衡的二叉查找树中，找到插入位置所需的时间类似于二分查找。
3.最好情况时间复杂度：O(1)，即当插入位置是根节点或叶子节点且无需遍历其他节点时。
删除（Delete）
1.最坏情况时间复杂度：O(n)，即当树退化为链表时，需要遍历整个树以找到要删除的节点，并且在删除后可能需要重新平衡子树。
2.平均情况时间复杂度：O(log n)（假设树是平衡的），即在平衡的二叉查找树中，找到删除位置并重新平衡子树所需的时间与搜索类似。
3.最好情况时间复杂度：O(1)（删除叶子节点），即当删除的节点是叶子节点且不需要重新平衡子树时。
遍历（Traversal）
1.中序遍历（In-order Traversal）：O(n)
访问顺序是左子树 -> 根节点 -> 右子树，按升序输出节点值。
2.前序遍历（Pre-order Traversal）：O(n)
访问顺序是根节点 -> 左子树 -> 右子树。
3.后序遍历（Post-order Traversal）：O(n)
访问顺序是左子树 -> 右子树 -> 根节点。
4.层次遍历（Level-order Traversal）：O(n)
按层次从上到下、从左到右访问节点。
平衡性
二叉查找树的最坏情况性能通常发生在树变得不平衡时。为了避免这种情况，可以使用自平衡二叉查找树，如AVL树、红黑树等，这些树在插入和删除操作后会保持平衡，从而确保O(log n)的时间复杂度。
总结
1.最坏情况时间复杂度：O(n)（树退化为链表）
2.平均情况时间复杂度：O(log n)（假设树是平衡的）
3.最好情况时间复杂度：O(1)（某些特定情况）
这些复杂度分析表明，虽然二叉查找树在最坏情况下性能较差，但在实际应用中，通过保持树的平衡，可以有效地提高其性能。

三、适用情况

对于程序员来说,内存泄漏是一个非常严重的问题,当程序需要长时间运行时,例如现在的大多数服务器程序,内存泄漏将会最终导致程序耗尽物理内存然后崩漬掉,这就会产生非常严重的后果。
一个程序员可能会写一个程序来监视内存分配和回收,并且报告程序的使用情况,以便于益视内存泄漏。这个内存分析程序可以仅仅是简单地重写一个新的malloc()和free()函数来记录每一次分配和释放内存的信息。我们希望记录每一次内存分配操作,并且当内存释放时,我们必须及时更新信息。
在前面的播述中,我们不可能知道我们将要存储多少个元素。一个基于散列的查找也许可以正常工作。但是我们也许会选择一个错误的散列表规模,以至于影响高效的资源使用。一个替代的查找策略是采用查找树。当我们准备在内存中维护我们的查找数据时,我们使用二叉查找树能够很好地做到这个。二叉查找树在动态数据,尤其是插人和删除操作非常频繁时,性能表现非常好。
一棵二叉查找树,T是一个节点的有限集合,并且节点之河能够通过有序的特征,如键值,来进行区分,节点的集合可以是空,或者只是包含了一个根节点nr,每一个节点都指向了两棵子二叉查找树,T,和T,并且满足这样的性质:如果人是节点的键值,那么所有在T的元素的键值都小于等于k,所有在T,的元素的键值都大于k,这个性质叫做二叉查找树性质(Cormen等,2001)。图5-8给出了一棵二又树的例子。每一个节点都有一个整数健值,唯一的区分节点。你可以看到在图5-8的树中寻找一个键值只需要从根节点开始,最多探测3个节点。这棵树是完全平衡的。也就是说,每一个节点恰好有两个子节点。一棵完全平衡二叉树有2“11个节点。
在这里插入图片描述

树也可能不会总是平衡的。在最坏情况下,一棵树可能退化到链表的性能。考虑使用和上图相同的节点,但是如果按照下图的方式来排列的话。节点被按照升序添加,虽然这个结构的确满足了二叉树的严格定义,每一个市点的左子树都是空的。这棵树简直就是一个链表。
在这里插入图片描述
1.数据规模位置,并且程序必须能够处理任何规模的数据。
2.数据集是高度动态的,在程序运行时候会有大量的插入和删除操作。
3.程序需要按照升序或者降序来遍历元素。
一且我们决定使用二叉查找树,我们必须做出如下的决定。
1.如果我们需要从任何指定节点起有序遍历数据集,那么在节点的结构中必须包括指向父节点的指针。
2.如来数摇是动态的,我们必须平衡树。
在大多数应用程序中,我们需要平衡树结构来避免出现偏置,偏置树的某些分支可能会比其他分支长或者短很多,在最坏情况下,会导致图5-9那样的退化树。两个流行的平衡树可以使用。一个是AVL树,由Adel son-Vel skii和Landis于1962年提出。一棵AVL树遵循如下的平衡性质:任何一个节点的子树的高度都不可能比其他节点的子树的高度大1。
最近更加频繁使用的平衡树叫做红黑树。红黑树是一个近似平衡的。使用红黑树能够保证任何一个分支的长度都不会超过其他的分支长度的两倍。一个红黑树满足如下条件(Cormen等,2001):
1.每一个节点被标记为红色或者黑色。
根节点是黑色的。
每一个叶子节点值为空,并且是黑色的。
所有的红色节点都有两个黑色子节点。
从一个节点到共子树的叶子节点的每条路径包含了同样数目的黑色节点。
在下图中,由于篇幅的关系,我们并不会给出空值的叶子节点。当你仔细看图时,你能够想象图中每一个叶子节点实际上有两个黑色子节点,每一个都是空值。
下图所示的是一颗有效的红黑树,它包含7个不同的整数,按照如下的顺序插入:13,26,43,17,25,15,16.
在这里插入图片描述
现在我们希望加入一个键值是14的节点。按照如上所述的性质,14将会被作为13的右子节点。红黑树插入算法将会修改这棵树,如下图所示,我们将在下一节“算法实现”中描述这个过程。
在这里插入图片描述

四、算法实现

#include <stdio.h>
#include <stdlib.h>

// 定义节点颜色
#define RED 1
#define BLACK 0

// 定义红黑树节点
struct Node {
    int data;
    int color;
    struct Node* left;
    struct Node* right;
    struct Node* parent;
};

// 定义 NIL 哨兵节点
struct Node* NIL = NULL;

// 创建新节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->color = RED;  // 新插入节点默认为红色
    newNode->left = NIL;
    newNode->right = NIL;
    newNode->parent = NULL;
    return newNode;
}

// 左旋
void leftRotate(struct Node** root, struct Node* x) {
    struct Node* y = x->right;
    x->right = y->left;
    
    if (y->left != NIL) {
        y->left->parent = x;
    }
    
    y->parent = x->parent;
    
    if (x->parent == NULL) {
        *root = y;
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }
    
    y->left = x;
    x->parent = y;
}

// 右旋
void rightRotate(struct Node** root, struct Node* y) {
    struct Node* x = y->left;
    y->left = x->right;
    
    if (x->right != NIL) {
        x->right->parent = y;
    }
    
    x->parent = y->parent;
    
    if (y->parent == NULL) {
        *root = x;
    } else if (y == y->parent->right) {
        y->parent->right = x;
    } else {
        y->parent->left = x;
    }
    
    x->right = y;
    y->parent = x;
}

// 修复红黑树
void fixInsert(struct Node** root, struct Node* z) {
    while (z->parent != NULL && z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            struct Node* y = z->parent->parent->right;
            if (y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->right) {
                    z = z->parent;
                    leftRotate(root, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rightRotate(root, z->parent->parent);
            }
        } else {
            struct Node* y = z->parent->parent->left;
            if (y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    rightRotate(root, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                leftRotate(root, z->parent->parent);
            }
        }
    }
    (*root)->color = BLACK;
}

// 插入节点
void insert(struct Node** root, int data) {
    struct Node* z = createNode(data);
    struct Node* y = NULL;
    struct Node* x = *root;
    
    while (x != NIL) {
        y = x;
        if (z->data < x->data) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    
    z->parent = y;
    
    if (y == NULL) {
        *root = z;
    } else if (z->data < y->data) {
        y->left = z;
    } else {
        y->right = z;
    }
    
    z->left = NIL;
    z->right = NIL;
    z->color = RED;
    
    fixInsert(root, z);
}

// 中序遍历
void inorder(struct Node* root) {
    if (root != NIL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

// 初始化 NIL 节点
void initNILNode() {
    NIL = (struct Node*)malloc(sizeof(struct Node));
    NIL->color = BLACK;
    NIL->left = NIL->right = NIL->parent = NULL;
}

int main() {
    initNILNode();  // 初始化 NIL 哨兵节点
    struct Node* root = NIL;

    insert(&root, 10);
    insert(&root, 20);
    insert(&root, 30);
    insert(&root, 40);
    insert(&root, 50);
    insert(&root, 25);

    printf("中序遍历: ");
    inorder(root);
    printf("\n");

    return 0;
}

原书这里是java代码，后续作者会将此补充完整。
红黑树和其他的平衡二叉查找树一样,比简单的二叉查找树实现复杂得多。不过这个代价通常是值得的,因为我们可以很明显地看到性能的改进。红黑树有两个存储方面的需求。
1.每一个节点需要存储其颜色,至少需要一个bit,但是事实上大多数实现都使用了至少一个字节。
2.每一个节点都必须有一个父节点的链接,这个在二叉查找树中是不需要的。
红黑树的根节点必须是空值的。程序员能够让所有的叶子节点的指针都指向这个单个空值节点。
红黑树查找的平均性能和二叉查找一样,都是O(log n)。但是,插入和副除操作也能够在O(log n)时间内完成。

五、算法优化

存在着一些其他的平衡树结构。最常见的就是之前提到的AVL树。红黑树和其他的平衡二叉查找树是内存查找的最好选择。当数据规模变得非常大,以至于不能完全存储在内存中时,另外一种树结构就能够派上用场:n路树,其每一个节点都有n>2个子节点。这类树的一个常见版本叫做B树,它能够最小化在一个大数据集中寻找特定元素时所需要
的磁盘存取操作。B树同样被用来实现关系数据库。

六、引用及参考文献

1.《算法设计手册》


http://www.kler.cn/a/372670.html

相关文章：

  • Electron 是一个用于构建跨平台桌面应用程序的开源框架
  • 大模型，多模态大模型面试【LoRA，分类，动静态数据类型，DDPM，ControlNet，IP-Adapter, Stable Diffusion】
  • 【力扣刷题实战】相同的树
  • 2024年优秀的天气预测API
  • 《高频电子线路》 —— 高频谐振功放
  • 推荐系统中的AB测试
  • 论文阅读：三星-TinyClick
  • k8s之调动pod到指定节点与创建多容器pod并查找pod日志
  • 【设计模式】《Java 设计模式魔法：解锁高效编程的秘密武器》
  • Linux线程安全（二）条件变量实现线程同步
  • Logstash 迁移索引元数据（设置和映射）
  • Word中遇到的问题记录（页眉，页码分节符，跨页断行）
  • 《Web性能权威指南》-浏览器API与协议-读书笔记
  • 搭建普通 Spring IoC 项目
  • 白立新：人工智能爆发，倒逼人类走向“三体全能”
  • 阿里巴巴店铺商品API返回值中的商品分类与筛选条件
  • QT如何给视频打时标
  • PG数据库之事务处理
  • 域渗透AD渗透攻击利用 python脚本攻击之IPC连接 以及 python生成exe可执行程序讲解方式方法
  • 「Mac畅玩鸿蒙与硬件7」鸿蒙开发环境配置篇7 - 使用命令行工具和本地模拟器管理项目
  • Spring Boot 安全 API 构建：加密解密功能的卓越实践
  • Linux 上安装 conda 步骤实现
  • 一、ARMv8寄存器之通用、状态、特殊寄存器
  • String常量池
  • 【秋招笔试-支持在线评测】10.30花子秋招(已改编)-三语言题解
  • Codeforces Global Round 27 D.Yet Another Real Number Problem