插图: 什么是二进制排序树？

点击上方的“五分钟内学习算法”，

设置为“顶部或星级”以尽快交付干货.

来自静宇

Jing Yu的写作风格一如既往的精致: )，欢迎关注他.

以下是原文.

今天，我们谈论二进制排序树，这是您会爱上的数据结构，当然，人们有优缺点，因此二进制排序也是如此. 让我们集思广益，征服她.

二叉排序树（Binary Sort Tree）或一棵空树；或具有以下属性的二叉树:

（1）如果左子树不为空，则左子树上所有节点的值均小于其根节点的值;

（2）如果右子树不为空，则右子树上所有节点的值都大于其根节点的值;

（3）其左和右子树分别是二进制排序树.

很明显，二进制排序树的定义是递归形式，因此二叉排序树中序遍历，Jing Yu将要讨论的插入，搜索和删除都是基于递归形式的.

下图中的二进制树是典型的二进制排序树:

由于二进制排序树的名称中包含单词sort，因此这是其优于普通二进制树的优势. 此时可能还不清楚，没关系，我们将逐步在上面建立一个二叉树会很清楚.

假设我们最初具有以下无序序列:

第1步: 插入8作为根节点.

步骤2: 插入3并将其与根节点8进行比较. 如果它小于8，并且根节点没有左子节点，则将3插入左子节点8.

第三步: 插入10，首先将其与根节点进行比较，发现它大于8，然后将10插入根节点的右子树中；如果根节点8的右子树为空，则使用10作为第8个右子树.

第四步: 插入1，首先与根节点比较，该根节点小于根节点，则应插入根节点的左子树. 然后与根节点的左子节点3进行比较，发现它小于3，则应插入3的左子节点.

步骤5: 插入6，首先与根节点8（小于8）进行比较，然后移至左侧；然后与3进行比较，大于3，转到那里，没有节点，然后使用6作为3的右子.

步骤6: 插入14，首先与大于8的8进行比较，然后移至右侧；然后与右边的8个孩子中的10个（大于10个）进行比较，然后转到没有节点的右边二叉排序树中序遍历，然后使用14作为10个右边的孩子.

第7步: 首先插入4，然后与8进行比较，找到小于8的位置，然后向左比较，然后与3进行比较，向右大于3的位置进行比较，然后与6进行比较，不带孩子的话向左走左，4作为6的左子代.

步骤8: 首先插入7，然后与8进行比较，发现它小于8，向左走，然后与3比较，向右走，与6比较，继续向右走，然后发现6没有合适的孩子，然后插入7作为6的右子代.

第9步: 插入13，首先与右侧比较8（大于），然后与右侧比较10（大于），然后与左侧比较14（小于），然后找到左侧14岁的孩子是空的. 将13插入14的左子位置.

上面构造的二元排序树的中阶遍历结果（对于二叉树的不熟悉遍历，可以参考扫描二叉树的所有遍历方法）:

二进制搜索是在有序数组上执行的，就像我们通过对二进制排序树执行中阶遍历所获得的结果一样. 最初，我们将整个有序数组用作二进制搜索的搜索空间，然后计算搜索空间的中间元素并将其与搜索元素进行比较；然后将整个搜索空间减少一半；重复上述步骤，直到找到要查找的元素或返回搜索失败的信息. 有关二进制搜索的详细介绍，请参阅本文.

二元排序树的搜索操作与二元搜索非常相似，我们尝试一起查找值为13的节点.

步骤1: 访问根节点8.

第二步: 根据二元排序树的左子树的性质小于根节点，而右子树大于根节点，则13> 8，因此值13的节点可能是在根节点上，在点8的右子树中，我们查看根节点的右子节点10:

步骤3: 与第二步13> 10相似，因此请看节点10的右子节点14:

第四步: 根据二元排序树的左子树的性质小于根节点，右子树大于根节点，13 <14，所以看左子13之14并发现它只是要找到的值相等:

二进制排序树搜索操作的实现

struct node* search(struct node* root, int key) 
{ 
 // 如果root为空或者root的值和待查找的key相同，则返回root
 if (root == NULL || root->key == key) 
 return root; 
 
