上海产品网站建设,下载商城,网站编辑制作,做360网站优化Binary Search Tree 二叉搜索树的概念二叉搜索树的操作二叉搜索树的实现查找插入删除 二叉搜索树的应用二叉搜索树的性能分析 二叉搜索树的概念
二叉搜索树又被称为二叉排序树#xff0c;顾名思义#xff0c;当我们使用中序遍历时#xff0c;会得到一个有序的序列。二叉搜索… Binary Search Tree 二叉搜索树的概念二叉搜索树的操作二叉搜索树的实现查找插入删除 二叉搜索树的应用二叉搜索树的性能分析 二叉搜索树的概念
二叉搜索树又被称为二叉排序树顾名思义当我们使用中序遍历时会得到一个有序的序列。二叉搜索树有如下的性质 1.若它的左子树不为空则左子树上每个节点的值都小于根节点的值。 2.若它的右子树不为空则右子树上每个节点的值都大于根节点的值。 3.左右子树也是二叉搜索树 如图所示就是一颗二叉搜索树。它的中序遍历结果为134678101314
二叉搜索树的操作
二叉搜索树的操作有查找插入删除。 查找 1.从根开始比较查找比根大则往右边走查找比根小则往左边走查找 2.最多查找高度次走到到空还没找到这个值不存在
插入 分为树是否为空 若为空树树为空则直接新增节点赋值给root指针 若不为空树按二叉搜索树性质查找插入位置插入新节点
删除
首先要查找要删除的节点是否在二叉树中若不存在则直接返回若存在分情况进行删除。 a.要删除的节点没有孩子 b.要删除的节点只有左孩子 c.要删除的节点只有右孩子 d.要删除的节点左右孩子都有 实际上对于删除操作来说可以要删除没有孩子节点或删除只有一个孩子节点的情况操作是相同的都是直接将要删除的节点的双亲节点的指针指向当前删除节点的孩子节点。当前节点如果没有孩子节点实际上当前节点的孩子节点是nullptr当前节点有孩子节点实际上也是将双亲指向当前的孩子节点 因此可以将四种情况中a和b情况进行合并那么就只有三种情况了。 a.要删除的节点没有孩子或者只有右孩子-------将双亲节点指向当前节点的右孩子然后直接删除当前节点 b.要删除的节点只有左孩子-------将双亲节点指向当前节点的左孩子然后直接删除当前节点 c.要删除的节点左右孩子都有------在它的右子树下找到最小的一个节点右子树的最左侧用它的值填补到被删除节点中再处理该节点的删除问题
二叉搜索树的实现
查找
1.从根开始比较查找比根大则往右边走查找比根小则往左边走查找 2.最多查找高度次走到到空还没找到这个值不存在
Node* Find(const T data){Node* cur _root;while (cur){if (data cur-_data){cur cur-_right;}else if (data cur-_data){cur cur-_left;}elsereturn cur;}return nullptr;}插入
分为树是否为空 若为空树树为空则直接新增节点赋值给root指针 若不为空树按二叉搜索树性质查找插入位置插入新节点
bool Insert(const T data){//空树插入成功后就是根节点if (_root nullptr){_root new Node(data);return true;}//非空就需要找到待插入的位置。Node* cur _root;Node* parent nullptr;while (cur){parent cur;if (cur-_data data)cur cur-_left;else if (cur-_data data)cur cur-_right;elsereturn false;} cur new Node(data);if (cur-_data parent-_data){parent-_right cur;}elseparent-_left cur;return true;}删除
首先要查找要删除的节点是否在二叉树中若不存在则直接返回若存在分情况进行删除。 a.要删除的节点没有孩子 b.要删除的节点只有左孩子 c.要删除的节点只有右孩子 d.要删除的节点左右孩子都有 实际上对于删除操作来说可以要删除没有孩子节点或删除只有一个孩子节点的情况操作是相同的都是直接将要删除的节点的双亲节点的指针指向当前删除节点的孩子节点。当前节点如果没有孩子节点实际上当前节点的孩子节点是nullptr当前节点有孩子节点实际上也是将双亲指向当前的孩子节点 因此可以将四种情况中a和b情况进行合并那么就只有三种情况了。 a.要删除的节点没有孩子或者只有右孩子-------将双亲节点指向当前节点的右孩子然后直接删除当前节点 b.要删除的节点只有左孩子-------将双亲节点指向当前节点的左孩子然后直接删除当前节点 c.要删除的节点左右孩子都有------在它的右子树下找到最小的一个节点右子树的最左侧用它的值填补到被删除节点中再处理该节点的删除问题
最终我们可以将情况分为上述的a b c三种情况 对于情况a来说其内部又可以分为两大类要删除的是根节点要删除的不是根节点 对于情况b来说其内部又可以分为两大类要删除的是根节点要删除的不是根节点 对于情况c来说我们是通过步骤1.在待删除节点的右子树中找到最小的节点替代节点 2.将替代节点的值赋给待删除的节点 3.删除找到的替代节点. 而在a情况中针对要删除的节点不是根节点我们需要判断待删除的节点是其双亲节点的左孩子还是右孩子。因为到时候需要让双亲节点指向待删除节点的左孩子 而在b情况中针对要删除的节点不是根节点我们需要判断待删除的节点是其双亲节点的左孩子还是右孩子。因为到时候需要让双亲节点指向待删除节点的右孩子 而在c情况中我们需要判断替代节点的是其双亲的左孩子还是右孩子。因为到时候需要让双亲节点指向待删除节点的右孩子 下图是上述分类情况的图示。 只有右孩子的场景 只有左孩子的场景 左右孩子均存在的场景 这个是对于删除操作需要分的情况 针对上述分的情况代码的实现
bool Erase(const T data){//找待删除节点的位置并且保存双亲Node* cur _root;Node* parent nullptr;while (cur){parent cur ;if (data cur-_data)break;else if (data cur-_data){parent cur;cur cur-_left;}else{parent cur;cur cur-_right;}}//值在BST中不存在值为data的节点if (cur nullptr)return false;// 只有右孩子或者没有孩子if (cur-_left nullptr){// 1.双亲为空,说明为根节点if (parent nullptr)_root cur-_right;// 2.双亲非空,说明不是根节点else{//可能是双亲的左孩子if (cur parent-_left)parent-_left cur-_right;//也可能是双亲的右孩子elseparent-_right cur-_right;}delete cur;}//只有左孩子else if (cur-_right nullptr){// 1.双亲为空是根节点if (parent nullptr)_root cur-_left;// 2.双亲不为空不是根节点else{if (cur parent-_left)parent-_left cur-_left;elseparent-_right cur-_left;}delete cur;}//左右孩子均存在,//先在其右子树中找到最左边的节点//将替代节点中的值赋给要删除的节点//删除替代节点else{Node* tmp cur-_right;parent cur;//在cur的右子树中找替代节点while (tmp-_left){parent tmp;tmp tmp-_left;}//用替代节点中的值替换待删除的节点cur-_data tmp-_data;//删除替代节点if (parent-_left tmp)parent-_left tmp-_right;elseparent-_right tmp-_right;delete tmp;}return true;二叉搜索树的应用
k模型和kv模型 k模型是指只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。 例如要查找一个单词是否拼写正确我们可以先将所有的单词作为key构建一个二叉搜索树。在这个二叉搜索树中去查找是否有我们想找到的单词若可以找到则证明拼写正确若找不到则证明拼写错误。 kv模型是指每一个关键码key都有与之对应的值Value即Key, Value的键值对。 例如英汉词典是一个典型的kv模型通过英文可以快速找到与其对应的中文。英文和中文就构成了一对键值对 二叉搜索树的性能分析
因为对应二叉搜索树来说插入和删除操作都要先进行查找查找的效率高低直接决定了各个操作的性能。
对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。
但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 如果关键码集合插入的次序接近于无序则会构造出作图这样的二叉搜索树而插入的次序如果是有序的则会构造出右图这样的单支树。
而不同的二叉搜索树其比较的平均次数是不同的。 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为O(logN)以2为底 最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为O(N)以2为底
正是由于插入的次序不同会导致构造的二叉搜索树的结构不同而退化成单枝时二叉搜索树就失去了优势因此如果需要按照任意次序插入时都能让二叉搜索树的性能达到最优就需要用到AVL树和红黑树了。
