二叉搜索树(BST, Binary Search Tree)又称二叉排序树或二叉查找树,它或者是一棵空树,或者具有以下性质的二叉树:
int a [] = { 8 , 3 , 1 , 10 , 6 , 4 , 7 , 14 , 13 };
1. 二叉搜索树的查找
2. 二叉搜索树的插入
插入具体过程:
3. 二叉搜索树的删除
首先查找元素是否在二叉搜索树中,如果不存在,则返回,否则要删除的节点可能分以下四种情况:
看起来有4种情况,实际情况1可以与情况2或者3合并起来,因此真正的删除过程如下:
1. K模型:K模型即只有Key作为关键码,结构中只需要存储Key即可,关键码即为需要搜索到的值。
比如:给一个单词word,判断该单词是否拼写正确,具体方式如下:
2. KV模型:每一个关键码Key,都有与之对应的值Value,即<Key,Value>的键值对。该种方式在现实生活中非常常见:
插入和删除操作都必须先查找,查找效率代表了二叉搜索树中各个操作的性能。
对有n个节点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是节点在二叉搜索树的深度的函数,即节点越深,比较次数越多。
但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树:
最优情况下,二叉搜索树为完全二叉树(或者接近完全二叉树)。
最差情况下,二叉搜索树退化为单支树(或者类似单支树)。
感谢各位大佬支持!!!
互三啦!!!