一、二叉搜索树概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
- 现阶段二叉搜索树没有重复的数据
二、二叉搜索树的创建
2.1 二叉搜索树的基本单位
template<class K> struct BSTreeNode { BSTreeNode(const K& key = K()) :_left(nullptr) , _right(nullptr) , _key(key) {} BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; };
2.2 实现二叉搜索树的基本框架
template<class K> class BSTree { public: //类型名字太长，不方便 typedef BSTreeNode<K> Node; private: Node* _root = nullptr; };
上面图示以物理结构数组int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13}创建出来的逻辑结构二叉搜索树的数据结构。
2.3 二叉搜索树的查找
二叉搜索树查找步骤:
- 规定一个关键值key
- 从根开始开始比较查找，key比根大则往右边走查找，key比根小则往左边走查找
- 最多查找高度次，走到到空，还没有找到，这值不存在
- 在插入接口中，虽然查找合适位置代码逻辑差不多，但是存在个别逻辑差异，注意识别
bool Find(const K& key) { Node* cur = _root->_key; while (cur) { if (key < cur->_key) { cur = cur->_left; } else if(key > cur->_key) { cur = cur->_right; } else { return true; } } return false; }
2.4 二叉搜索树的插入
插入具体过程:
- 树为空，则直接新增节点，赋值给root指针
- 树不为空，按二叉搜索树性质插入位置，插入新节点
bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* parent = nullptr; //这里cur是临时变量 Node* cur = _root; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(key); if (parent->_key < key) { parent->_right = cur; } else if (parent->_key > key) { parent->_left = cur; } return true; }
插入具体过程细节处理:
- 需要判断树是否为空树，如果为空，创建节点赋值给_root
- 创建两个指针parent和cur保证节点的连接
- 通过不同比较大小，直到cur找到为空的位置，创建节点
- 该节点需要满足二叉搜索树的特性，需要再次判断，选择连接
2.5 二叉搜索树的删除(难点)
2.5.1 删除该子树根节点情况分析
首先查找元素是否在二叉搜索树中，如果不存在则返回false，否则要删除的节点可能分为下面三种情况。先到需要被删除的节点，这里就不重复实现了。
删除节点情况划分：
- 要删除的节点无孩子节点
- 要删除的节点只有一个孩子节点
- 要删除的节点有左、右孩子节点
2.5.2 删除第一、二情况节点
这里第一种和第一种情况可以归类为同一种情况。无论被删除节点是否有无真实存在的孩子节点，都可以看成要删除的节点只有一个孩子节点，将第一种情况看成第二种情况，被删除节点有空孩子节点。
if (cur->_left == nullptr) { if (parent->_left == cur) { parent->_left = cur->_right; } else if (parent->_right == cur) { parent->_right = cur->_right; } delete cur; } else if (cur->_right == nullptr) { if (parent->_left == cur) { parent->_right = cur->_left; } else if (parent->_right == cur) { parent->_left = cur->_left; } delete cur; }
关于数据结构学习，我们需要借助具体的逻辑结构去实现"抽象"的物理结构。接下我也希望你们可以借助图和文字进行对代码的解读。
- 第一个判断分支决定，parent指向另外一个可能为空的节点。
- 第二个分支判断被删除节点相对parent节点的位置
判断结束后，parent节点进行连接操作进行删除操作。
- 小总结：判断被删除节点位置与被删除节点可能不为空孩子位置，进行连接即可。
草稿说明，上面是优化版本说明:
有了上面两个信息的话，比如通过
parent->_left == cur需要被删除的节点是左节点，并且cur->_left == nullptr该节点左孩子节点为空，那么parent->_left = cur->_right;。parent->_left是根据第一个条件，该parent->_left需要重新连接新节点，那么新节点是谁？通过cur->_left == nullptr判断，该左孩子为空，肯定连接右孩子节点。
【高阶数据结构】深度探索二叉树进阶：二叉搜索树概念及其高效实现（二）https://developer.aliyun.com/article/1617405
