首页
学习
活动
专区
工具
TVP
发布

4.5.1 二叉排序树

1、二叉排序树的定义 左子树结点值<根结点值<右子树结点值 2、二叉排序树的查找 二叉排序树的查找时从根结点开始,沿着某一分支逐层向下进行比较比较的过程。...构造一棵二叉排序树就是依次输入数据元素,并将它们插入二叉排序树中的适当位置上的过程。...,必须先把被删除结点从存储二叉排序树的链表上摘下来,将因删除结点而断开的二叉链表重新链接起来,同时确保二叉排序树的性子不会丢失。...6、二叉排序树的查找效率分析 对于高度为H的二叉树,其插入和删除操作的运行时间都是O(H),但在最坏的情况下,即构造二叉排序树的输入序列是有序的,则会形成一个倾斜的单支树,此时二叉排序树的性能显著变坏,...从查找过程看,二叉排序树与二分查找相似。就平均时间性能而言,二叉排序树的上的查找和二叉查找差不多。但二分查找的判定树唯一,二叉排序树不唯一,相同的关键字其插入顺序不同可能生成不同的二叉排序树

48230
您找到你想要的搜索结果了吗?
是的
没有找到

二叉排序树

之前说二叉树时,说到树这种结构就是就是为了弥补数组和链表的缺点而诞生的,二叉排序树(Binary search tree,简称BST),更是体现了这一点。...二叉排序树有以下特点: 左子节点的值比父节点小; 右子节点的值比父节点大; 2....构建过程: 假如现有数列:7,3,10,12,5,1,9,构建二叉排序树的过程如下: 7当成父节点,3比7小,放到7的左边; 10比7大,放到7的右边; 12比7大,比10也大,放到10的右边; 5比7...小,比3大,放到3的右边; 1比7小,比3小,放到3的左边; 9比7大,比10小,放到10的左边; 二叉排序树 3....二叉排序树的删除: 二叉排序树的删除有三种情况,如下: (1):删除的是叶子节点:比如上面这棵二叉排序树中的1,5,9,12: 首先找到这个节点targetNode,如果不存在,直接删除失败; 然后找到

23620

查找——树表——>二叉排序树

树表 表结构在查找过程中动态生成 对于给定值key 若表中存在,则成功返回; 否则插入关键字等于key 的记录 二叉排序树 二叉排序树或是空树,或是满足如下性质的二叉树: - 若其左子树非空,则左子树上所有结点的值均小于根结点的值...; - 若其右子树非空,则右子树上所有结点的值均大于等于根结点的值; - 其左右子树本身又各是一棵二叉排序树 [在这里插入图片描述][在这里插入图片描述]>中序遍历二叉排序树后**得到一个关键字的递增有序序列...** --- 二叉排序树的操作-查找 若查找的关键字等于根结点,成功 否则 - 若小于根结点,查其左子树 - 若大于根结点,查其右子树 在左右子树上的操作类似 算法思想 - 若二叉排序树为空...插入的元素一定在叶结点上 [在这里插入图片描述] --- 二叉排序树的操作-生成 从空树出发,经过一系列的查找、插入操作之后,可生成一棵二叉排序树 不同插入次序的序列生成不同形态的二叉排序树 [在这里插入图片描述...] --- 二叉排序树的操作-删除 将因删除结点而断开的二叉链表重新链接起来 防止重新链接后树的高度增加 [在这里插入图片描述] 删除叶结点,只需将其双亲结点指向它的指针清零,再释放它即可。

41285

二叉排序树代码实现(java版)

1、一棵空树,或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树...rightNode; private int value; public Node(int value) { this.value = value; } } 2、定义一个二叉排序树类...for (int i : arr) { tree.addNode(new Node(i)); } } } 三、插入节点 1、实现思路: 在二叉排序树中肯定需要一个...需要按照二叉排序树的性质从其左子树或者有子树中选择节点补到待删除节点的位置。...//查找某个节点 Node search = tree.search(9); //删除某个节点 tree.delete(3); } 八、总结 以上就是对于二叉排序树

22110

数据结构 二叉排序树

定义 二叉排序树要么是空二叉树,要么具有如下特点: 二叉排序树中,如果其根结点有左子树,那么左子树上所有结点的值都小于根结点的值; 二叉排序树中,如果其根结点有右子树,那么右子树上所有结点的值都大小根结点的值...; 二叉排序树的左右子树也要求都是二叉排序树; 例如,下图就是一个二叉排序树: image.png 二叉排序树关键字的操作 使用二叉排序树查找关键字 二叉排序树中查找某关键字时,查找过程类似于次优二叉树...删除关键字 在查找过程中,如果在使用二叉排序树表示的动态查找表中删除某个数据元素时,需要在成功删除该结点的同时,依旧使这棵树为二叉排序树。...(T); } 运行结果: 中序遍历二叉排序树: 2 3 4 5 9 删除3后,中序遍历二叉排序树: 2 4 5 9 总结 使用二叉排序树在查找表中做查找操作的时间复杂度同建立的二叉树本身的结构有关...例如:查找表 {45,24,53,12,37,93} 和表 {12,24,37,45,53,93} 各自构建的二叉排序树图下图所示: image.png 使用二叉排序树实现动态查找操作的过程,实际上就是从二叉排序树的根结点到查找元素结点的过程

50610

详解数据结构——二叉排序树

目录 二叉排序树 二叉排序树的查找 二叉排序树的插入 二叉排序树的删除 查找时间效率分析 ---- 二叉排序树 二叉排序树,又称二叉查找树(BST,Binary Search Tree...左子树和右子树又各是一棵二叉排序树 左子树结点值<根结点值<右子树结点值 进行中序遍历可以得到一个递增的有序序列 二叉排序树的查找 若树非空,目标值与根结点的值比较: 若相等,则查找成功; 若小于根结点...若原二叉排序树为空,则直接插入结点;否则, 若关键字k小于根结点值,则插入到左子树, 若关键字k大于根结点值,则插入到右子树 代码 最坏时间复杂度O(h) ,树的高度 //在二叉排序树插入关键字为...; while (i < n){ //依次将每个关键字插入到二叉排序树中 BST_Insert(T,str[i]); i++; } } 二叉排序树的删除 先搜索找到目标结点...: 1、若被删除结点z是叶结点,则直接删除,不会破坏二叉排序树的性质。

44340
领券