计算机知识二叉排序树（BST）思维导图
简单介绍二叉排序树（BST）的内容
树图思维导图提供 计算机知识二叉排序树（BST）思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 计算机知识二叉排序树（BST）思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：ff8d892038bd27b6bfe6eaaf9b883b95
思维导图大纲
二叉排序树（BST）思维导图模板大纲
定义
二叉排序树也称二叉查找树、有以下特征的非空二叉树
特征
左子树非空、左子树上所有结点的关键字都小于根结点关键字
右子树非空、右子树上所有结点的关键字都大于根结点关键字
左右子树本身也是一棵二叉排序树
查找
从根结点开始、沿某个分支逐层向下比较的过程
给定值与根结点比较、相等则查找成功、小于根结点则在左子树找、大于则在右子树找、（递归查找的过程）
插入
若为空树、直接插入结点
若小于根结点关键字、插入左子树、若大于根结点关键字、插入右子树
删除
被删除结点右子树为空、用左子女来填补
被删除结点左子树为空、用右子女来填补
被删除结点左右子树均不为空、在右子树找一个中序遍历第一个子女来填补
效率
高度为h的二叉排序树、插入和删除操作运行时间都是O(h)
最坏情况就是构造二叉排序树时的输入序列有序、会形成单支树
平均查找长度取决于树的高度
若二叉排序树左右子树高度之差绝对值不超过1，则变成平衡二叉树、平均查找长度O(log2 n)
平均性能二叉排序树与二分查找树差不多、但二分查找树查找唯一，二叉排序树查找不唯一
适用情况
有序表为静态查找表时（即只有查找操作），宜用顺序表为其存储结构、采用二分查找实现查找操作
有序表为动态查找表时（即有插入删除操作），宜使用二叉排序树为其逻辑结构
概括思维导图模板大纲
相关思维导图模板
树图思维导图提供 计算机辅助电子线路设计 在线思维导图免费制作，点击“编辑”按钮，可对 计算机辅助电子线路设计 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：6ca7534122e478b7cd1b28b3c72601e8
树图思维导图提供 计算机网络应用层 在线思维导图免费制作，点击“编辑”按钮，可对 计算机网络应用层 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：1d7a27cc460774320c29f068a3a669b8
沪公网安备 31011502019485号
上海工商