wap版网站建设方案网站推广的意义和方法

当前位置： 首页 > news >正文

wap版网站建设方案,网站推广的意义和方法,wordpress 页面 404,怎么制作软件app教程二叉搜索树#xff08;Binary Search Tree#xff09; 二叉搜索树是一种特殊的二叉树#xff0c;它用来快速搜索某个值#xff0c;对于每个节点都应该满足以下条件#xff1a; 若该节点有左子树#xff0c;那么左子树中所有节点的值都应该小于该节点的值。若该节点有右…二叉搜索树Binary Search Tree 二叉搜索树是一种特殊的二叉树它用来快速搜索某个值对于每个节点都应该满足以下条件 若该节点有左子树那么左子树中所有节点的值都应该小于该节点的值。若该节点有右子树那么右子树中所有节点的值都应该大于该节点的值。左右子树都应该是二叉搜索树。 根据条件三可以确定二叉搜索树是通过递归定义的。 并且我们可以得到以下结论左子树节点值 根节点值 右子树节点值。 所以二叉搜索树的中序遍历是一个升序的序列。 但是我们构建二叉搜索树的目的不是为了排序是为了高效地查询、插入、删除元素。 二叉搜索树示例图
查找操作 查找操作就是从根节点开始沿某个路径一直向下搜索的过程。要查找的值比当前节点值小就往当前节点的左子树查找要查找的值比当前节点值大就往当前节点的右子树查找。直到找到要查找的值为止。 当节点分布均匀时时间复杂度一般为树的高度O(logn) 但是最坏情况下节点会退化成链表所以时间复杂度为O(n)。 插入操作 将一个元素插入到树中是从根节点开始与当前节点相比较如果比当前节点的值小就进入该节点的左子树如果比当前节点的值大就进入该节点的右子树。直到遇到一个空节点就可以将要插入的节点安放在这个空节点的位置。所以插入的节点一定是一个新添加的叶子节点。并且在二叉搜索树中通常不允许存储重复的值。 同查询操作一样时间复杂度为O(n)。 删除操作 删除操作分为三种情况 当要删除的节点为叶子节点的时候直接删除。当要删除的节点有左子树或者右子树的时候删除该节点用该节点的子节点代替该节点。当要删除的节点既有左子树又有右子树的时候有两种方法但是目的都是将情况变成第一种或者第二种。 3.1 找到该节点的直接前驱(该节点左子树中的最大值)来代替该节点然后针对这个直接前驱完成情况二节点的删除。 3.2 找到该节点的直接后继(该节点右子树中的最小值)来代替该节点然后针对这个直接后继完成情况二节点的删除。 解释 节点 x 的直接前驱在中序遍历中x 的前驱。在 x 的左子树的最右下节点该节点一定没有右子树。对于“该节点一定没有右子树”的解释因为该节点如果有右子树那么说明有比该节点还大的节点那么该节点就不是 x 的直接前驱了。 节点 x 的直接后继在中序遍历中x 的后继。在 x 的右子树的最左下节点该节点一定没有左子树 演示第三种删除 给出一个二叉搜索树如下图所示现要删除节点20 那么根据第三种情况我们要先找到节点20的直接前驱17或者直接后继25然后将这个直接前驱或者直接后继复制一份替换掉根节点。 此时我们再将原来的那个直接前驱或者直接后继删除掉即可这时候删除它就变成了情况1或者情况2 如果选择3.1删除17就是情况1删除叶子节点直接删掉即可 如果选择3.2删除25就是情况2用节点26代替节点25即可。 Q可能此时就有人有疑问难道就不会出现要删除的直接前驱或者直接后继既有左子树又有右子树 A这时不可能的直接前驱要是还有右子树那他就不是直接前驱。根据BST定义可知一个节点的右子树的值肯定要比该节点大。所以直接前驱时没有右子树的。 我们继续以方式3.2为例演示 将25删掉之后将26放在25的位置上。切不可放到28的右子树上去了。 这样就完成了节点20的删除。 平衡二叉树AVL树 我们知道在二叉搜索树中对于一个有序度很高的序列甚至是一个有序数列我们在利用这个序列建二叉搜索树的时候树会退化成一个链表这样一来各种操作的时间复杂度将会变得很高。那么如何解决这种情况呢我们引入了AVL树的概念AVL树是一种自平衡的二叉搜索树那么如何实现这个自平衡呢就让我们接着学习。 基本概念 为保证二叉搜索树的性能在插入、删除节点时规定任意节点的左右子树高度差不超过 1 这样的二叉搜索树被称为AVL树。 左右子树的高度差被称为平衡因子BFBF 左子树高度 - 右子树高度取值范围为[-1,0,1]。 查找操作 查找原理同二叉搜索树一样从根节点开始向下查找。时间复杂度为O(logn)比BST更稳定 插入操作 我们先按照二叉搜索树的算法插入一个节点那么在途径的所有节点的平衡因子都可能会受到影响它们的BF的绝对值可能变得大于1了此时就应该想办法调整这棵树的结构让它重新变成平衡二叉树。 那么如何调整呢从哪里开始调整呢我们要先认识一个基本概念两个基本操作。 一个基本概念两个基本操作 基本概念最小不平衡子树。 在插入一个新节点之后可能会造成很多节点的BF绝对值都大于1此时我们应该找到距离新插入的节点最近的不平衡的点BF绝对值大于1的点以这个点为根的子树就是最小不平衡子树。 我们要调整的地方就是在最小不平衡子树处仅需让最小不平衡子树平衡整棵树就平衡了。为了简写下文中称最小不平衡子树的根节点为T。 基本操作左旋、右旋。 这两个操作都是对于T进行的T对于T的右子树左旋、T对于T的左子树右旋。 首先来看一种简单的左旋 7是最小不平衡子树的根节点T现在要对T绕12进行左旋我们可以很直观的看到左旋之后降低了T的右子树高度使T的BF变成了0那为什么左旋之后仍然符合二叉搜索树的要求左子树根节点右子树呢注意理解这个地方节点7是从12的左父亲旋转到左孩子的不管它是父亲还是孩子它都在12的左边这里强调的是一种相对关系在下面我们会举例更复杂的左旋在旋转时处理两个不相邻的节点时需要关注它们的相对关系。旋转操作不仅涉及父子节点的转换还需要考虑整个子树的结构平衡。 铺垫完了现在我们来看一种复杂的左旋 这是一颗平衡二叉树没有出现失衡。 当我们插入一个节点18它会按照插入算法被安放在节点15的右孩子的位置。 这时这个二叉树出现失衡。节点5是T节点。由于插入的新节点的位置是在T的右孩子的右子树中属于RR型插入需要左旋T节点来保持平衡。 这时候我们将T绕10左旋转的时候会发现10的左边有个孩子挡住了我们的旋转此时怎么办呢 我们在上文中说过要以基本原则来思考一个节点的右子树的所有节点都是比它大的。那么可以将6放在5的右孩子上也不破坏原本的二叉搜索树结构。让T的右孩子的左子树变成T的右子树。 于是我们得到了这个重新平衡的AVL树 讲完基本操作下面我们来看四种插入类型以及对应的自平衡调整方式。 AVL 树的插入与四种旋转LL, RR, LR, RL 在 AVL 树 中插入新节点后可能会导致某些节点的 平衡因子BF 超出 [-1, 0, 1] 的范围这时需要针对 最小不平衡子树的根节点T 进行 旋转 来恢复平衡。 新节点不同的插入方式对应的旋转方式也是不一样的。 LL型 插入方式新节点插入在T的左孩子的左子树上所以被称为LL型插入。 调整方式右旋T节点。RR型 插入方式新节点插入在T的右孩子的右子树上。 调整方式左旋T节点。LR型 插入方式新节点插入在T的左孩子的右子树上。 调整方式左旋孩子节点再右旋T节点。RL型 插入方式新节点插入在T的右孩子的左子树上。 调整方式右旋孩子节点再左旋T节点。 练习构建以下序列的AVL树10 6 18 12 13 8 20 17 28 删除操作 同插入操作一样删除操作也是先通过二叉搜索树的删除算法删除一个节点e然后就要从这个节点e开始向上找到第一个不平衡的节点T于是就要对这个节点进行调整。 如何调整呢我们首先要找到以这个T节点为根的子树中最高的儿孙节点根据孙子节点相对于儿子节点的位置判断属于哪种类型LL、RR、LR、RL然后对这个T进行调整。调整完了T之后要继续向上寻找不平衡的点继续调整。 为什么插入操作只用调整一次而删除操作调整完一次之后还要继续查找不平衡的点因为插入操作是要在固定的位置插入的这个位置取决于值的大小而删除操作是在任意位置删除一个节点那么任意删除的这个节点很可能就影响到了其他很多个节点的平衡所以要向上挨着调整。 如何寻找最高的儿孙节点如下图所示假设T为最小不平衡子树根节点我们需要在T的左右子树中寻找较高的那个子树较高子树的根节点就是最高儿子节点。然后我们继续在最高儿子节点的左右子树中寻找较高的那个子树此时这个子树的根节点就是最高孙子节点。 注黄色节点为最高儿子节点绿色节点为最高孙子节点。 红黑树RBT 基本概念 红黑树是在二叉搜索树的基础上在每个节点中增加了一个储存节点颜色的信息位同过对任意一条从根到叶子节点路径上的各个节点的着色限制确保没有一条路径比其他的路径长出两倍。这样一来就保证了二叉搜索树的相对平衡不会出现极端情况。这就是红黑树。 RBT的规则 注意在RBT中我们所说的叶子节点NIL节点与正常的二叉树中的叶子节点Leaf Node是有区别的RBT的叶子节点是指空节点 1.每个节点要么是红色要么是黑色 2.根节点或者叶子节点必须是黑色 3.红色节点的两个孩子必须都是黑色节点就是说不会有两个相连的红色节点 4.对于任意一个节点这个节点到其所有叶子节点的路径上每条路径上的黑色节点的数量必须是相同的 RBT的性质 1.最长路径不会超过最短路径的两倍。 最短路径全由黑色节点组成设其长度为 b。 最长路径红黑节点交替出现由于红色节点不能连续最长路径的黑色节点数也为 b红色节点数最多为 b-1因此最长路径长度为 2b-1。 所以最长路径不会超过最短路径的两倍。 2.有n个节点的红黑树树的高度 h 2log2(n 1) 由这个性质可以得到在RBT中的查询、插入、删除操作时间复杂度都是O(logn)。

