美文网首页
二叉搜索树

二叉搜索树

作者: 骑猪满天飞 | 来源:发表于2021-01-17 20:24 被阅读0次

    二叉搜索树

    定义

    一棵二叉搜索树需要满足以下条件：

    • 是一棵二叉树
    • 对于树中任意节点，所有左子树元素都小于该节点，所有右子树元素都大于等于该节点
    bst.png

    上图就是一棵，二叉搜索树。每个二叉搜索树的节点还包含属性left、right、parent，分别指向它的左、右孩子和父节点。

    性质

    中序遍历

    ​ 对二叉搜索树进行一次中序遍历，可以按顺序输出每个元素值。

    二叉搜索树操作

    二叉搜索树支持以下操作：

    1. search - 查找元素
    2. minimum - 查找最小元素值
    3. maximum - 查找最大元素值
    4. successor - 找指定元素的前驱元素
    5. predecessor - 找指定元素的后继元素
    6. insert - 插入元素
    7. delete - 删除元素

    查找

    查找指定元素

    由于二叉搜索树的性质，可以在O(h) (h为树的高度)时间内找到元素。

    树的节点结构和树表示如下：

    typedef int Tp;
typedef struct TNode {
    Tp data;
    TNode* parent;
    TNode* left;
    TNode* right;
}TNode;

class BinSearchTree {
private:
    typedef TNode* Root_ ;
    Root_ root_ = nullptr;

...
};

    对元素进行搜索，若目标元素大于当前元素，则搜索当前节点的右子树，否则搜索左子树：

    TNode* BinSearchTree::TreeSearch(Tp key) {
    TNode* p = root_;
    while (p) {
        if (p->data == key) {
            return p;
        }
        else if (key < p->data) {
            p = p->left;
        }
        else {
            p = p->right;
        }
    }
    return nullptr;
}

    找最小、最大值

    根据二叉搜索树的性质，最小值为最左节点。

    /**
* @brief 寻找最小节点
* 
*/
TNode* BinSearchTree::TreeMinimumHelper(Root_ t) {
    while (t->left) {
        t = t->left;
    }
    return t;
}

    同理最大值为树的最右节点

    前驱节点

    寻找目标节点的前驱节点分为两种情况：

    1. 目标节点存在左子树，前驱为：该左子树的最大值。例如 ，15的前驱为13。

    2. 目标节点不存在左子树，前驱为：第一个使得目标节点成为为右子树中元素的祖先节点.。

      例如，17的前驱为15，因为15是17的第一个祖先元素，使得17成为右子树元素。

    search.png 
    /**
* @brief 寻找指定节点的前驱节点
*/
TNode* BinSearchTree::TreePredecessorHelper(TNode* p) {
    if (p->left) {
        return TreeMaximumHelper(p->left);
    }
    TNode* pre = p->parent;
    while (pre && p == pre->left) {
        p = pre;
        pre = pre->parent;
    }
    return pre;
}

    后继节点

    后继节点的寻找，与前驱类似，为前驱的相反情况

    /**
* @brief 寻找指定节点的后继节点
*/
TNode* BinSearchTree::TreeSuccessorHelper(TNode* p) {
    if (p->right) {
        return TreeMinimumHelper(p->right);
    }
    TNode* next = p->parent;
    while (next && p == next->right) {
        p = next;
        next = next->parent;
    }
    return next;
}

    插入、删除

    插入

    插入相对删除比较简单

    步骤：

    1. 根据要插入数据的值，找到插入的位置。
    2. 插入元素
    void BinSearchTree::TreeInsert(Tp key) {
        TNode* node = new TNode;
    node->data = key;
    node->parent = nullptr;
    node->left = nullptr;
    node->right = nullptr;

    TNode* pre = nullptr;
    TNode* cur = root_;

    
    while (cur) {
        /// 找到插入位置，与该位置的父节点
        pre = cur;
        if (key < cur->data) {
            cur = cur->left;
        }
        else {
            cur = cur->right;
        }
    }

    node->parent = pre;

    /// 插入元素
    if (!pre) {
        root_ = node;
    }
    else if (key < pre->data) {
        pre->left = node;
    }
    else {
        pre->right = node;
    }
}

    删除

    删除分为3中情况

    1. 目标节点，左孩子为空

      这时候用右孩子节点r，替换目标节点z

    delete1.png

    1. 目标节点，右孩子为空

      ​ 这时候用左孩子节点l，替换目标节点z

    delete2.png

    1. 目标节点，左右孩子都存在

      这时需要用目标节点的后继节点y，替换目标节点z。

      该后继节点y = minimum(target->right)，所以没有左孩子。

      1. 当y的父节点，是z时：
      delete31.png 
      ​ 直接用`y`替换目标节点`z`即可
    1. 当y的父节点，不是z时：
    delete32.png 
      1）需要先将`x`替换`y`，设置`y`的右孩子设为`r`，`r`的父节点为`y`

  2）用`y`替换`z`

    代码实现：

    1. 替换函数：
    /**
* @brief 子树替换，用于辅助节点删除
* @param target 被替换子树的根节点
* @param source 源子树
*/
void BinSearchTree::Transplant(TNode* target, TNode* source) {
    if (!target->parent) {
        root_ = source;
    }
    else if (target->parent->left == target) {
        target->parent->left = source;
    }
    else {
        target->parent->right = source;
    }

    if (source) {
        source->parent = target->parent;
    }
}
    1. 删除节点操作
    /**
* @brief 删除指定数据
*
*/
void BinSearchTree::TreeDelete(Tp key) {
    TNode* p = TreeSearch(key);
    if (p) {
        if (!p->left) {
            Transplant(p, p->right);
        }
        else if (!p->right) {
            Transplant(p, p->left);
        }
        else {
            TNode* next = TreeMinimumHelper(p->right);  /// 找到p节点的后继节点
            if (next->parent != p) {
                Transplant(next, next->right);
                next->right = p->right;
                p->right->parent = next;
            }
            Transplant(p, next);
            next->left = p->left;
            next->left->parent = next;
        }
        delete p;

    }
    else {
        std::cout << key << " is not in the tree!" << std::endl;
    }
}

    完整代码

    /**
* @file         bst.h
* @author       tanghf
* @date         2021-01-17
* @version      V1.0
* @copyright    Copyright (c) 2021
*
*/
#ifndef BST_H_
#include <vector>

