- dataStruct
- 分类
- Apr 6, 2018
数据结构—红黑二叉树
继上一篇的23树，红黑二叉树实质上就是一个23树，在《算法》第四版开篇彩页中，将一颗红黑树展开（未展示nil节点），就是一个23树。 红黑树还是遵循了二叉树的约束，主要就将23树中变异的3-节点恢复成了二叉树中的标准节点——实际上是将3-节点中的左key提取折叠到右key的左子树位置并用红色链接表示；黑色链接代表是普通的1-节点。 对-3连接的折叠 一个红链接，实际上，就是一个-3连接节点中，前两个节点的折叠；比如一个-3节点，有BF两个键，红黑树中规定，左边的键需要降级成为右键的左子节点； 而原本-3节点的左和中节点，转变为了B的左子节点和右子节点。 原书对红黑树的一种等价定义（网上一搜红黑树出来的五个定义，是结论上的定义，这里的定义是从实现角度出发的）： 红链接均为左链接； 没有任何一个节点同时和两条红链接相连； 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。 对于以上第一条，是一个约定，就像1+1为什么等于2；如果设定红链接都是右链接也没啥关系； 对于第二条，想想把红链接打开的情况：红链接连接的连个节点，在23树中本是平级的存在；如果存在两个连续的红链接，代表有三个节点在同一个级别；这违反了23树的定义； 红黑树既要 保证23树的定义也要保证二叉树的定义。 对于第三条，黑色节点，也就是普通节点，为了保证局部与整体的平衡，需要选装和变色来处理。 红黑树的旋转与变色 关于一二点、在红黑树中需要特别的去维护、如果红链接出现在了右链接，就需要左旋；如果出现了一个节点上有两个红链接，需要变色或是旋转 变色 如果一个节点有两个子节点，其链接都是红色，那么其子节点都转为黑色，自身转为红色并将其父链接转为红链接。 旋转 如果一个节点其与父节点和子节点的链接有两条红链接，需要视以下情况旋转： /或\字形，如果两条红链接是这种形状，对其右旋或左旋即可； >或<字形，如果是这种形状，需要先对中间层节点旋转； 旋转过程同AVL，大概说一说行了。 插入和删除 以上强调的是红链接，原书中也是以链接来解释，能更好提现折叠，但是网上很多都上来直接说红节点和黑节点； 至于插入和删除；插入过程会不断出现违反上述 1,2性质的过程，需要不断旋转和变色，在AVL的旋转上再加些自身逻辑判断即可； 而删除的话，参考RedBlack.pdf吧…… 对于删除的补充概括，删除一个节点，难处理的情况主要有两种： 删除的节点有子节点并且为红色（这里都不说nil），那么过程和AVL中的删除是一样的，寻找继任者复制待删除元素位置，再删除继任者即可；...
Read More - Apr 6, 2018
数据结构—23树
AVL的完美导致负荷太大 继上一篇对AVL树中的总结；AVL是完美平衡树，对于性能开销太大，因为每次插入删除元素，一是都要递归往上一层记录平衡因子，二是一旦平衡因子绝对值大于一，都要进行旋转； 其实这么完美是没有必要的，当一颗树达到很深的层级以后如此完美的平衡造成根节点很频繁的修改自身平衡因子和主动选装； 一生二二生三 三生万物 2-3树 于是有人提出了23树，23树的性质先不说，其主旨就是为了减轻根结点的压力，如果插入的元素再插入的节点上自己能使自己平衡的话，就不需要递归交给上一层直至根结点处理了； 但是如果要在AVL树的基础上，在每个节点插入时保持自治平衡是不可能的；所谓一生二二生三 三生万物，只有节点产生变异——能有三个子节点，就能保证基本的平衡。（为啥是三节点，从次幂的角度来说，到第N层的时候，没增加一个次幂就能多容纳很多个元素了，所以不要小看多出来的这一个节点） 对于有三个子节点的父节点来说，它会有两个键，左子节点大于起左键，中子节点大于左键小于右键，右子节点大于右键； 插入元素 一个元素X，如果插入到2-节点上，那么还好说，直接将2-转为3-节点即可：之前我以为的是如果2-的节点缺少子节点，会将x作为其子节点，但是这么一来会增加局部的高度…… 一个元素X，如果插入到3-节点上，需要将3-节点临时转为4-节点；然后4-节点中的中键提升到其父节点所在位置；如果父节点因此变为了4-节点，那么递归往上处理 以上两点，体现了节点的局部独立自治平衡，不用每次都要像AVL那样由根节点来旋转实现平衡； 但是23树不是标准的二叉树，对于AVL中的put、delete、和旋转都不适用了； 牛逼的前人们，想出了红黑二叉树表示23树，保证了局部子树的平衡自治，又能使用AVL树中的方法。
Read More - Apr 5, 2018
数据结构—AVL搜索树
BST在极端情况下，比如按顺序插入1，2，3，4，5，6，7；那么这几个元素都会变成上一个元素的右节点，，这样搜索起来复杂度又变成线性的了； 在基于BST的约束上，新增了一个约束，来保证树的搜索不会恶化成线性的： 根结点的左子树和右子树高度距离不超过1 为了实现上述这一点，基于BST需要进行以下改造： 在节点上会多记录一个平衡因子的属性，每个节点的平衡因子都是由其直系子节点的左右分配情况而来；比如叶子节点的平衡因子就是0。 没新增一个节点，需要更新其父节点的平衡因子，递归更新到根结点为止 如果根结点的平衡因子大于一，需要对树进行旋转： 3.1 旋转的过程类似于BST寻找继任者的过程，如果树失衡了，需要将根结点及其偏轻的子树与其偏重的子树割； 3.2 偏重的子树会成为新的根，而偏轻的那一根子树，需要在新的根中找到合适的位置插入： 3.2.1 偏轻的那根树，观其方向，理论上只要取代新的根同一个方向的节点，并将被取代的节点插入到取代后的位置即可； 3.2.2 然而有种特殊的现象，新的根走势为’<’或’>’字型，这样的化会死循环，， 为了解决这种现象，先将’<’或’>’转为’'或’/’，这样旋转才能生效； 以上的规则都是由实际的二叉树图表推导的；AVL树基于BST稍微修改即可得到，但是很少用到AVL，每次插入都递归更新向上节点的平衡因子，并且根结点的平衡因子如果大于 1 的话，还要旋转，性能太低；虽然实现了绝对的平衡，但是带来的性能影响太大； 左旋和右旋比较抽象，实际上就是在BST寻找继任者的基础上改的
Read More - Apr 5, 2018
数据结构—二叉搜索树
二叉搜索树又叫BST，这种结构主要是为了与列表搜索和哈希搜索区别开； BST这种结构，不同于列表一味将元素按递增或递减的顺序排列，而是将元素在插入到树中位置时，就先为其找好适当的位置插入，待需要查询的时候，不需要像列表查询那样需要从头找到尾（或者二分法查找）； BST的实现，其实只要知道以下几个条件即可自己实现： 树中只能有一个根结点 每个节点最多能有两个子节点 每个节点的左子节点必须小于自己，右节点必须大于自己 根据以上三个条件，就可以完成BST了，不过实际上流程还是比较复杂，网上给的教程都是噼里啪啦给一堆图；个人感觉用流程图更清晰： put方法： delete方法： 在删除node的方法中，判断node是否为子节点，如果不是叶子节点，那么删除了node时需要考虑它的子节点怎么处理； 处理的方式就是在node子节点中寻找一位继任者来代替node的位置；看似很麻烦，其实由于BST的三个约束，寻找继任者很简单： 删除node，node的继任者必须满足继任者大于原node的左节点，小于等于原node的右节点； 对于寻找继任者，感觉只要看看二叉堆的性质即可，二叉堆的最左边的左节点是最小的（最左边意思就是它已经没有子左节点，不管它有没有子右节点） 实现以上所说的Node结构，以及BST树中核心的put和delete方法，以及一些辅助方法，就能实现一个二叉搜索树了，至于具体实现网上已经很多就不写了。
Read More - Mar 31, 2018
队列——约瑟夫问题
队列的应用 著名的约瑟夫问题：一个一世纪著名历史学家弗拉维奥·约瑟夫斯的传奇故事。故事讲的是， 他和他的 39 个战友被罗马军队包围在洞中。他们决定宁愿死，也不成为罗马人的奴隶。他们 围成一个圈，其中一人被指定为第一个人，顺时针报数到第七人，就将他杀死。 约瑟夫斯是 一个成功的数学家，他立即想出了应该坐到哪才能成为最后一人。【摘自here】 使用python实现约瑟夫问题 """ 众人围一圈: 1 从一数到七；2 人来又人往；3 逢七便出局；4 直至座一人； """ # fixme 用队列来实现还是有些混淆，用循环队列解决试试 def josheper(players, bullet=7): seat = MyQueue() # 众人围一圈 for player...
Read More