-
Size Balanced Tree
平衡性 每棵子树的大小，不小于其兄弟的子树大小。既每棵叔叔树的大小，不小于其任何侄子树的大小。左旋触发条件：cur = 节点 4，cur.right.right.size > cur.left.size。出现右边子树节点数太多。通过左旋，将 cur.right 的结点替换 cur 节点。具体过程如下图# 左旋def left_rotate(self, cur: Node): right_node = cur.right cur.right = right_node.le...…
-
SkipLists
跳表是一个随机化的搜索数据结构跳表的 NB 之处： 思想先进：跳表不再使用硬规则来数据的平衡性，而是使用概率保证。 由于使用概率随机生成数据层，与用户输入的数据无关。跳表时间复杂度评估第 0 层：N 个节点（每个节点必在第 0 层）第 1 层：$\frac{N}{2}$ 个节点第 2 层：$\frac{N}{4}$ 个节点第 3 层：$\frac{N}{8}$ 个节点…第 k 层：$\frac{N}{2^k}$ 个节点类似满二叉树查找数据查找 50 。从 head 的最上层开始查找...…
-
有序表
概述有序表的简单介绍有序表和哈希表的本质区别就是：哈希表的 Key 是通过 Hash 函数散列组织的，而有序表的 Key 是顺序组织的。 有序表在使用层面上可以理解为一种**集合**结构 如果只有 key，没有伴随数据 value，可以使用 TreeSet 结构 如果既有 key，又有伴随数据 value，可以使用 TreeMap 结构 有无伴随数据，是 TreeSet 和 TreeMap 唯一的区别，底层的实际结构是一回事 有序表和哈希表的区别是，有序表把 key 按照顺序组织...…
