网站链接视频怎么做,短网址在线生成哪个好,网站制作学习,商务网站建设毕业设计概述
二叉树#xff08;Binary Tree#xff09;#xff1a;每个节点最多有两个子节点#xff08;左子节点和右子节点#xff09;#xff0c;没有限制节点的顺序。特点是简单直观#xff0c;易于实现#xff0c;但查找效率较低。
二叉搜索树#xff08;Binary Search…概述
二叉树Binary Tree每个节点最多有两个子节点左子节点和右子节点没有限制节点的顺序。特点是简单直观易于实现但查找效率较低。
二叉搜索树Binary Search TreeBST在二叉树的基础上左子节点的值小于等于父节点的值右子节点的值大于等于父节点的值。特点是插入、删除和查找的平均时间复杂度为O(log n)但如果树不平衡可能会退化为链表时间复杂度为O(n)。
平衡二叉树Balanced Binary Tree在二叉搜索树的基础上保持树的平衡即左右子树的高度差不超过1。常见的平衡二叉树有AVL树和红黑树。特点是插入、删除和查找的时间复杂度为O(log n)但维护平衡的代价较高。
红黑树Red-Black Tree是一种自平衡的二叉搜索树通过对节点进行着色和旋转操作来保持树的平衡。特点是插入、删除和查找的时间复杂度为O(log n)并且对于任意节点从根节点到达该节点的路径长度相等。
B树B-Tree一种多路搜索树每个节点可以有多个子节点。特点是适合存储在磁盘或其他外部存储设备上的大量数据可以减少磁盘I/O操作的次数。
B树B Tree在B树的基础上进行了优化非叶子节点只存储索引信息所有叶子节点通过指针连接形成链表。特点是适合范围查询和排序常用于数据库索引。
详解
结构特点树的节点数目、子节点数目、节点之间的关系等。
平衡性是否能够保持树的平衡即节点的左右子树高度差是否有限制。
插入、删除和查找的时间复杂度不同树对这些操作的时间复杂度不同影响了树的使用场景。
存储和访问方式不同树的存储方式和访问方式有所不同适用于不同的应用场景。
二叉树Binary Tree
只是看起来是个树乱序查找数据得一个一个的找所以没啥用。
二叉搜索树Binary Search TreeBST
有序的查找比二叉树要快如图找0005的话从根节点开始只需要寻找3次就能找到 但如果是这样的那就得找5次这就退化成了链表 平衡二叉树Balanced Binary Tree
为解决退化问题在二叉搜索树的基础上通过旋转来保持平衡使左右子树的高度差不超过1。 旋转方式
先看下每个节点里有什么 1、节点值每个节点都包含一个值用于存储数据。 2、左子树指针指向节点的左子树的指针。 3、右子树指针指向节点的右子树的指针。 4、父节点指针指向节点的父节点的指针。这个参数在某些实现中可能会被省略。5、平衡因子平衡因子是用于判断节点平衡状态的指标它是指一个节点的左子树高度减去右子树高度的差值。平衡因子可以为-1、0或1分别代表左子树高度比右子树高度小1、相等或大1。 情况与旋转方式 LL左-左情况0004作为根节点右旋操作 RR右-右情况0004作为根节点左旋操作。 LR左-右情况0003和0004交换得到LL左-左情况。 RL右-左情况0004和0005交换得到RR右-右情况。 旋转前 旋转后 下面这种情况同时满足LL、LR用两种选择方式来选择都是可以的默认是LL。RR、RL同理默认RR。 当作LL情况时 先无视0004旋转后再把0004插入。 当作LR情况时先无视0002旋转后再把0002插入。
旋转前 旋转后 由于绝对平衡要求过于严苛当数据庞大的时候需要消耗大量的资源进行旋转来保持平衡。
红黑树Red-Black Tree
红黑树是一种自平衡的二叉查找树具有以下特点 节点是红色或黑色每个节点要么是红色要么是黑色。 根节点是黑色根节点始终是黑色的。 叶子节点NIL节点空节点是黑色叶子节点是特殊的空节点它们被认为是黑色的。 红色节点的子节点都是黑色的红色节点不能连续出现即红色节点的父节点和子节点都是黑色的。 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点这个特性保证了红黑树的平衡性即任意两个叶子节点的路径长度相等。
自平衡满足红黑树的条件即可、无需像平衡二叉树那样高度差绝对值必须小于等于1。红黑树的自平衡操作主要包括左旋、右旋和颜色翻转三种操作在插入或删除一个节点时红黑树最多需要进行3次旋转即可达到平衡。 红黑树旋转
参照红黑树最多三次旋转达到平衡 - 简书 (jianshu.com)
B树B-Tree
相比于二叉搜索树B树的每个节点可以存储更多的键和值。数据直接存储在节点上。 B树B Tree
相比于B树B树内部节点上只存储键具体数据存到叶子节点上。 在线演示工具 二叉搜索树https://www.cs.usfca.edu/~galles/visualization/BST.html 平衡二叉树https://www.cs.usfca.edu/~galles/visualization/AVLtree.html 红黑树https://www.cs.usfca.edu/~galles/visualization/RedBlack.html B树https://www.cs.usfca.edu/~galles/visualization/BTree.html B树https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
