哈Ha！
六个月前，我考虑过如何从O（log（N））的二叉树中获取元素。 答案很快就到了-懒散传播。 但是我懒得在代码中实现它。 现在我们需要在大学里参加毕业项目，所以我什么都做。 这就是我坐下来实施的方式。
一些注意事项：- 这棵树是不平衡的（到目前为止，因为仍需要编写文凭项目），结果，估计O（log（N））在各处被随机输入数据摊销。
- 我没有找到类似的数据结构，我所询问的同事和朋友也没有提供类似的数据。 如果您知道这种想法的实施方式，请告诉我。
- 在顶点类中，可以通过将父级传递给方法来免除父级字段。
想法描述让我们为每个顶点存储左侧的顶点数量；让我们在顶点countLefter处调用此字段。 但是，如果我们将最左边的元素添加到树中，我们将不得不更改所有其他顶点的countLefter，这可能会很痛苦，而且其根（哦，这个双关语）根本不符合二叉树的原理。 为了避免这种情况，让我们为每个顶点输入一个添加字段，在其中我们将存储需要为子树的每个顶点（包括该顶点本身）添加到countLefter字段中的数量。 因此，将最左边的元素添加到树中，您只需要：
- 沿着我们到达新顶点插入点的整个路径增加countLefter
- 对于上述右边之一的所有顶点，加1
现在，引入push（）方法是合乎逻辑的，它将在顶点本身及其后代的countLefter中添加添加。
这是顶点类的产生方式：public class UNode { UNode parent; int key; int countLefter; int add; UNode left; UNode right; public UNode() { } public UNode(UNode parent, int key, int countLefter, int add, UNode left, UNode right) { this.parent = parent; this.key = key; this.countLefter = countLefter; this.add = add; this.left = left; this.right = right; } public void push() { countLefter += add; if (left != null) left.add += add; if (right != null) right.add += add; add = 0; } @Override public String toString() { return "Node{" + "key=" + key + ", countLefter=" + countLefter + '}'; } }
太好了，现在您可以开始
构建一棵树了！我们要做的第一件事，就是转到顶部-我们称为push（）方法。
我们将通过左删除来删除该元素（我们采用已删除顶点的最右边的顶点）。
要按索引获取元素，我们必须采取明显行动：如果当前顶点的索引<countLefter，则向左移动。 如果值相等，则找到具有给定索引的顶点。 否则，我们转到右边。
原则上，删除和添加元素与常规二叉树没有太大区别，只是更改了countLefter和add字段。 如果成功添加/删除后我们返回到左侧的顶部，则需要更改这些字段。 如果在右边，否。
这是树代码： import java.util.LinkedList; public class UTree { private UNode root; private int size; public UTree() { } public int size() { return size; } public int get(int index) { return get(index, root); } public boolean add(int key) { if (root == null) { root = new UNode(null, key, 0, 0, null, null); size++; return true; } boolean res = add(key, root); if (res) size++; return res; } public boolean remove(int key) { if (root == null) return false; if (key == this.root.key) { root.push(); removeRoot(); size--; return true; } boolean res = remove(key, root); if (res) size--; return res; } private int get(int index, UNode root) { root.push(); if (index == root.countLefter) return root.key; if (index < root.countLefter) return get(index, root.left); return get(index, root.right); } private boolean add(int key, UNode root) { if (key == root.key) return false; root.push(); if (key < root.key) if (root.left != null) { boolean res = add(key, root.left); if (res) { root.countLefter++; if (root.right != null) root.right.add++; } return res; } else { root.left = new UNode(root, key, root.countLefter, 0, null, null); root.countLefter++; if (root.right != null) root.right.add++; return true; } if (root.right != null) return add(key, root.right); else { root.right = new UNode(root, key, root.countLefter + 1, 0, null, null); return true; } } public boolean removeByIndex(int index) { if(this.root == null) return false; root.push(); if (index == this.root.countLefter) { removeRoot(); return true; } boolean res = removeByIndex(index, root); if (res) size--; return res; } private boolean removeByIndex(int index, UNode root) { if (root == null) return false; root.push(); if (index == root.countLefter) return removeNode(root); if (index < root.countLefter) { boolean res = removeByIndex(index, root.left); if (res) { root.countLefter--; if (root.right != null) root.right.add--; } return res; } else return removeByIndex(index, root.right); } private boolean removeNode(UNode root) { if (root.left == root.right) { if (root.parent.left == root) root.parent.left = null; else root.parent.right = null; return true; } if (root.left == null) { if (root.parent.left == root) { root.parent.left = root.right; root.right.add--; } else { root.parent.right = root.right; root.right.add--; } root.right.parent = root.parent; return true; } if (root.right == null) { if (root.parent.left == root) root.parent.left = root.left; else root.parent.right = root.left; root.left.parent = root.parent; return true; } UNode right = getRight(root.left); cut(right); root.key = right.key; root.countLefter--; root.right.add--; return true; } private boolean remove(int key, UNode root) { if (root == null) return false; root.push(); if (key == root.key) return removeNode(root); if (key < root.key) { boolean res = remove(key, root.left); if (res) { root.countLefter--; if (root.right != null) root.right.add--; } return res; } else return remove(key, root.right); } private void removeRoot() { if (root.left == root.right) { root = null; return; } if (root.left == null) { root = root.right; root.add--; return; } if (root.right == null) { root = root.left; return; } UNode right = getRight(root.left); cut(right); root.key = right.key; root.countLefter--; root.right.add--; } private static void cut(UNode node) { if (node.parent.left == node) node.parent.left = node.left; else node.parent.right = node.left; if (node.left != null) node.left.parent = node.parent; } private UNode getRight(UNode root) { root.push(); if (root.right == null) return root; return getRight(root.right); } public void printTree() { printTree(root); } private void printTree(UNode root) { if (root == null) return; root.push(); printTree(root.left); System.out.println(root); printTree(root.right); } public LinkedList<UNode> getAll(){ LinkedList<UNode> res = new LinkedList<>(); getAll(root, res); return res; } private void getAll(UNode root, LinkedList<UNode> res){ if (root == null) return; root.push(); getAll(root.left, res); res.add(root); getAll(root.right, res); } }
→
这里的代码可以在github上找到。
我将给出一些工作速度的结果。 测试的依据是：
添加到树中：因此，在[0; 0; 1_000）：
大约100毫秒。 TreeSet在大约130毫秒内完成了此任务。
在[0; 10_000）：
大约150毫秒。 TreeSet在大约190毫秒内完成了此任务。
在[0; 100_000）：
大约320毫秒。 TreeSet在大约415毫秒内完成了此任务。
在[0; 1_000_000）：
大约510毫秒。 TreeSet在大约700毫秒内完成了此任务。
在[0; 10_000_000）：
大约590毫秒。 TreeSet在大约750毫秒内完成了此任务。
立即移除随机将一百万个数字添加到树中。 然后，我们尝试删除一百万次随机数。 在测试中，仅考虑移除时间。
添加和删除范围[0; 10_000_000）：
大约740毫秒。 TreeSet在大约750毫秒内完成了此任务。
添加和删除范围[0; 1_000_000）：
大约600毫秒。 TreeSet在大约800毫秒内完成了此任务（比以前的测试还多）。
添加和删除范围[0; 100_000）：
大约130毫秒。 TreeSet在大约160毫秒内完成了此任务。
添加和删除范围[0; 10_000）：
大约45毫秒。 TreeSet在大约50毫秒内完成了此任务。
添加和删除范围[0; 1_000）：
大约30毫秒。 TreeSet在大约37毫秒内完成了此任务。
好了，最后，为了一切开始，按索引访问TreeSet没有此功能。 因此，我将仅给出UTree的结果。 再次添加一百万个元素，然后从0到树中元素数的随机索引处获得该元素。 仅考虑按索引访问的时间。
加法范围[0; 1000）：85毫秒
加法范围[0; 10_000）：140毫秒
加法范围[0; 100_000）：300毫秒
加法范围[0; 1_000_000）：655毫秒
我希望有人觉得我的想法有用，但也许对某人来说，这是处理二叉树的机会，如果您还没有这样做的话:)
聚苯乙烯新年过后，我打算对平衡树感到困惑。 如果我这样做，则继续链接将显示在此处。