青岛网站制作流程,电子商务网络营销方式,合肥建设网站公司,网站的点击率点击上方蓝字#xff0c;关注并星标#xff0c;和我一起学技术。大家好#xff0c;今天给大家介绍一个很厉害的数据结构#xff0c;它的名字就很厉害#xff0c;叫SB树#xff0c;业内大佬往往叫做傻叉树。这个真不是我框你们#xff0c;而是它的英文缩写就叫SBT。SBT其… 点击上方蓝字关注并星标和我一起学技术。大家好今天给大家介绍一个很厉害的数据结构它的名字就很厉害叫SB树业内大佬往往叫做傻叉树。这个真不是我框你们而是它的英文缩写就叫SBT。SBT其实是英文Size balanced tree的缩写翻译过来可以理解成节点平衡树这是大牛陈启峰在高中参加算法竞赛时期发明的数据结构。不得不说大牛实在是大牛在高中的时候就已经难以望其项背了。二叉搜索树SBT本质上是一棵二叉搜索树我们之前介绍过二叉搜索树但是从来没有真正实现过。我们今天先来复习一下二叉搜索树的概念。对于一棵二叉树而言如果它满足对于每一个节点都有以它右孩子构成的右子树中的所有元素大于它左孩子为根构成的左子树所有元素都小于它那么这样一棵二叉树就可以被认为是一棵二叉搜索树。比如下图就是一棵经典的二叉搜索树。二叉搜索树有什么好处呢我们观察一下上图其实很容易发现当我们想要查找某个元素是否存在于二叉树当中的时候我们可以利用刚才提到的性质进行快速地查找。比如我们想要判断15这个元素在不在树当中我们首先和根节点的11进行判断由于15大于11如果15存在一定在11的右子树。所以我们移动到它的右子树16上继续判断。由于15小于16所以15要存在一定在它的左子树当中以此类推我们只需要经过最多4次比较就可以找到15。对于一棵二叉树而言如果它是完美二叉树每一层的元素都是满的。我们假设它的层数是k那么它一共可以存放个元素。反过来说如果一个完美二叉树当中存在n个元素那么它的层数应该是。换句话说我们只需要次操作就可以判断元素是否存在。但是这是完美的情况大多数情况下普通方法构建出来的二叉搜索树并不是完美的其中可能存在倾斜。在极端情况下甚至可以蜕化成链表。比如这样正因为如此所以我们才需要设置一些机制来保证二叉搜索树的平衡性。平衡性有了二叉搜索树的查找效率才能得到保障。关于让二叉树维持平衡的方法现在有很多种比如大名鼎鼎的红黑树、AVL树等等其实本质上都是二叉搜索树。只是它们维护二叉树平衡性的方法不同。今天我们介绍的SBT同样也是一种自平衡二叉搜索树的实现方法它的核心机制是旋转。旋转旋转是二叉搜索树维持平衡的常用机制说是旋转其实可以理解成树上的某些节点之间互换位置。当然位置不能随意更换我们必须要保证更换位置之后不会破坏二叉搜索树的特性同时让二叉树整体更加趋向于平衡。旋转分为两种一种是左旋另外一种是右旋。我们一个一个来介绍。左旋左旋可以理解成逆时针旋转我们来看一个例子是不是看着有点蒙不知道这个旋转怎么实现的这里我有一个方法我们可以想象一下我们把左边的二叉树以B为轴逆时针旋转90度之后得到的结果是这样我们可以发现B节点拥有三个孩子节点了这显然就违反了二叉树的规则。那么我们就需要断掉它的一个孩子重新分配。那么为什么重新分配是把E分配给D而不是把C分配给E或者是D呢首先我们观察一下就知道C子树的元素都是比B要大的那么把它分配给D显然不合适。对于把C分配给E看起来似乎没有问题但其实仔细想下也会发现不妥。不妥的原因在哪里不妥的地方在于我们不知道E节点的情况如果E没有右子树还好如果E存在右子树那么怎么处理所以我们只有一种解法就是把E分配给D做右子树因为D原先的右子树是B旋转之后一定就不存在右子树了。我们试着写出伪代码def left_rotate(u): ur u.right u.right ur.left ur.left u u ur看起来旋转一通操作猛如虎但是写成代码也就这么几行。右旋左旋理解了右旋也就好办了实际上右旋就是左旋的逆操作。左旋刚才是逆时针的旋转那么右旋自然就是顺时针的旋转。这个不需要死记你只需要记住是向左旋转或者是向右旋转就可以了。对于这样一棵子树我们要进行右旋之前左旋的时候我们是以右孩子作为旋转轴那么右旋自然就要以左孩子作为旋转轴了。旋转90度之后我们得到了这样的结果同样我们发现A节点的孩子数量超过了限制我们需要断开重连。根据刚才一样的判断方法我们可以发现只有一种重连的方式就是把C节点作为D的左孩子。因为D的左孩子原本是A由于旋转D没有左孩子了这样连接一定不会引起冲突和问题。最终我们得到的结果就是同样我们可以写出伪代码def right_rotate(u): ul u.left u.left ul.right ul.right u u ul旋转很好理解但是我们为什么要旋转呢我们观察一下会发现旋转最重要的功能就是改变了一些节点的位置这样可以扭转一些不平衡的情况。比如在右旋之前可能E或者C子树当中元素过多引发了不平衡。当我们旋转之后我们把E和C分别放到了树的两边。这样旋转之后的树距离平衡也就更接近了一些但是如何严格地保证完全达到完美平衡呢这里就需要引入本数据结构的核心概念——size balance了。Size Balance前面我们也说过了实现二叉树平衡的方法有很多同样定义一棵二叉树是否平衡的标准也有很多。比如在AVL树当中是通过左右两棵子树的树深来判断的两边的树深差不超过1那么就认为是平衡了。而在SBT当中我们对二叉树平衡的定义是基于节点数量的也就是Size。这里呢我们需要定义一下size的概念对于树上某个节点而言它的size指的是以它为树根的子树当中节点的数量。接下来我们就要结合size来讨论平衡树不平衡的情况以及我们让它变得平衡能够使用的办法。首先我们先来看看我们认为平衡树达到平衡的条件。这里呢我们一共有两个条件这两个条件都是对称的。我们先来看下一个一般意义上的平衡树。我们观察一下上面的图来思考一下什么情况下可以认为这棵树达成平衡了呢是L.size R.size吗这其实是有问题的因为可能L的节点都落在了A上R的节点都落在了C上。这同样是不平衡的但这种情况除非我们继续往下递归否则很难识别。所以这里换了一种方法我们判断R和AB的size的关系以及L和CD size的关系。我们要求L.size C.size, D.size, R.size A.size, B.size。也就是说高层的size一定要比底层来的大这两个条件都很直观也都很好记。这两个条件理解了我们再去分析它不平衡的条件就很清楚了。一共有四种情况Size of A size of RSize of B size of RSize of C size of LSize of D size of L在这4种情况当中1和3是对称的2和4也是对称的。所以我们只需要着重分析其中两种就可以了另外两种可以通过对称性得到。由于我们使用递归来维护树的平衡性的时候是从底往上的。因此我们可以假设ABCDLR这六棵子树都是平衡的这样可以简化我们的分析。我们假设我们现在有了一个函数叫做maintain它可以将一棵不平衡的子树旋转到平衡状态。我们先假设已经有了这个函数再去看看它里面需要实现哪些逻辑。接下来我们来看看上面四种情况如果不满足的话我们应该怎么处理。情况1情况1当中A.size R.size也就是A当中的节点比较多为了能够趋近于平衡。我们将原子树右旋得到我们右旋之后A的层级向上提升了一层。我们观察一下旋转之后的结果会发现R子树的平衡性得到了保持没有被破坏A子树本身就是平衡的。所以旋转之后还有还有两个节点的平衡性没有保证。一个是T节点一个是L节点。那么我们递归调用maintain(T)和maintain(L)即可。我们写成伪代码就是right_rotate(T)maintain(T)maintain(L)情况2下面我们来看情况2也就是B.size R.size的情况。和上面一种情况类似由于B的节点比较多我们希望能够把B往上提。但是B节点在内部我们无论对L左旋还是右旋都既然对T旋转不行那么我们可以对L进行旋转啊这样不就可以影响到B节点了吗为了展示地更加清楚我们把B子树的孩子节点也画出来。接着我们对L进行左旋这样可以把B往上提升一层得到虽然我们把B往上提了一层但是对于T子树而言左重右轻的局面仍然没有改变。要想改变T的不平衡我们还需要对T进行右旋得到对于这个结果而言除了L、T和B这三棵树而言其他所有的子树都满足平衡了。所以我们按顺序维护L、T和B即可。我们写成代码就是left_rotate(L)right_rotate(T)maintain(L)maintain(T)maintain(B)情况3和情况1刚好相反我们把左旋和右旋互换即可情况4和情况2也一样。所以我们可以写出所有的情况来了def maintain(t): if t.left.left.size t.right.size: right_rotate(t) maintain(t.right) maintain(t) elif t.left.right.size t.right.size: left_rotate(t.left) right_rotate(t) maintain(t.left) maintain(t.right) maintain(t) elif t.right.right.size t.left.size: left_rotate(t) maintain(t.left) maintain(t) else: right_rotate(t.right) left_rotate(t) maintain(t.left) maintain(t.right) maintain(t) 这里的四种情况罗列出来当然就可以但是有很多代码重复了我们可以设置一个flag标记表示我们判断的是左子树还是右子树。这样我们可以把一些情况归并在一起让代码显得更加简洁def maintain(t, flag): if flag: if t.left.left.size s.right.size: right_rotate(t) elif s.left.right.size t.right.size: left_rotate(t.left) right_rotate(t) else: return else: if t.right.right.size t.left.size: left_rotate(t) elif t.right.left.size t.left.size: right_rotate(t.right) left_rotate(t) else: return maintain(t.left, False) maintain(t.right, True) maintain(t, False) maintain(t, True) 这里其实我们省略了maintain(t.left, True)和maintain(t.right, False)这两种情况这两种情况我们稍微分析一下会发现其实已经被包含了。我们搞清楚了这些之后还有一个疑问没有解开就是为什么旋转操作可以让二叉树趋向于平衡呢而不是无穷无尽地旋转下去呢尽管我们已经知道了不会但是还是想要来证明一下。我们以情况一举例我们右旋之后的结果是我们对比一下旋转之前的结果会发现T、R、C、D的高度增加1而L和A的高度减小了1。由于A.size R.sizeA的size最小等于R.size 1也就刚好是T加上R子树的size。这两个部分一增一减互相抵消之后至少还有L这个节点的深度减小了1。也就是说旋转之后的所有元素的深度和是在减小的不仅是情况1如此其他的情况也是一样。既然深度和是在减小的那么maintain这个操作就一定不是无限的。并且它也的确可以让树趋向于稳定因为完美平衡的情况下所有元素的深度和才是最小的。实现细节到这里我们就已经把SBT的原理都讲解完了但是还存在一些细节上的问题。由于我们是使用Python是引用语言所以当我们在旋转的时候进行赋值只是指针之间改变了引用的目标 并没有实际对原本的结构进行改变。我们来看下刚才上面的伪代码def right_rotate(u): ul u.left u.left ul.right ul.right u u ul由于我们把u的左孩子右旋代替了u本来的位置。当我们执行u ul的时候只是u这个指针改变了指向的位置。至于原本的数据结构当中的内容并没有发生变化。因为u、ul这些变量都是临时变量都是拷贝出来的我们随便更改也不会影响类当中的值。在C当中我们可以传入引用这样我们修改引用就是修改原值了。但是Python当中不行想要解决这个问题只有一种方法就是对于每个节点我们都记录它父节点的位置。当我们旋转完了之后我们需要去更新它父节点中储存的孩子节点的地址这样的话我们就不只是局部变量之间互相修改了就真正落实到了数据结构上了。我们以右旋为例 def reset_child(self, node, child, left_or_rightleft): Since Python pass instance by reference, in order to rotate the node in tree, we need to reset the child of father node Otherwise the modify wont be effective if node is None: self.root child self.root.father None return if left_or_right left: node.lchild child else: node.rchild child if child is not None: child.father node def rotate_right(self, node, left_or_rightleft): Right rotate operation of Treap. Example: D / \ A B / \ E C After rotate: A / \ E D / \ C B father node.father lchild node.lchild node.lchild lchild.rchild if lchild.rchild is not None: lchild.rchild.father node lchild.rchild node node.father lchild # 要重新reset父节点的孩子节点这样整个改动才是真的生效了。 self.reset_child(father, lchild, left_or_right) # 更新节点买的size node.size node_size(node.lchild) node_size(node.rchild) 1 lchild.size node_size(lchild.lchild) node_size(lchild.rchild) 1 return lchild由于每个节点的孩子节点有两个所以我们还需要一个变量来记录我们当前要改变的节点究竟是它父亲节点的左孩子还是右孩子这样我们才能在reset的时候正确地修改。不仅是旋转如此删除和添加也是一样的我们都需要修改父节点当中的信息否则我们修改来修改去改的都只是局部变量而已。另外一点是我们旋转之后还需要更新每个节点的size这个逻辑如果忘记了那么后面的maintain就无从谈起了。最后我们思考一个问题我们在什么情况下需要maintain操作呢也就是什么情况下会破坏树的平衡性呢其实很简单就是当树中的元素数量发生改变的时候。无论是增多或者是减少都有可能破坏树的平衡。所以我们在完成了插入和删除之后都需要maintain一次树的平衡。论文当中对于maintain这个操作还有详细的分析可以证明maintain的均摊复杂度是也就是常数级的操作这也是为什么SBT运行效率高的原因。论文的最后还附上了SBT和其他常用平衡树数据结构的比较我们可以看出SBT无论是运行效率还是质量都是其中佼佼者。最后我们聊一聊SBT的实现。关于SBT这类复杂数据结构的实现还是C要更方便一些主要原因就是因为C当中带有引用和指针的传递操作。我们可以在函数内部修改全局的值而Python当中则不行。参数传递默认传递的是拷贝我们在函数内部赋值并不会影响结果。所以如果使用Python实现会更加复杂一些并且需要一些修改父节点的额外操作。因此网上关于SBT的Python实现非常非常少我有自信说我的代码目前是我能找到的实现得比较好的一个。相关代码很长足足有五百多行不适合放在文章当中。如果大家感兴趣可以在公众号内回复SBT关键字进行获取。今天的文章就到这里衷心祝愿大家每天都有所收获。如果还喜欢今天的内容的话请来一个三连支持吧~(点赞、在看、转发)- END -
