二叉搜索树 BSTtype
status
date
slug
summary
tags
category
icon
password
Property
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
- 若它的左子树不为空，则左子树上所有节点的值都 小于「根节点的值」
- 若它的右子树不为空，则右子树上所有节点的值都 大于「根节点的值」
- 它的所有子树也都是二叉搜索树
所有，二叉搜索树的特点是每一个节点都满足：左孩子的值 < 父节点的值 < 右孩子的值
二叉搜索树的实现
节点类和树类
定义二叉搜索树节点类模板：
定义二叉搜索树类模板：
构造函数
拷贝构造函数
赋值运算符重载
析构函数
查找
二叉搜索树的查找(非递归)
- 如果根节点为空，返回
nullptr
- 如果根节点不为空，从根节点开始，查找
key： - 如果
key比当前节点小，则去当前节点的左子树中查找 - 如果
key比当前节点大，则去当前节点的右子树中查找 - 如果
key等于当前节点，返回节点地址
二叉搜索树的查找(递归)
分而治之的思想：每一级递归时，在我们眼中，当前树只有
root、left、right 三个节点。
插入
二叉搜索树的插入(非递归)
- 树为空，直接插入
- 树不为空，根据「二叉搜索树性质」，从根节点开始，查找到适合插入 key 的空位置，然后插入。
插入元素的顺序不同，树的结构也会不同，但中序遍历的结果是一样的：
二叉搜索树的插入(递归)
- 如果当前树的根节点为空，则直接插入
- 如果当前树的根节点不为空：
- 插入的值
key如果比当前树的根节点大，则去往当前树的右子树中插入 - 插入的值
key如果比当前树的根节点小，则去往当前树的左子树中插入
中序遍历
删除
二叉搜索树的删除（非递归）
首先查找元素
key是否在二叉搜索树中，如果不存在，则返回false，否则删除结点，分下面几种情况：- 要删除的结点「无孩子」结点（叶子节点），或者要删除的结点「只有左孩子」结点
先判断被删除节点cur是父节点parent的左孩子还是右孩子，让父结点
parent的左 / 右指针指向被删除节点的左孩子，然后删除该节点如果删除的是根节点，
cur没有父节点，直接把cur的左孩子变为根
- 要删除的结点「只有右孩子」结点
先判断被删除节点
cur是父节点parent的左孩子还是右孩子，让父结点parent的左 / 右指针指向被删除节点的右孩子，然后删除该节点如果删除的是根节点，
cur没有父节点，直接把cur的右孩子变为根：
- 要删除的结点「有左右孩子」结点
- 左子树中的最大节点 --> 即左子树的最右侧节点（它的右孩子一定为空）
- 右子树中的最小节点 --> 即右子树的最左侧节点（它的左孩子一定为空）
有两个孩子，不好直接删除，所以用替代法删除：找一个替代节点，比被删除节点的左孩子值大，比被删除节点右孩子的值小。即被删除节点左子树中的最大节点或者右子树中的最小节点。
替代节点找到后，将替代节点中的值赋给「要的删除节点」，转换成删除替代节点。
二叉搜索树的删除（递归）
二叉搜索树的应用
K的模型–set
K (Key) 模型：确定一个值在不在一个集合中，K模型即只有Key作为关键码，二叉搜索树结构中只需要存储Key即可，关键码即为需要搜索到的值。
KV的查找模型–map
KV (Key/Value) 模型：每一个关键码Key，都有与之对应的值Value，即
<Key,Value>的键值对。KV模型中，二叉搜索树的每个节点不仅要存放key，还要存放value，但是在插入、删除的时候，还是按照 key 值来查找到该节点，对其进行插入、删除操作。
二叉搜索树的性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是与树的深度有关，即树越深，则比较次数越多。但对于同一个关键码集合，如果各关键码插入的顺序不同，可能得到不同结构的二叉搜索树：
二叉搜索树的查找是很快的，但是它很依赖于树的形状：
最优情况下，有n个结点的二叉搜索树为完全二叉树，其平均比较次数为：
最差情况下，有n个结点的二叉搜索树退化为单支树，其平均比较次数为：