C++ 二叉搜索树概念与实现

二叉搜索树基本概念

二叉搜索树（Binary Search Tree，简称 BST）是一种特殊的二叉树，满足以下性质：

1. 对于树中的每个节点，其左子树中所有节点的值都小于该节点的值。
2. 对于树中的每个节点，其右子树中所有节点的值都大于该节点的值。
3. 左右子树也分别是二叉搜索树。

这种特性使得二叉搜索树在查找、插入和删除操作上具有较高的效率，平均时间复杂度为 O(log n)。

性能分析

最优情况下，二叉搜索树为完全二叉树（或者接近完全二叉树），其高度为 log₂N；最差情况下，二叉搜索树退化为单支树（或者类似单支），其高度为 N。所以综合而言，二叉搜索树增删查改时间复杂度为 O(N)。

二分查找也可以实现 O(log₂N) 级别的查找效率，但是二分查找有两大缺陷：

1. 需要存储在支持下标随机访问的结构中，并且有序。
2. 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。

这里也就体现出了平衡二叉搜索树的价值。

实现细节

节点结构设计

节点采用模板设计，使得该结构可以存储任意类型的数据，只要该类型支持比较运算。

template<class K> struct BSTreeNode { 
    K _key; 
    BSTNode<K>* _left; 
    BSTNode<K>* _right; 
    BSTNode(const K& key) :_key(key) , _left(nullptr) , _right(nullptr) { } 
};

• _key：节点的关键字，用于比较和查找
• _left：指向左子节点的指针
• _right：指向右子节点的指针
• 构造函数：初始化节点的关键字，并将左右子节点指针置为 nullptr

类结构与核心操作

template<class K> class BSTree { 
    typedef BSTreeNode<K> Node; 
public: 
    // 构造、拷贝构造、赋值运算符、析构函数 
    BSTree() = default; 
    BSTree(const BSTree<K>& t); 
    BSTree<K>& =(BSTree<K> t); 
    ~(); 
    
    ; 
    ; 
    ; 
    
    ; 
: 
    
     _InOrder(Node* root); 
    
    ; 
    
    ; 
: 
    Node* _root = ; 
};