typedef int Tp;
typedef struct TNode {
    Tp data;
    TNode* parent;
    TNode* left;
    TNode* right;
}TNode;

/**
* @brief 二叉搜索树
* 
*/
class BinSearchTree {
private:
    
    typedef TNode* Root_ ;
    Root_ root_ = nullptr;

private:
    enum { kNInfinity = -65535};
    void TreeVistHelper(TNode* p);
    void Transplant(TNode* target, TNode* source);
    TNode* TreeMinimumHelper(Root_ t);
    TNode* TreeMaximumHelper(Root_ t);
    TNode* TreeSuccessorHelper(TNode* p);
    TNode* TreePredecessorHelper(TNode* p);
    
public:
    BinSearchTree(){}
    BinSearchTree(std::vector<Tp> tree);
    ~BinSearchTree();
    void TreeVist();
    TNode* TreeSearch(Tp key);
    void TreeInsert(Tp key);    
    void TreeDelete(Tp key);    
    Tp TreeMinimum() { 
        if (!root_) 
            return kNInfinity;
        return TreeMinimumHelper(root_)->data;
    }
    Tp TreeMaximum(){ 
        if (!root_)
            return kNInfinity;
        return TreeMaximumHelper(root_)->data; 
    }
    Tp TreeSuccessor(Tp key);
    Tp TreePredecessor(Tp key);
};

#endif // !BST_H_

    #include <iostream>
#include "bst.h"


/*
* @brief 将数组转化为二叉搜索树
* 
*/
BinSearchTree::BinSearchTree(std::vector<Tp> tree) {
    for (const auto& key : tree) {
        TreeInsert(key);
    }
}

BinSearchTree::~BinSearchTree() {
    while (root_) {
        TreeDelete(root_->data);
    }
}

/**
* @brief 按顺序遍历搜索树
*
*/
void BinSearchTree::TreeVist() {
    TreeVistHelper(root_);
    std::cout << std::endl;
}

/**
* @brief 在树中搜索目标值
* @return 若存在返回值为目标值的节点的，否则范围空指针
*/
TNode* BinSearchTree::TreeSearch(Tp key) {
    TNode* p = root_;
    while (p) {
        if (p->data == key) {
            return p;
        }
        else if (key < p->data) {
            p = p->left;
        }
        else {
            p = p->right;
        }
    }
    return nullptr;
}