 // 当待查找的关键字大于根结点的值，则递归查找根结点的右子树
 if (root->key < key) 
 return search(root->right, key); 
 // 当待查找的关键字小于根结点的值，则递归查找根结点的左子树
 return search(root->left, key); 
} 

对于将要插入的任何元素x插入到二进制排序树的叶节点中，问题的关键在于确定插入位置，原理当然与上述搜索操作相同，即开始从根节点判断，直到到达叶节点为止，都可以将要插入的元素作为叶节点插入.

假设我们现在要插入一个值为9的节点，该怎么办？

第1步: 访问根节点8

步骤2: 根据属性，二进制排序树的左子树小于根节点，右子树大于根节点9> 8，因此应将值9的节点插入根在节点8的右子树中，我们查看根节点的右子节点10:

第三步: 根据二进制排序树的左子树小于根节点的性质，右子树大于根节点9 <10，因此应插入值为9的节点进入节点在点10的左子树中，当访问节点10的左子节点并发现其为空时，将9插入为节点10的左子节点.

struct node* insert(struct node* node, int key) 
{ 
    /*如果树为空，则返回一个新的结点，相当于上面例子中10的左子树为空，则将9插入到10的左子树 */
    if (node == NULL) return newNode(key); 
  
    /*当插入的值key小于当前结点的key，则递归判断左子树*/
    if (key < node->key) 
        node->left  = insert(node->left, key); 
    else if (key > node->key)  /*当插入的值key大于当前结点的key，则递归判断右子树子树*/
        node->right = insert(node->right, key);    
  
    /* 返回结点指针*/
    return node; 
} 

删除操作不同于搜索和插入操作，我们需要处理以下三种情况:

首先，已删除的节点D是叶节点: 可以直接从二进制排序树中删除它，并且不会影响树的结构

第二，删除的节点D只有一个子节点: 如果只有左子节点而没有右子节点，则只需将要删除的节点的左子节点链接到要删除的节点的父节点，然后删除节点D可以；如果只有右子节点而没有左子节点，则只需将节点D的右子节点重新连接到节点D的父节点.

假设我们要删除值为14的节点，该节点只有一个左子节点13，没有右子节点.

第一步: 将要删除的节点14的左子节点13保存到临时变量temp，并删除节点14；

步骤2: 将已删除节点14的父节点10的右子节点设置为temp，即节点13.

让我们以删除节点10为例，然后看看没有左子，只有右子的情况.

步骤1: 将要删除的节点10的右子节点14保存到临时变量temp，并删除节点10；

步骤2: 将已删除节点10的父节点8的右子节点设置为temp，即节点14.

三个，已删除节点的左右子节点存在

这种情况更为复杂，但我相信，只要萧玉玉耐心阅读，就会有收获. 这次，我们将使图片更加复杂，在原始结10上添加一个左子结. 点9.

上述二进制排序树的中阶遍历结果如下:

现在，我们不首先考虑对二进制排序的删除操作，而仅考虑对获得的中阶遍历结果进行删除. 让我们以删除中阶遍历结果中的顶点8为例:

删除中阶遍历结果中的8后，哪种方法不会改变中阶遍历结果的顺序？

让我们看一下如何删除左右子节点中存在的节点. 我们仍然以删除根节点8为例. 首先，让我们看一下用根节点左子树中具有最大值的节点7替换根节点的情况.

第一步: 获得要删除的节点8的左子树中具有最大值的节点7，并将其保存在临时指针变量temp中（此步骤可以通过删除该节点的左子节点3开始. 节点. 访问正确的子节点，直到获得叶节点）:

步骤2: 将删除节点8的值替换为7；

第三步: 删除根节点左子树中值最大的节点（此步骤可能使左子节点在左子树中具有最大值的节点，但没有右子节点，然后delete会退化为第二种情况，只需递归调用即可）:

让我们看一下删除节点的右子树中具有最小值的节点替换删除节点的情况:

第一步: 在删除节点8的右子树中找到值最小的节点，即9（首先访问删除节点的右子节点10，然后一直向左走，直到左子节点为如果为空，则获得右侧子树中具有最小值的节点.

步骤2: 将删除节点8的值替换为9；

第3步: 删除根节点右子树中具有最小值的节点.

上面是对删除二进制排序树的三种情况的分析.

二进制排序树的删除操作代码的实现:

