前言

关于初上手做二叉搜索树和平衡二叉树but没有相关了解而被干碎了，遂抓紧学习基本概念而写博客

关于树方面更加深入的了解，如现在的二叉搜索树（BST），后来的平衡二叉树（AVL）、B树、B+树、红黑树等。除去对于习题方面的提高外，更重要的是能应用于实际开发中的，从中获取的优化程序的能力和拆解问题建立抽象模型的思维能力。

一、基本概念——什么是二叉搜索树

二叉搜索树（BST,Binary Search Tree）又称二叉排序树、二叉查找树

首先，它可以是一棵空树；

若不是，则它需要满足以下条件：

1. 非空左子树的所有键值小于其根节点的键值
2. 非空右子树的所有键值大于其根节点的键值
3. 左右子树也分别为二叉搜索树

二叉搜索树一般不支持key值冗余（不允许有重复的key值）

如图为一棵标准的二叉搜索树：

相比较于常规的二叉树，二叉搜索树具有明显的大小区分度，对二叉搜索树进行中序遍历，所获取的键值便是严格从小到大排序的。

也因此，二叉搜索树较普通的二叉树具有显著高效的搜索效率，平均时间复杂度一般为O（logn），当退化为普通二叉树或不“平衡”时，最坏会退化为O（n）。图示为普通数组、普通二叉树、二叉搜索树之间，对元素操作的平均时间复杂度：

二、二叉搜索树的应用——K模型与KV模型

K即key，V即value，分别对应的是单键值和键值对的情况；

1、K模型

K 模型即 key 模型，在这种模型下，二叉搜索树的每个节点仅存储一个关键码（key）。其主要功能是判断某个关键码是否存在于树中，也就是进行查找操作。

特点
  • 存储单一：每个节点只保存一个关键码，没有与之关联的其他数据。
  • 查找为主：主要用途是查找某个关键码是否存在，插入和删除操作也是围绕关键码进行的。
#include <stdio.h>

typedef struct TreeNodeK {
    int key; // 单键值
    struct TreeNodeK *left;
    struct TreeNodeK *right;
} TreeNodeK;

int main()
{
    return 0;
}

2、KV模型

KV 模型即 key-value 模型，在这种模型下，二叉搜索树的每个节点除了存储关键码（key）之外，还会存储与之关联的值（value）。可以把它想象成一个字典，通过关键码来查找对应的值。

如C++中stl的std::map和std::set，都是基于红黑树来创建的，以实现哈希方法或存储唯一元素并自动排序，而红黑树本质上也是一棵自平衡的二叉搜索树（或干脆称之为平衡二叉搜索树）

特点
  • 存储关联：每个节点存储一个关键码和一个与之关联的值，形成键值对。
  • 数据映射：不仅可以判断关键码是否存在，还能获取关键码对应的关联值。
#include <stdio.h>

typedef struct TreeNodeKV {
    int key; // 键值
    int value; // 键值对应的value
    struct TreeNodeKV *left;
    struct TreeNodeKV *right;
} TreeNodeKV;

int main()
{
    return 0;
}

三、二叉搜索树的基本操作（K模型为例）

1、查找元素

给定目标节点值 num ，可以根据二叉搜索树的性质来查找。我们声明一个节点 curr，从二叉树的根节点 root 出发，循环比较节点值 curr.val 和 num 之间的大小关系。由于二叉搜索树不支持键值冗余，不会存在父节点、孩子结点相等的情况，且每次都会根据大小排除一半的可能性，因此对于平衡的二叉搜索树，其查找效率和二分查找是相同的O（logn）。如图所示：

// 查找函数的实现
TreeNode *search(TreeNode *bst, int num)
{
    TreeNode *curr = bst->root;
    while (curr != NULL)
	{
        if (curr->val < num)
		{
            // 目标节点在 curr 的右子树中
            curr = curr->right;
        }
		else if (curr->val > num)
		{
            // 目标节点在 curr 的左子树中
            curr = curr->left;
        }
		else
		{
            // 找到目标节点，跳出循环
            break;
        }
    }
    // 返回目标节点
    return curr;
}

通过对于查找操作的学习，可以完成 98. 验证二叉搜索树 题目：