/**
* @brief 在搜索树中插入元素
* 
*/
void BinSearchTree::TreeInsert(Tp key) {
    TNode* node = new TNode;
    node->data = key;
    node->parent = nullptr;
    node->left = nullptr;
    node->right = nullptr;

    TNode* pre = nullptr;
    TNode* cur = root_;

    
    while (cur) {
        /// 找到插入位置，与该位置的父节点
        pre = cur;
        if (key < cur->data) {
            cur = cur->left;
        }
        else {
            cur = cur->right;
        }
    }

    node->parent = pre;

    /// 插入元素
    if (!pre) {
        root_ = node;
    }
    else if (key < pre->data) {
        pre->left = node;
    }
    else {
        pre->right = node;
    }
}



/**
* @brief 删除指定数据
*
*/
void BinSearchTree::TreeDelete(Tp key) {
    TNode* p = TreeSearch(key);
    if (p) {
        if (!p->left) {
            Transplant(p, p->right);
        }
        else if (!p->right) {
            Transplant(p, p->left);
        }
        else {
            TNode* next = TreeMinimumHelper(p->right);  /// 找到p节点的后继节点
            if (next->parent != p) {
                Transplant(next, next->right);
                next->right = p->right;
                p->right->parent = next;
            }
            Transplant(p, next);
            next->left = p->left;
            next->left->parent = next;
        }
        delete p;

    }
    else {
        std::cout << key << " is not in the tree!" << std::endl;
    }
}


/**
* @brief 寻找目标值的下一个元素
*
*/
Tp BinSearchTree::TreeSuccessor(Tp key) {
    TNode*  p = TreeSearch(key);
    if (p) {
        TNode* next = TreeSuccessorHelper(p);
        if (next) {
            return next->data;
        }
        else {
            return kNInfinity;
        }
        
    }
    else {
        return kNInfinity;
    }
}

/**
* @brief 寻找目标值的前一个元素
*
*/
Tp BinSearchTree::TreePredecessor(Tp key) {
    TNode* p = TreeSearch(key);
    if (p) {
        TNode* next = TreePredecessorHelper(p);
        if (next) {
            return next->data;
        }
        else {
            return kNInfinity;
        }

    }
    else {
        return kNInfinity;
    }
}



/***********************辅助函数******************/
/**
* @brief 寻找最小节点
* 
*/
TNode* BinSearchTree::TreeMinimumHelper(Root_ t) {
    while (t->left) {
        t = t->left;
    }
    return t;
}

/**
* @brief 寻找最大节点
*
*/
TNode* BinSearchTree::TreeMaximumHelper(Root_ t) {
    while (t->right) {
        t = t->right;
    }
    return t;
}

/**
* @brief 中序遍历
*
*/
void BinSearchTree::TreeVistHelper(TNode* p) {
    if (p) {
        TreeVistHelper(p->left);
        std::cout << p->data << " ";
        TreeVistHelper(p->right);
    }
}

/**
* @brief 子树替换，用于辅助节点删除
* @param target 被替换子树的根节点
* @param source 源子树
*/
void BinSearchTree::Transplant(TNode* target, TNode* source) {
    if (!target->parent) {
        root_ = source;
    }
    else if (target->parent->left == target) {
        target->parent->left = source;
    }
    else {
        target->parent->right = source;
    }

    if (source) {
        source->parent = target->parent;
    }
}

/**
* @brief 寻找指定节点的后继节点
*/
TNode* BinSearchTree::TreeSuccessorHelper(TNode* p) {
    if (p->right) {
        return TreeMinimumHelper(p->right);
    }
    TNode* next = p->parent;
    while (next && p == next->right) {
        p = next;
        next = next->parent;
    }
    return next;
}


/**
* @brief 寻找指定节点的前驱节点
*/
TNode* BinSearchTree::TreePredecessorHelper(TNode* p) {
    if (p->left) {
        return TreeMaximumHelper(p->left);
    }
    TNode* pre = p->parent;
    while (pre && p == pre->left) {
        p = pre;
        pre = pre->parent;
    }
    return pre;
}

    相关文章

      网友评论

          本文标题：二叉搜索树

          本文链接：https://www.haomeiwen.com/subject/ekjzaktx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|二叉搜索树|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！