struct node* deleteNode(struct node* root, int key)
{
 // 如为空，直接返回
 if (root == NULL) return root;
 // 如果删除的值小于 root 的值，则递归的遍历rootde左子树
 // 即删除结点位于左子树
 if (key < root->key)
  root->left = deleteNode(root->left, key);
 // 如果删除的值大于 root 的值，则递归的遍历root的右子树
 // 即删除结点位于右子树
 else if (key > root->key)
  root->right = deleteNode(root->right, key);
 // 如果值相等，则删除结点
 else
 {
  /*第一种情况可以包含在第二种当中，所以不做处理
   这里处理第二种情况*/
  //删除结点的左孩子为空
  if (root->left == NULL)
  {
   struct node *temp = root->right;
   if(root->key == 30){
                printf(%d\n,temp->key);
   }
   free(root);
   return temp;
  }
  else if (root->right == NULL)//删除结点的右孩子为空
  {
   struct node *temp = root->left;
   free(root);
   return temp;
  }
  // 左右孩子均不为空，获取删除结点中序遍历的直接后继结点 
  struct node* temp = minValueNode(root->right);
  // 将删除结点的值替换为直接后继结点的值
  root->key = temp->key;
  // 删除直接后继结点
  root->right = deleteNode(root->right, temp->key);
  /* 或者获取删除结点中序遍历的直接前驱结点。*/
  //struct node* temp = maxValueNode(root->left);
  // root->key = temp->key;
  //root->left = deleteNode(root->left, temp->key);
 }
 return root;
}

插入，搜索和删除二叉树的最差时间复杂度是h，其中h是二叉树的高度. 在最极端的情况下，我们可能必须从根节点访问最深的叶节点，倾斜树的高度可能变为n，并且插入和删除操作的时间复杂度可能会变为. 下图是两棵倾斜的树（相当于一个链表）. 这也是在二进制排序树的多次插入操作之后可能发生的不平衡问题，也是二进制排序树的缺陷，但仍不能阻止它成为很好的数据结构.

问题来自LeetCode 98验证二进制搜索树

给出一个二叉树，确定它是否是有效的二叉搜索树.

假设二叉搜索树具有以下特征:

节点的左子树仅包含少于当前节点的子树. 节点的右子树仅包含大于当前节点的数字. 所有左右子树本身都必须是二叉搜索树.

输入: [2,1,3]

输出: true示例2:

输入: [5,1,4，null，null，3,6].

输出: false

说明: 输入为: [5,1,4，null，null，3,6]. 根节点的值为5，但其右子节点的值为4.

我们将回顾二进制排序树的定义. 二进制排序树（Binary Sort Tree）是一棵空树；或具有以下属性的二叉树:

（1）如果左子树不为空，则左子树上所有节点的值均小于其根节点的值;

（2）如果右子树不为空，则右子树上所有节点的值都大于其根节点的值;

（3）其左和右子树分别是二进制排序树.

最简单的方法是为每个顶点确定其左孩子是否小于它，以及左孩子是否大于它.

bool isValidBST(struct TreeNode* root){
    if( root == NULL ) return true;
    if( root->left != NULL && root->left->val > root->val ) 
        return false;
    if( root->right != NULL && root->right->val < root->val ) 
        return false;
    if( !isValidBST(root->left) || !isValidBST(root->right) ) 
        return false;
    
    return true;
}

上图中的根节点为6，左子树中的节点7大于6，这显然不符合二进制排序树的定义；右子树中的节点1小于根节点6，这也是不合理的. 但是您发现上面的程序将返回true，因为上面的程序仅检查节点的左子节点和右子节点，我们自然会考虑检查节点左子树中的最大顶点是否小于该节点. 如果点较小，则右侧子树中具有最小值的顶点大于该节点会更好. 例如，根节点6的左子树中的最大顶点比6大7，因此它不是二进制排序树，并且返回false. ;

对于每个节点，检查节点左子树中值最大的节点是否小于该节点，右子树中值最小的节点是否大于该节点.

