C++ 二叉搜索树原理与实现

何为二叉搜索树

二叉搜索 (排序) 树具有如下特征：

若它的左子树不为空，则**左子树上所有结点的值都小于等于根结点的值；若它的右⼦树不为空，则右子树上所有结点的值都大于等于根结点的值；它的左右⼦树也分别为二叉搜索树；二叉搜索树的中序遍历是有序的；**了解二叉搜索树是为了之后为 map/set/multimap/multiset 的关联式容器打下基础。特别地，二叉搜索树分为冗余和不冗余版本。(冗余即有相等值也可插入)

在冗余版本的二叉搜索树中，会出现如下两种情况，那这两都是正确的吗？

是的，并不影响搜索二叉树的性质。

性能分析

可以发现在该二叉搜索树较为平衡的情况下，即在最优情况下，找到指定结点的情况下，只需要访问高度 k 次，即高度为：log₂N；但在最差情况下，高度会达到 N。（在红黑树章节会有详解如何平衡高度差）

综合来讲，二叉搜索树增删查改时间复杂度为：O(N)。

二分查找也能达到 log₂N 级别的查找效率，为何不使用二分查找呢？二分查找有以下缺陷：**需要存储在支持下标随机访问的结构中，并且有序。插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。**二叉搜索树在最差情况下能达到 O(N) 级别，那它能起到什么作用呢？二叉搜索树的引入是为了后续为平衡二叉树 AVL 树和红⿊树作铺垫，之后引入了旋转的概念，能够好维持二叉树的结构。

搜索树的结构

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

插入和查找 (非冗余版本)

插入时分为以下情况：

1. 树为空时，申请一个新结点赋值给根结点_root;
2. 树不为空时，插⼊值⽐当前结点⼤往右⾛，插⼊值⽐当前结点⼩往左⾛，找到空位置，插⼊新结点。(如若支持冗余，则可往左走，也可往右走，确保逻辑一致性)

{ 
    
     (_root == ) { 
        _root =  (key); 
         ; 
    } 
    Node* parent = ; 
    Node* cur = _root; 
    
     (cur) { 
         (cur->_key < key) { 
            parent = cur; 
            cur = cur->_right; 
        }   (cur->_key > key) { 
            parent = cur; 
            cur = cur->_left; 
        }  { 
             ; 
        } 
    } 
    cur =  (key); 
     (parent->_key > key) { 
        parent->_left = cur; 
    }  { 
        parent->_right = cur; 
    } 
     ; 
}