1. 1黑高度的定义 黑高度black-height是指从某个节点到叶子节点的路径上的黑色节点数量不包括该节点本身。根据性质5所有路径的黑高度相同。 2.2 红黑树的高度与黑高度的关系 设红黑树的黑高度为 bh则树的高度 h 满足h 2 * bh 这是因为红节点不能连续出现路径上的红色节点数量最多与黑色节点数量相等。 2.3 节点数量与黑高度的关系 对于黑高度为 bh 的红黑树节点数量 n 满足n 2^bh - 1 这是因为黑高度为 bh 的树至少是一个完全二叉树节点数量为 2^bh - 1。 2.4 推导高度与节点数量的关系 由 n 2^bh - 1可得bh log2(n 1) 结合 h 2 * bh得到h 2 * log2(n 1) 查找操作 原理同二叉搜索树的查找操作 由于红黑树的高度 h 2 * log2(n 1)查找操作的时间复杂度为 O(log n)。 插入操作 新节点颜色 插入操作的原理也是按照二叉搜索树的算法插入元素但是这个插入的新节点应该是什么颜色呢 很明显新节点设置为红色会更好。 如果新节点设置为黑色那么在插入一个新节点的时候他一定会使从根节点到叶子结点这条路径上的黑色节点数目变多那么每次插入都需要重新调整这条路径上的黑色节点数目这样很麻烦。 如果新节点颜色设置为红色那么只可能违反两个红色节点不相连或者根节点不能为红色这两个原则这两个调整起来很简单并且有可能在插入新节点的时候并不破坏树的结构。 插入后调整方式 插入的节点是根节点 只需要将新节点的颜色由红色设置为黑色即可。 新节点的叔叔节点是红色 这种情况不需要旋转操作此时要将父亲、叔叔、爷爷节点全部改变颜色。并且将改变后的爷爷节点当作新插入的节点继续向上判断直至RBT树平衡。 叔叔节点是黑色 这时候需要看新节点和爷爷节点的位置关系通过旋转 变色来调整分四种情况 LL型 新节点是爷爷节点的左孩子的左孩子 调整方式右旋父亲节点 父爷变色RR型 新节点是爷爷节点的右孩子的右孩子 调整方式左旋父亲节点 父爷变色LR型 新节点是爷爷节点的左孩子的右孩子 调整方式先左旋孩子节点再右旋父亲节点 儿爷变色RL型 新节点是爷爷节点的右孩子的左孩子 调整方式先右旋孩子节点再左旋父亲节点 儿爷变色