网站空间名,钢铁网站哪家做的好,教育网站前置审批,我的世界做封面网站4.二叉搜索树
又叫二叉查找树、有序二叉树、排序二叉树。树中任意一个结点#xff0c;其左子树的每个节点值都要小于该节点#xff0c;其右子树的每个节点值都要大于该节点 作用#xff1a;能够进行快速查找、插入、删除操作
4.1 二叉搜索树的时间复杂度
注#xff1a;二…4.二叉搜索树
又叫二叉查找树、有序二叉树、排序二叉树。树中任意一个结点其左子树的每个节点值都要小于该节点其右子树的每个节点值都要大于该节点 作用能够进行快速查找、插入、删除操作
4.1 二叉搜索树的时间复杂度
注二叉搜索树的形态各异故时间复杂度也不尽相同
这里重点分析查找的时间复杂度因为不管删除、插入操作都要先进行查找目标。
4.1.1 查找时间复杂度
4.1.1.1 一般情况
分析查找目标节点都要先从根节点开始找 eg这里我们查找下图 值为5的节点根据二叉搜索树的特点首先我们要从结点开始由于5比10小走左边到6的位置由于5比6小继续走左边到4的位置而5比4大故走右边这里就找到5了这里一共进行了3次对比找到了5。其他节点的查找方法也是这样。 下图2的几次方代表每层的最大节点数量而这个次方就代表对比的次数 故从上面得到查找的时间复杂度为O(logn),由于上面说过进行插入、删除操作都要进行查找操作故它们两的时间复杂度也为Ologn
4.1.1.2 特殊情况 这种情况就从二叉树退化为了链表而链表的时间复杂度为On故它的时间复杂度也为On 。
5.红黑树
5.1 概念
也是一种自平衡的二叉搜索树BST以前叫作平衡二叉B树
5.2 红黑树特质红黑规则
5.2.1 节点要么是红色要么是黑色
5.2.2 根节点必须是黑色
5.2.3 叶子节点都是黑色的空节点标为null的都是空节点
5.2.4 红黑树中红色节点的子节点都是黑色
5.2.5 从任意节点到叶子节点的所有路径都包含相同数目的黑色节点 注再添加或删除节点时如果不符和这些性质会发生旋转以达到所有性质也就是说这五个性质都是为了保证红黑树的平衡。
5.3 红黑树时间复杂度
5.3.1 查找
红黑树也h是一个二叉搜索树故时间复杂度为Ologn
5.3.2 添加
添加搜先要从查找操作开始因为需要查找到目标添加位置时间复杂度为Ologn添加完成后为了保证满足红黑树的特质即规则故需要进行时间复杂度为O1的旋转调整操作。故总时间复杂度为Ologn。
5.3.3 删除
删除搜先要从查找操作开始因为需要查找到目标添加位置时间复杂度为Ologn删除完成后为了保证满足红黑树的特质即规则故需要进行时间复杂度为O1的旋转调整操作。故总时间复杂度为Ologn。
即查找、添加、删除都是Ologn