bool func(struct TreeNode* root, long low, long high)
{
    if (root == NULL) // 空树必然满足条件
    {
    	return true; // 或者递归遍历寻找到叶节点仍然满足条件
	}
    long num = root->val;
    if (num <= low || num >= high)
    {
    	return false; // 超出限定范围，则不满足条件
	}
    // 递归的调用，以判断左子树和右子树性质
    return func(root->left, low, num) && func(root->right, num, high);
}

bool isValidBST(struct TreeNode* root)
{
    // 考虑到不支持键值冗余，且root->val可以达到int的MIN和MAX，故使用long
    return func(root, LONG_MIN, LONG_MAX);
}

2、插入操作

当树为空树，则可以以结点为根建立树

若不为空，则需按照二叉搜索树的性质查找临界的结点并插入

在进行插入操作的代码实现过程中，应当注意以下的点：

1、二叉搜索树不支持键值冗余，因此对于树中已存在的键值，应当直接返回退出

2、由于需要进行插入的操作，因此每遍历查找至一层，都需要另外的一个指针记录当前结点的父节点（或者直接使用递归的方式，不过应当考虑到递归可能带来的栈溢出情况，这里采用递归法）

// 创建新节点
TreeNode* createNode(int val)
{
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 插入节点
TreeNode* insert(TreeNode* root, int val)
{
    if (root == NULL)
	{
        return createNode(val);
    }
    if (val < root->val)
	{
        root->left = insert(root->left, val);
    }
	else
	{
        root->right = insert(root->right, val);
    }
    return root;
}

对应着 701. 二叉搜索树中的插入操作 题目

struct TreeNode* createTreeNode(int val)
{
    struct TreeNode* ret = malloc(sizeof(struct TreeNode));
    ret->val = val;
    ret->left = ret->right = NULL;
    return ret;
}

// 迭代法的实现
struct TreeNode* insertIntoBST(struct TreeNode* root, int val)
{
    if (root == NULL)
	{
        root = createTreeNode(val);
        return root;
    }
    struct TreeNode* pos = root;
    while (pos != NULL)
	{
        if (val < pos->val)
		{
            if (pos->left == NULL)
			{
                pos->left = createTreeNode(val);
                break;
            }
			else
			{
                pos = pos->left;
            }
        }
		else
		{
            if (pos->right == NULL)
			{
                pos->right = createTreeNode(val);
                break;
            }
			else
			{
                pos = pos->right;
            }
        }
    }
    return root;
}

3、删除操作

查找元素是否在二叉搜索树中，如果不存在，则返回

否则就应当遵守以下规则：

1. 要删除的节点无孩子节点 ——可以直接删除该节点
2. 要删除的节点只有左孩子节点——让左孩子节点替代该节点位置，并删除该节点
3. 要删除的节点只有右孩子节点——让右孩子节点替代该节点位置，并删除该节点
4. 要删除的节点有左右孩子节点——由二叉树的性质，查找删除节点的右子树key值最小节点，让最小节点的key覆盖掉删除节点的key。因为右子树是全部大于父节点的结点，而右子树最小的结点不存在孩子（否则一定不为最小结点），且可以始终满足大于原父节点左子树，小于原父节点右子树的性质

TreeNode* findMin(TreeNode* root)
{
    while (root->left != NULL)
	{
        root = root->left;
    }
    return root;
}

TreeNode* deleteNode(TreeNode* root, int key)
{
    if (root == NULL)
	{
        return root;
    }
    if (key < root->val)
	{
        root->left = deleteNode(root->left, key);
    }
	else if (key > root->val)
	{
        root->right = deleteNode(root->right, key);
    }
	else
	{
        // 情况 1: 没有子节点或只有一个子节点
        if (root->left == NULL)
		{
            TreeNode* temp = root->right;
            free(root);
            return temp;
        }
		else if (root->right == NULL)
		{
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        // 情况 2: 有两个子节点
        TreeNode* temp = findMin(root->right);
        root->val = temp->val;
        root->right = deleteNode(root->right, temp->val);
    }
    return root;
}

以及对应的题目 450. 删除二叉搜索树中的节点

struct TreeNode* deleteNode(struct TreeNode* root, int key)
{
    if (root == NULL)
	{
        return NULL;
    }
    if (root->val > key)
	{
        root->left = deleteNode(root->left, key);
        return root;
    }
    if (root->val < key)
	{
        root->right = deleteNode(root->right, key);
        return root;
    }
    if (root->val == key)
	{
        if (!root->left && !root->right)
		{
            return NULL;
        }
        if (!root->right)
		{
            return root->left;
        }
        if (!root->left)
		{
            return root->right;
        }
        struct TreeNode *successor = root->right;
        while (successor->left)
		{
            successor = successor->left;
        }
        root->right = deleteNode(root->right, successor->val);
        successor->right = root->right;
        successor->left = root->left;
        return successor;
    }
    return root;
}

四、K模型与KV模型的具体实现

1、K模型

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

// 定义 K 模型二叉搜索树的节点结构
typedef struct TreeNodeK
{
    int key;
    struct TreeNodeK *left;
    struct TreeNodeK *right;
} TreeNodeK;

// 创建新节点
TreeNodeK* createNodeK(int key)
{
    TreeNodeK* newNode = malloc(sizeof(TreeNodeK));
    newNode->key = key;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 插入节点
TreeNodeK* insertK(TreeNodeK* root, int key)
{
    if (root == NULL)
	{
        return createNodeK(key);
    }
    if (key < root->key)
	{
        root->left = insertK(root->left, key);
    }
	else if (key > root->key)
	{
        root->right = insertK(root->right, key);
    }
    return root;
}

// 查找节点
TreeNodeK* searchK(TreeNodeK* root, int key)
{
    if (root == NULL || root->key == key)
	{
        return root;
    }
    if (key < root->key)
	{
        return searchK(root->left, key);
    }
    return searchK(root->right, key);
}

// 中序遍历
void inorderK(TreeNodeK* root)
{
    if (root != NULL)
	{
        inorderK(root->left);
        printf("%d ", root->key);
        inorderK(root->right);
    }
}

// 释放树的内存
void freeTreeK(TreeNodeK* root)
{
    if (root != NULL)
	{
        freeTreeK(root->left);
        freeTreeK(root->right);
        free(root);
    }
}

2、KV模型

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

// 定义 KV 模型二叉搜索树的节点结构
typedef struct TreeNodeKV
{
    int key;
    int value;
    struct TreeNodeKV *left;
    struct TreeNodeKV *right;
} TreeNodeKV;

// 创建新节点
TreeNodeKV* createNodeKV(int key, int value)
{
    TreeNodeKV* newNode = (TreeNodeKV*)malloc(sizeof(TreeNodeKV));
    newNode->key = key;
    newNode->value = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 插入节点
TreeNodeKV* insertKV(TreeNodeKV* root, int key, int value)
{
    if (root == NULL)
	{
        return createNodeKV(key, value);
    }
    if (key < root->key)
	{
        root->left = insertKV(root->left, key, value);
    }
	else if (key > root->key)
	{
        root->right = insertKV(root->right, key, value);
    }
    return root;
}

// 查找节点
int* searchKV(TreeNodeKV* root, int key)
{
    if (root == NULL || root->key == key)
	{
        return root ? &root->value : NULL;
    }
    if (key < root->key)
	{
        return searchKV(root->left, key);
    }
    return searchKV(root->right, key);
}

// 中序遍历
void inorderKV(TreeNodeKV* root)
{
    if (root != NULL)
	{
        inorderKV(root->left);
        printf("(%d, %d) ", root->key, root->value);
        inorderKV(root->right);
    }
}

// 释放树的内存
void freeTreeKV(TreeNodeKV* root)
{
    if (root != NULL)
	{
        freeTreeKV(root->left);
        freeTreeKV(root->right);
        free(root);
    }
}

五、浅总结

总而言之，二叉搜索树BST是后续的树结构的基础，尤其是较为接近的平衡二叉树AVL，其除去平衡因子的限制外，本身就是一棵二叉搜索树，以及后续的红黑树（弱平衡二叉树）等，因此对于它的掌握与理解，是非常关键而重要的。

# 数据结构 # c语言 # 算法
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

魔乐社区虾王挑战赛 · OpenClaw虾客松正式启动！

avatar 魔乐社区
cover

「极限压缩 量化未来」Modelers GeekDay上海站圆满落幕

avatar 魔乐社区
cover

量化挑战赛冠军专访：4小时啃下W4A8量化，我靠的是这些经验

avatar 魔乐社区