int minValueNode(struct TreeNode* node)
{
 struct TreeNode* current = node;
 /*从删除结点的右孩子开始一直向左走，找到最小值*/
 while (current && current->left != NULL)
  current = current->left;
 return current->val;
}
/* 返回删除结点左子树当中的值最大的结点指针 */
int maxValueNode(struct TreeNode* node)
{
 struct TreeNode* current = node;
 /*从删除结点的右孩子开始一直向左走，找到最小值*/
 while (current && current->right != NULL)
  current = current->right;
 return current->val;
}
bool isValidBST(struct TreeNode* root){
    if(root == NULL) return true;
    if(root->left != NULL && maxValueNode(root->left) >= root->val) return false;
    if(root->right != NULL && minValueNode(root->right) <= root->val) return false;
    if(!isValidBST(root->left) || !isValidBST(root->right)) return false;
    return true;
}

第二种方法在哪里效率低下？对于每个节点，请在左侧子树中找到值最大的节点，然后在右侧子树中找到值最小的节点. 这样，不可避免地要反复搜索自然效率低下的树的子树. 更好的解决方案是只检查树中的每个节点一次. 诀窍是编写一个辅助函数isBSTUtil（struct TreeNode * root，long long min，long long max）遍历树，并不断更新每个遍历节点的最大值和最小值，并将最小值初始设置为LONG_MIN，将最大值设置为LONG_MAX；递归调用左子树时，最大值将更新为节点的值max = root-> val（左子树节点的最大值必须小于root-> val），即，调用isBSTUtil（root ->左，最小，根值）;当右子树被递归调用时，右子树中所有节点的下限也大于root的值，因此update min = root-val（右子树节点的最小值必须大于root-> val），即isBSTUtil（root-> right，root-> val，max）.

int isBSTUtil(struct TreeNode* node, long long min, long long max)  
{  
  /* 是一颗空树 */
  if (node==NULL)  
     return 1; 
        
  /* 结点的值小于等于最小值，或者大于等于最大值都是不合理的，返回false */  
  if (node->val <= min || node->val >= max)  
     return 0;  
  
  /*否则递归地判断结点的左子树和右子树*/
  return 
    isBSTUtil(node->left, min, node->val) && 
    isBSTUtil(node->right, node->val, max); 
}  
bool isValidBST(struct TreeNode* root){
    return isBSTUtil(root,LONG_MIN, LONG_MAX);
}

我们可以使用空指针代替LONG_MIN和LONG_MAX的值. （原理与第三种方法相同. 节点左子树中节点的最大值不会超过该节点的值，并且节点右子树中节点的最小值也将为大于节点的值）

class Solution {
public:
    bool isValidBST(TreeNode* root,TreeNode* l=NULL, TreeNode* r=NULL) {
        if(root == NULL) return true;
        if(l != NULL && root->val <= l->val) return false;
        if(r != NULL && root->val >= r->val) return false;
        return isValidBST(root->left, l, root) and
            isValidBST(root->right, root, r);
    }
};

我们之前讨论过，二进制排序树的中阶遍历结果是一个有序数组，该有序数组的第一个元素必须小于后一个元素.

在进程内遍历中，如果当前访问节点的值小于或等于，则可以传入一个整数变量pre，该变量用于将前一个节点的值保存在递归调用函数中. 他的前任节点不是二叉树.

class Solution {
bool isBSTUtil(struct TreeNode* root, long long& prev) 
{ 
    if (root) { 
        if (!isBSTUtil(root->left, prev)) 
            return false; 
  
        // 当前结点小于等于它的直接前驱顶点，返回false 
        if (root->val <= prev) 
            return false; 
  
        //初始化pre 为当前结点
        prev = root->val; 
  
        return isBSTUtil(root->right, prev); 
    } 
  
    return true; 
} 
public:
    bool isValidBST(TreeNode* root) {
        long long prev = LONG_MIN; 
        return isBSTUtil(root, prev); 
    }
};

如果您有兴趣，可以在LeetCode上提交. 最后一个实现的时间复杂度是空间复杂度.

•C ++如何从代码过渡到游戏？ •告诉您学习编程的技巧（推荐收藏）•自学编程的八个错误！战胜它！ •如何有效地为新手解决算法问题（LeetCode）•10个VS Code插件工件，第七个超级实用！ •在拼多多工作感觉如何？我的tm心态崩溃了！ •写信给小白，从头开始拥有一个很棒的网站！

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-229630-1.html