在讲到集合的时候,很容易让人想到的是数组和链表。然后大家会讨论这两种数据结构的差异。但是根据指定的内容在集合中查找,这两种数据结构的性能却没有区别都是O(n),如何提高在集合中检索指定内容数据的性能,是我们在程序开发中面临的问题。
二叉排序树
二叉排序树的性质
- 左子树不空时,左子树上所有的结点关键字的值均小于根结点关键字的值;
- 右子树不空时,右子树上所有的结点关键字的值均大于根结点关键字的值;
- 左右子树同时有满足性质1、性质2
二叉树的查找
- 将给定的值与根结点相比较,若相等则查找成功;
- 若小于根结点到左子树进行查找,若大于根结点到右子树进行查找;
- 左右子树依次进行步骤1、步骤2操作,直到找到相等的结点或找到null(查找失败)
- 二叉树的查找与折半查找相似
二叉树的操作
插入
例,根据{45,53,45,12,24,90}来构建二叉排序树
- 从一个空树出发来构建二叉排序树,新增结点是建立在查找二叉排序树失败的前提下,因此新增的结点一定是二叉排序树的叶子结点
- 中序遍历二叉排序树即可得到一个有序的集合
删除
二叉排序树的删除规则:设,
*f为指向被删除结点的双亲结点的指针*p为指向被删除结点的指针-
若*p是叶子结点,那么就直接删除
- *p是*f的左子结点,如图所示:
- *p是*f的右子结点,如图所示:
-
若删除的*p结点只有左子树或是右子树,删除*p结点之后直接将子树挂在*f结点上即可,成为*f结点的子树
- *p是*f的左子结点,如图所示:
- *p是*f的右子结点,如图所示:
- 说明:上述只是部分情况,剩余情况最后都跟上图显示的删除*p结点之后的结点情况一致。
-
若删除的*p结点同时拥有左、右子树,删除节点有两种可行性操作:
-
若*p结点是*f的左子结点
- 第一种操作:将*p点的左子树PL直接挂载到*f结点上,成为*f结点的左子树,然后将*p结点的右子树PR挂载到中序遍历时PL子树中*p结点的直接前驱节点,成为该节点的右子树;如图所示:
-
第二种操作:使用二叉排序树的中序遍历得到的结点顺序,确定*p结点的直接前驱或直接后继结点,将该结点移到*p结点位置
-
该结点满足以下特性:
- 该结点是叶子结点或只有一个子树(若是前驱节点只有左子树;若是后继节点只有右子树)
- 该结点是*p前驱结点的话,就是该前驱结点父节点的右子结点;
- 该结点是*p后继结点的话,就是该后继结点父节点的左子结点。
-
接下来以*p结点的前驱结点进行讨论:
- 若*p结点的前驱结点是叶子结点则直接移动即可,图就略过了。
- 若*p结点的前驱结点有左子树的话,则将左子树挂载到*p结点的前驱结点的父结点上,成为*p结点的前驱结点的父结点的右子树,如图所示:
-
接下来以*p结点的后继结点进行讨论:
- 若*p结点的后继结点是叶子结点则直接移动即可,图(略)
- 若*p结点的后继结点有右子树的话,则将右子树挂载到*p结点的后继结点的父结点上,成为*p结点的后继结点的父结点的左子树,如图所示:
-
上述是在*p是*f的左孩子的前提下进行的讨论,接下来是以*p是*f的右孩子进行讨论,直接上图了
- 第一种操作:
-
第二种转换:
- 以*p结点的前驱结点进行讨论
- 以*p结点的后继结点进行讨论
-
-