从二叉树中随机 select 个节点
Randomly select a node from a Binary Tree
我的树class:
public class BT<E>{
E value;
BT<E> left, right;
public BT(E value)
{
this.value=value;
}
public BT (E value, BT left, BT right)
{
this.value = value;
this.left = left;
this.right = right;
}
生成树后如何从树中返回随机节点？我知道我生成的每棵树的深度和节点数。
所以使用随机整数方法和return一个介于0和树大小之间的整数。
然后在树上进行广度/深度优先遍历，使用计数器，return到达随机整数时节点。
Random rand = new Random();
int randomNum = rand.nextInt(treesize);
int count = -1;
Node randNode;
public static void getRandomTraversal(Node root){
count++;
if(count == randomNum)
randNode = root;
if(root.leftChild != null)
getRandomTraversal(root.leftChild);
if(root.rightChild != null)
getRandomTraversal(root.rightChild);
}
或者，您可以删除 count 作为全局变量并将其添加为递归函数的参数。虽然当树有多个 child.
时，这对于二叉树来说并不那么容易
- Select一个随机数(
new Random().nextInt(numberOfNodes))
- 随心所欲地遍历树（深度优先，广度优先，后序，中序，前序）
- 对于您访问的每个节点，增加一个计数器
- 如果计数器的值等于随机选择的数字，则选择该节点
Dennis 和 Jeroen 的算法实现起来很简单，但是 O(n)。我相信我有一个稍微复杂一点的 O(log n) 算法。
每个节点都需要均等的被选中机会。所以在某棵树 T 中，令 LN(T) 为左树中的节点数，RN(T) 为右树中的节点数，N(T) 为节点数节点总数，包括这个（所以 N(T) = 1 + LN(T) + RN(T)）。 Select 来自 0 to N(T) - 1 的随机数 R。如R == 0、return这个节点。如果1 <= R <= LT(N)，在左子树上递归这个方法。否则，在右子树上递归此方法。
未经测试的代码（假设 BT 有一个 .size() 方法适用于 O(1)）：
public BT randomNode() {
int r = new Random().nextInt(this.size());
if (r == 0) {
return this;
} else if (left != null && 1 <= r && r <= left.size()) {
return left.randomNode();
} else {
return right.randomNode();
}
}
当然你可以做一些事情，比如从方法中提升 new Random() 但算法是一样的。
编辑：修复了左子树为空时的空指针异常。
首先
问题也出自书籍 <Cracking the coding interview 6th>，在部分：IX Interview Questions | 4. Trees and graphs | Question 4.11.
（Gayle Laakmann McDowell的一本好书，他是Google的软件工程师，采访过很多人。）
算法
(A) 随机数决定，记录子树大小
逻辑：
实现二叉树节点。
- 每个节点都有一个大小字段。
指示以此节点为根的子树大小。
- 如果每个节点都有一个指向其父节点的父字段，这会有所帮助。
实现二叉树，最好是BST。
- 插入/删除时，维护节点的大小和父字段。
BSTNode getRandomNode(BSTNode current, int rand)
将 rand 与子树大小进行比较：
Node<T> left = current.getLeft(); // left,
int leftSize = (left == null ? 0 : left.getSize()); // get size of left subtree,
if (rand == leftSize) return current; // current is chosen,
if (rand < leftSize) return randomNode(current.getLeft(), rand); // call on left subtree recursively,
else return randomNode(current.getRight(), rand - leftSize - 1); // call on right subtree recursively,
- T getRandomNode(BST树)
- 如果树为空，return null。
- 生成一个随机数，范围为
[0, size)。
- 调用
getRandomNode(tree.getRoot(), rand)，获取随机节点。
- Return 随机节点的值。
复杂度：
- 时间：
O(h)
- Space:
O(1), (方法堆栈使用 O(h))
其中：
h 是树的高度。
(B) 放入链表，随机索引访问
逻辑：
- 将树节点添加到列表中，支持通过索引快速访问。
- 调用该方法时，在
[0, size)范围内生成一个随机索引，然后获取给定索引处的节点。
复杂度：
时间：O(1) （如果树是静态的）
Space: O(n)
其中：
n是树的大小。
提示：
- 如果树是动态的，那么树变化时也需要维护数组。
- 当一个节点从树中移除时，也需要从数组中移除。
这也需要 O(n).
- 当一个节点添加到树中时，也需要追加到数组中。
如果末尾有空 space，则需要 O(1)，但在调整数组大小时，它是 O(n)。
比较两种算法：
- 对于动态树，
A 使用的内存更少，运行速度更快。肯定是赢家。
- 对于静态树，也可以考虑
B，在构建数组后循环时可能会更快。
代码
（以下是Java中使用上述算法A的实现，带有测试用例。）
RandomBST.java
import java.util.concurrent.ThreadLocalRandom;
/**
* Random BST impl.
*
* @param <T>
* @author eric
* @date 2/10/19 5:02 PM
*/
public class RandomBST<T extends Comparable> extends BST<T> implements RandomBSTDesign<T> {
@Override
public void add(T v) {
root = add((RandomBSTNode<T>) root, v, (RandomBSTNode<T>) root);
}
/**
* Add to a subtree start from given node.
*
* @param current root of a subtree to add node to,
* @param currentParent parent of current,
* @param v
* @return the new root of subtree,
*/
protected RandomBSTNode<T> add(RandomBSTNode<T> current, T v, RandomBSTNode<T> currentParent) {
if (current == null) { // subtree is empty,
RandomBSTNode<T> newNode = new RandomBSTNode<>(v, currentParent); // create new node,
newNode.incSizeOfParents(); // increase size of parents,
size++;
return newNode;
}
// compare,
int compareFlag = v.compareTo(current.value);
// check this or subtree,
if (compareFlag < 0) { // smaller, go to left subtree,
current.left = add(current.getLeft(), v, current);
} else if (compareFlag > 0) { // larger, go to right subtree,
current.right = add(current.getRight(), v, current);
} else { // equals, ignore it,
}
return current;
}
@Override
protected RandomBSTNode<T> delete(BSTNode<T> current, T v) {
return delete((RandomBSTNode<T>) current, v); // cast to subtype to call another method,
}
/**
* Delete given value in subtree, if any.
*
* @param current
* @param v
* @return new root of the subtree
*/
protected RandomBSTNode<T> delete(RandomBSTNode<T> current, T v) {
if (current == null) return null;
// compare,
int compareFlag = v.compareTo(current.value);
// check this or subtree,
if (compareFlag < 0) { // smaller, go to left subtree,
current.left = delete(current.left, v);
} else if (compareFlag > 0) { // larger, go to right subtree,
current.right = delete(current.right, v);
} else { // equals, delete it,
// no child,
if (current.left == null && current.right == null) {
current.decSizeOfParents(); // decrease size of parents,
size--;
return null;
}
// one child - right,
if (current.left == null) {
current.decSizeOfParents(); // decrease size of parents,
size--;
RandomBSTNode<T> randomRight = current.getRight(); // cast to subtype,
randomRight.parent = current.parent;
return randomRight;
}
// one child - left,
if (current.right == null) {
current.decSizeOfParents(); // decrease size of parents,
size--;
RandomBSTNode<T> randomLeft = (RandomBSTNode<T>) current.left; // cast to subtype,
randomLeft.parent = current.parent;
return randomLeft;
}
// 2 child,
T smallestInRight = findSmallestValue(current.right);
current.value = smallestInRight; // replace current with smallest in right subtree,
current.right = delete(current.right, smallestInRight); // delete original smallest value in right subtree,
}
return current;
}
@Override
public RandomBSTNode<T> getRoot() {
return (RandomBSTNode<T>) root;
}
@Override
public T randomValue() {
if (size == 0) return null; // empty tree,
int rand = ThreadLocalRandom.current().nextInt(size); // random value,
RandomBSTNode rnode = randomNode(getRoot(), rand); // get random node,
// System.out.printf("rand = %d, random node: %s\n", rand, rnode);
return rnode == null ? null : (T) rnode.value;
}
protected RandomBSTNode randomNode(RandomBSTNode<T> current, int rand) {
RandomBSTNode<T> left = current.getLeft(); // left,
int leftSize = (left == null ? 0 : left.getSize()); // get size of left subtree,
if (rand == leftSize) return current; // current is chosen,
if (rand < leftSize) return randomNode(current.getLeft(), rand); // call on left subtree recursively,
else return randomNode(current.getRight(), rand - leftSize - 1); // call on right subtree recursively,
}
/**
* Random BST node impl.
*
* @param <T>
*/
static class RandomBSTNode<T extends Comparable> extends BSTNode<T> implements RandomBSTNodeDesign<T> {
protected int size; // size of subtree which has this node as root,
protected RandomBSTNode<T> parent; // parent of this node, or null if this is root,
public RandomBSTNode(T value, RandomBSTNode<T> parent) {
this(value, 1, parent); // on creation, got size 1,
}
public RandomBSTNode(T value, int size, RandomBSTNode<T> parent) {
super(value);
this.size = size;
this.parent = parent;
}
@Override
public int incSize() {
return ++size;
}
@Override
public int decSize() {
return --size;
}
@Override
public void incSizeOfParents() {
RandomBSTNode<T> pn = parent;
while (pn != null) {
pn.incSize();
pn = pn.parent;
}
}
@Override
public void decSizeOfParents() {
RandomBSTNode<T> pn = parent;
while (pn != null) {
pn.decSize();
pn = pn.parent;
}
}
@Override
public boolean isRoot() {
return parent == null;
}
@Override
public RandomBSTNode<T> getLeft() {
return (RandomBSTNode<T>) left;
}
@Override
public RandomBSTNode<T> getRight() {
return (RandomBSTNode<T>) right;
}
@Override
public int getSize() {
return size;
}
@Override
public RandomBSTNode getParent() {
return parent;
}
@Override
protected void appendMoreToString(StringBuilder sb) {
sb.append(", size = ").append(size); // size,
sb.append(", parent value = ").append(parent == null ? null : parent.getValue()); // parent,
}
/*------ unsupported methods ------*/
@Override
void setLeft(BSTNode<T> left) {
throw new UnsupportedOperationException("Should not set subtree directly, because size is difficult to maintain.");
}
@Override
void setRight(BSTNode<T> right) {
throw new UnsupportedOperationException("Should not set subtree directly, because size is difficult to maintain.");
}
}
}
RandomBSTTest.java (部分)
（单元测试，通过TestNG）
import org.testng.Assert;
import org.testng.annotations.BeforeMethod;
import org.testng.annotations.Test;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.function.Consumer;
/**
* RandomBST test.
*
* @author eric
* @date 2/10/19 5:50 PM
*/
public class RandomBSTTest {
private int n = 100;
private int avgRound = (1 << 18); // avg round for each node, when get random value,
private RandomBST<Integer> mbst; // minimal BST,
private RandomBST<Integer> ebst; // empty BST,
@BeforeMethod
public void init() {
// init minimal BST,
mbst = CreateMinimalBST.createRandomFromNumRange(0, n);
// init empty BST,
ebst = new RandomBST<>();
}
// other non-random related test cases are removed,
// randomValue()
@Test
public void testRandomValue() {
int round = n * avgRound; // total round,
System.out.printf("tree size: %d, total round: %d, result:\n", n, round);
Map<Integer, Integer> freqMap = new LinkedHashMap<>();
// init map,
for (int i = 0; i < n; i++) {
freqMap.put(i, 0);
}
// get random value & count frequency,
for (int i = 0; i < round; i++) {
int rv = mbst.randomValue();
freqMap.put(rv, freqMap.get(rv) + 1);
}
double avgPercentage = 100 / n; // average percentage,
// print result,
for (int x : freqMap.keySet()) {
int freq = freqMap.get(x);
double percentage = freq * 100.0 / round;
double diffPercentage = percentage - avgPercentage;
System.out.printf("\trandom value: %2d, chosen count: %d, percentage: %.4f %%, differ: %.4f %%\n", x, freq, percentage, diffPercentage);
Assert.assertTrue(Math.abs((freq - avgRound) * 1.0 / avgRound) <= 0.01); // differ <= 0.01, means <= 1 / 100,
}
// empty tree,
Assert.assertNull(ebst.randomValue());
}
}
(所有测试用例都会通过。)
测试方法的输出testRandomValue():
tree size: 100, total round: 26214400, result:
random value: 0, chosen count: 262162, percentage: 1.0001 %, differ: 0.0001 %
random value: 1, chosen count: 262166, percentage: 1.0001 %, differ: 0.0001 %
random value: 2, chosen count: 262897, percentage: 1.0029 %, differ: 0.0029 %
random value: 3, chosen count: 261887, percentage: 0.9990 %, differ: -0.0010 %
random value: 4, chosen count: 262428, percentage: 1.0011 %, differ: 0.0011 %
random value: 5, chosen count: 262094, percentage: 0.9998 %, differ: -0.0002 %
random value: 6, chosen count: 261662, percentage: 0.9982 %, differ: -0.0018 %
random value: 7, chosen count: 262034, percentage: 0.9996 %, differ: -0.0004 %
random value: 8, chosen count: 261218, percentage: 0.9965 %, differ: -0.0035 %
random value: 9, chosen count: 262054, percentage: 0.9997 %, differ: -0.0003 %
random value: 10, chosen count: 261821, percentage: 0.9988 %, differ: -0.0012 %
random value: 11, chosen count: 262401, percentage: 1.0010 %, differ: 0.0010 %
random value: 12, chosen count: 262056, percentage: 0.9997 %, differ: -0.0003 %
random value: 13, chosen count: 262119, percentage: 0.9999 %, differ: -0.0001 %
random value: 14, chosen count: 261878, percentage: 0.9990 %, differ: -0.0010 %
random value: 15, chosen count: 262191, percentage: 1.0002 %, differ: 0.0002 %
random value: 16, chosen count: 261224, percentage: 0.9965 %, differ: -0.0035 %
random value: 17, chosen count: 262471, percentage: 1.0012 %, differ: 0.0012 %
random value: 18, chosen count: 261906, percentage: 0.9991 %, differ: -0.0009 %
random value: 19, chosen count: 262752, percentage: 1.0023 %, differ: 0.0023 %
random value: 20, chosen count: 262762, percentage: 1.0024 %, differ: 0.0024 %
random value: 21, chosen count: 262245, percentage: 1.0004 %, differ: 0.0004 %
random value: 22, chosen count: 261942, percentage: 0.9992 %, differ: -0.0008 %
random value: 23, chosen count: 262339, percentage: 1.0007 %, differ: 0.0007 %
random value: 24, chosen count: 262266, percentage: 1.0005 %, differ: 0.0005 %
random value: 25, chosen count: 261584, percentage: 0.9979 %, differ: -0.0021 %
random value: 26, chosen count: 263036, percentage: 1.0034 %, differ: 0.0034 %
random value: 27, chosen count: 261412, percentage: 0.9972 %, differ: -0.0028 %
random value: 28, chosen count: 262305, percentage: 1.0006 %, differ: 0.0006 %
random value: 29, chosen count: 261236, percentage: 0.9965 %, differ: -0.0035 %
random value: 30, chosen count: 261681, percentage: 0.9982 %, differ: -0.0018 %
random value: 31, chosen count: 262829, percentage: 1.0026 %, differ: 0.0026 %
random value: 32, chosen count: 262411, percentage: 1.0010 %, differ: 0.0010 %
random value: 33, chosen count: 263766, percentage: 1.0062 %, differ: 0.0062 %
random value: 34, chosen count: 262448, percentage: 1.0012 %, differ: 0.0012 %
random value: 35, chosen count: 262074, percentage: 0.9997 %, differ: -0.0003 %
random value: 36, chosen count: 261986, percentage: 0.9994 %, differ: -0.0006 %
random value: 37, chosen count: 261971, percentage: 0.9993 %, differ: -0.0007 %
random value: 38, chosen count: 262403, percentage: 1.0010 %, differ: 0.0010 %
random value: 39, chosen count: 261510, percentage: 0.9976 %, differ: -0.0024 %
random value: 40, chosen count: 262020, percentage: 0.9995 %, differ: -0.0005 %
random value: 41, chosen count: 262410, percentage: 1.0010 %, differ: 0.0010 %
random value: 42, chosen count: 261910, percentage: 0.9991 %, differ: -0.0009 %
random value: 43, chosen count: 262240, percentage: 1.0004 %, differ: 0.0004 %
random value: 44, chosen count: 261923, percentage: 0.9992 %, differ: -0.0008 %
random value: 45, chosen count: 261856, percentage: 0.9989 %, differ: -0.0011 %
random value: 46, chosen count: 262708, percentage: 1.0022 %, differ: 0.0022 %
random value: 47, chosen count: 262695, percentage: 1.0021 %, differ: 0.0021 %
random value: 48, chosen count: 262882, percentage: 1.0028 %, differ: 0.0028 %
random value: 49, chosen count: 262596, percentage: 1.0017 %, differ: 0.0017 %
random value: 50, chosen count: 262872, percentage: 1.0028 %, differ: 0.0028 %
random value: 51, chosen count: 262343, percentage: 1.0008 %, differ: 0.0008 %
random value: 52, chosen count: 261969, percentage: 0.9993 %, differ: -0.0007 %
random value: 53, chosen count: 261301, percentage: 0.9968 %, differ: -0.0032 %
random value: 54, chosen count: 262206, percentage: 1.0002 %, differ: 0.0002 %
random value: 55, chosen count: 261923, percentage: 0.9992 %, differ: -0.0008 %
random value: 56, chosen count: 262577, percentage: 1.0017 %, differ: 0.0017 %
random value: 57, chosen count: 262308, percentage: 1.0006 %, differ: 0.0006 %
random value: 58, chosen count: 262600, percentage: 1.0017 %, differ: 0.0017 %
random value: 59, chosen count: 261682, percentage: 0.9982 %, differ: -0.0018 %
random value: 60, chosen count: 261983, percentage: 0.9994 %, differ: -0.0006 %
random value: 61, chosen count: 262450, percentage: 1.0012 %, differ: 0.0012 %
random value: 62, chosen count: 263582, percentage: 1.0055 %, differ: 0.0055 %
random value: 63, chosen count: 261755, percentage: 0.9985 %, differ: -0.0015 %
random value: 64, chosen count: 262773, percentage: 1.0024 %, differ: 0.0024 %
random value: 65, chosen count: 261581, percentage: 0.9979 %, differ: -0.0021 %
random value: 66, chosen count: 262071, percentage: 0.9997 %, differ: -0.0003 %
random value: 67, chosen count: 262053, percentage: 0.9997 %, differ: -0.0003 %
random value: 68, chosen count: 261491, percentage: 0.9975 %, differ: -0.0025 %
random value: 69, chosen count: 261840, percentage: 0.9988 %, differ: -0.0012 %
random value: 70, chosen count: 261837, percentage: 0.9988 %, differ: -0.0012 %
random value: 71, chosen count: 262293, percentage: 1.0006 %, differ: 0.0006 %
random value: 72, chosen count: 261928, percentage: 0.9992 %, differ: -0.0008 %
random value: 73, chosen count: 260978, percentage: 0.9956 %, differ: -0.0044 %
random value: 74, chosen count: 262260, percentage: 1.0004 %, differ: 0.0004 %
random value: 75, chosen count: 262151, percentage: 1.0000 %, differ: 0.0000 %
random value: 76, chosen count: 262981, percentage: 1.0032 %, differ: 0.0032 %
random value: 77, chosen count: 261602, percentage: 0.9979 %, differ: -0.0021 %
random value: 78, chosen count: 261938, percentage: 0.9992 %, differ: -0.0008 %
random value: 79, chosen count: 262335, percentage: 1.0007 %, differ: 0.0007 %
random value: 80, chosen count: 262213, percentage: 1.0003 %, differ: 0.0003 %
random value: 81, chosen count: 262336, percentage: 1.0007 %, differ: 0.0007 %
random value: 82, chosen count: 262356, percentage: 1.0008 %, differ: 0.0008 %
random value: 83, chosen count: 261782, percentage: 0.9986 %, differ: -0.0014 %
random value: 84, chosen count: 262610, percentage: 1.0018 %, differ: 0.0018 %
random value: 85, chosen count: 261772, percentage: 0.9986 %, differ: -0.0014 %
random value: 86, chosen count: 261874, percentage: 0.9990 %, differ: -0.0010 %
random value: 87, chosen count: 262319, percentage: 1.0007 %, differ: 0.0007 %
random value: 88, chosen count: 262144, percentage: 1.0000 %, differ: 0.0000 %
random value: 89, chosen count: 261808, percentage: 0.9987 %, differ: -0.0013 %
random value: 90, chosen count: 261980, percentage: 0.9994 %, differ: -0.0006 %
random value: 91, chosen count: 261742, percentage: 0.9985 %, differ: -0.0015 %
random value: 92, chosen count: 261994, percentage: 0.9994 %, differ: -0.0006 %
random value: 93, chosen count: 262365, percentage: 1.0008 %, differ: 0.0008 %
random value: 94, chosen count: 261954, percentage: 0.9993 %, differ: -0.0007 %
random value: 95, chosen count: 261660, percentage: 0.9982 %, differ: -0.0018 %
random value: 96, chosen count: 263220, percentage: 1.0041 %, differ: 0.0041 %
random value: 97, chosen count: 261049, percentage: 0.9958 %, differ: -0.0042 %
random value: 98, chosen count: 262000, percentage: 0.9995 %, differ: -0.0005 %
random value: 99, chosen count: 262692, percentage: 1.0021 %, differ: 0.0021 %
===============================================
Default Suite
Total tests run: 1, Failures: 0, Skips: 0
===============================================
相关class&接口：
BST是一个简单的二叉树实现。BSTNode 是 BST 的节点实现，包含字段：value / left / right.
RandomBSTDesign 是 RandomBST.
RandomBSTDesign$RandomBSTNodeDesign 是 RandomBST$RandomBSTNode.
RandomBST是随机bst impl，extends BST，主要是重写add()/delete()方法维护parent/size 字段。
RandomBST$RandomBSTNode 是 RandomBST 的节点实现，扩展 BSTNode，并添加字段：parent / size.
CreateMinimalBST是一个帮助构建最小高度的二叉搜索树的工具。
我的树class:
public class BT<E>{
E value;
BT<E> left, right;
public BT(E value)
{
this.value=value;
}
public BT (E value, BT left, BT right)
{
this.value = value;
this.left = left;
this.right = right;
}
生成树后如何从树中返回随机节点？我知道我生成的每棵树的深度和节点数。
所以使用随机整数方法和return一个介于0和树大小之间的整数。
然后在树上进行广度/深度优先遍历，使用计数器，return到达随机整数时节点。
Random rand = new Random();
int randomNum = rand.nextInt(treesize);
int count = -1;
Node randNode;
public static void getRandomTraversal(Node root){
count++;
if(count == randomNum)
randNode = root;
if(root.leftChild != null)
getRandomTraversal(root.leftChild);
if(root.rightChild != null)
getRandomTraversal(root.rightChild);
}
或者，您可以删除 count 作为全局变量并将其添加为递归函数的参数。虽然当树有多个 child.
时，这对于二叉树来说并不那么容易- Select一个随机数(
new Random().nextInt(numberOfNodes)) - 随心所欲地遍历树（深度优先，广度优先，后序，中序，前序）
- 对于您访问的每个节点，增加一个计数器
- 如果计数器的值等于随机选择的数字，则选择该节点
Dennis 和 Jeroen 的算法实现起来很简单，但是 O(n)。我相信我有一个稍微复杂一点的 O(log n) 算法。
每个节点都需要均等的被选中机会。所以在某棵树 T 中，令 LN(T) 为左树中的节点数，RN(T) 为右树中的节点数，N(T) 为节点数节点总数，包括这个（所以 N(T) = 1 + LN(T) + RN(T)）。 Select 来自 0 to N(T) - 1 的随机数 R。如R == 0、return这个节点。如果1 <= R <= LT(N)，在左子树上递归这个方法。否则，在右子树上递归此方法。
未经测试的代码（假设 BT 有一个 .size() 方法适用于 O(1)）：
public BT randomNode() {
int r = new Random().nextInt(this.size());
if (r == 0) {
return this;
} else if (left != null && 1 <= r && r <= left.size()) {
return left.randomNode();
} else {
return right.randomNode();
}
}
当然你可以做一些事情，比如从方法中提升 new Random() 但算法是一样的。
编辑：修复了左子树为空时的空指针异常。
首先
问题也出自书籍 <Cracking the coding interview 6th>，在部分：IX Interview Questions | 4. Trees and graphs | Question 4.11.
（Gayle Laakmann McDowell的一本好书，他是Google的软件工程师，采访过很多人。）
算法
(A) 随机数决定，记录子树大小
逻辑：
实现二叉树节点。
- 每个节点都有一个大小字段。
指示以此节点为根的子树大小。 - 如果每个节点都有一个指向其父节点的父字段，这会有所帮助。
- 每个节点都有一个大小字段。
实现二叉树，最好是BST。
- 插入/删除时，维护节点的大小和父字段。
BSTNode getRandomNode(BSTNode current, int rand)
将 rand 与子树大小进行比较：Node<T> left = current.getLeft(); // left, int leftSize = (left == null ? 0 : left.getSize()); // get size of left subtree, if (rand == leftSize) return current; // current is chosen, if (rand < leftSize) return randomNode(current.getLeft(), rand); // call on left subtree recursively, else return randomNode(current.getRight(), rand - leftSize - 1); // call on right subtree recursively,- T getRandomNode(BST树)
- 如果树为空，return null。
- 生成一个随机数，范围为
[0, size)。 - 调用
getRandomNode(tree.getRoot(), rand)，获取随机节点。 - Return 随机节点的值。
复杂度：
- 时间：
O(h) - Space:
O(1), (方法堆栈使用O(h))
其中：
h是树的高度。
(B) 放入链表，随机索引访问
逻辑：
- 将树节点添加到列表中，支持通过索引快速访问。
- 调用该方法时，在
[0, size)范围内生成一个随机索引，然后获取给定索引处的节点。
复杂度：
时间：
O(1)（如果树是静态的）Space:
O(n)
其中：
n是树的大小。
提示：
- 如果树是动态的，那么树变化时也需要维护数组。
- 当一个节点从树中移除时，也需要从数组中移除。
这也需要O(n). - 当一个节点添加到树中时，也需要追加到数组中。
如果末尾有空 space，则需要O(1)，但在调整数组大小时，它是O(n)。
- 当一个节点从树中移除时，也需要从数组中移除。
比较两种算法：
- 对于动态树，
A使用的内存更少，运行速度更快。肯定是赢家。 - 对于静态树，也可以考虑
B，在构建数组后循环时可能会更快。
代码
（以下是Java中使用上述算法A的实现，带有测试用例。）
RandomBST.java
import java.util.concurrent.ThreadLocalRandom;
/**
* Random BST impl.
*
* @param <T>
* @author eric
* @date 2/10/19 5:02 PM
*/
public class RandomBST<T extends Comparable> extends BST<T> implements RandomBSTDesign<T> {
@Override
public void add(T v) {
root = add((RandomBSTNode<T>) root, v, (RandomBSTNode<T>) root);
}
/**
* Add to a subtree start from given node.
*
* @param current root of a subtree to add node to,
* @param currentParent parent of current,
* @param v
* @return the new root of subtree,
*/
protected RandomBSTNode<T> add(RandomBSTNode<T> current, T v, RandomBSTNode<T> currentParent) {
if (current == null) { // subtree is empty,
RandomBSTNode<T> newNode = new RandomBSTNode<>(v, currentParent); // create new node,
newNode.incSizeOfParents(); // increase size of parents,
size++;
return newNode;
}
// compare,
int compareFlag = v.compareTo(current.value);
// check this or subtree,
if (compareFlag < 0) { // smaller, go to left subtree,
current.left = add(current.getLeft(), v, current);
} else if (compareFlag > 0) { // larger, go to right subtree,
current.right = add(current.getRight(), v, current);
} else { // equals, ignore it,
}
return current;
}
@Override
protected RandomBSTNode<T> delete(BSTNode<T> current, T v) {
return delete((RandomBSTNode<T>) current, v); // cast to subtype to call another method,
}
/**
* Delete given value in subtree, if any.
*
* @param current
* @param v
* @return new root of the subtree
*/
protected RandomBSTNode<T> delete(RandomBSTNode<T> current, T v) {
if (current == null) return null;
// compare,
int compareFlag = v.compareTo(current.value);
// check this or subtree,
if (compareFlag < 0) { // smaller, go to left subtree,
current.left = delete(current.left, v);
} else if (compareFlag > 0) { // larger, go to right subtree,
current.right = delete(current.right, v);
} else { // equals, delete it,
// no child,
if (current.left == null && current.right == null) {
current.decSizeOfParents(); // decrease size of parents,
size--;
return null;
}
// one child - right,
if (current.left == null) {
current.decSizeOfParents(); // decrease size of parents,
size--;
RandomBSTNode<T> randomRight = current.getRight(); // cast to subtype,
randomRight.parent = current.parent;
return randomRight;
}
// one child - left,
if (current.right == null) {
current.decSizeOfParents(); // decrease size of parents,
size--;
RandomBSTNode<T> randomLeft = (RandomBSTNode<T>) current.left; // cast to subtype,
randomLeft.parent = current.parent;
return randomLeft;
}
// 2 child,
T smallestInRight = findSmallestValue(current.right);
current.value = smallestInRight; // replace current with smallest in right subtree,
current.right = delete(current.right, smallestInRight); // delete original smallest value in right subtree,
}
return current;
}
@Override
public RandomBSTNode<T> getRoot() {
return (RandomBSTNode<T>) root;
}
@Override
public T randomValue() {
if (size == 0) return null; // empty tree,
int rand = ThreadLocalRandom.current().nextInt(size); // random value,
RandomBSTNode rnode = randomNode(getRoot(), rand); // get random node,
// System.out.printf("rand = %d, random node: %s\n", rand, rnode);
return rnode == null ? null : (T) rnode.value;
}
protected RandomBSTNode randomNode(RandomBSTNode<T> current, int rand) {
RandomBSTNode<T> left = current.getLeft(); // left,
int leftSize = (left == null ? 0 : left.getSize()); // get size of left subtree,
if (rand == leftSize) return current; // current is chosen,
if (rand < leftSize) return randomNode(current.getLeft(), rand); // call on left subtree recursively,
else return randomNode(current.getRight(), rand - leftSize - 1); // call on right subtree recursively,
}
/**
* Random BST node impl.
*
* @param <T>
*/
static class RandomBSTNode<T extends Comparable> extends BSTNode<T> implements RandomBSTNodeDesign<T> {
protected int size; // size of subtree which has this node as root,
protected RandomBSTNode<T> parent; // parent of this node, or null if this is root,
public RandomBSTNode(T value, RandomBSTNode<T> parent) {
this(value, 1, parent); // on creation, got size 1,
}
public RandomBSTNode(T value, int size, RandomBSTNode<T> parent) {
super(value);
this.size = size;
this.parent = parent;
}
@Override
public int incSize() {
return ++size;
}
@Override
public int decSize() {
return --size;
}
@Override
public void incSizeOfParents() {
RandomBSTNode<T> pn = parent;
while (pn != null) {
pn.incSize();
pn = pn.parent;
}
}
@Override
public void decSizeOfParents() {
RandomBSTNode<T> pn = parent;
while (pn != null) {
pn.decSize();
pn = pn.parent;
}
}
@Override
public boolean isRoot() {
return parent == null;
}
@Override
public RandomBSTNode<T> getLeft() {
return (RandomBSTNode<T>) left;
}
@Override
public RandomBSTNode<T> getRight() {
return (RandomBSTNode<T>) right;
}
@Override
public int getSize() {
return size;
}
@Override
public RandomBSTNode getParent() {
return parent;
}
@Override
protected void appendMoreToString(StringBuilder sb) {
sb.append(", size = ").append(size); // size,
sb.append(", parent value = ").append(parent == null ? null : parent.getValue()); // parent,
}
/*------ unsupported methods ------*/
@Override
void setLeft(BSTNode<T> left) {
throw new UnsupportedOperationException("Should not set subtree directly, because size is difficult to maintain.");
}
@Override
void setRight(BSTNode<T> right) {
throw new UnsupportedOperationException("Should not set subtree directly, because size is difficult to maintain.");
}
}
}
RandomBSTTest.java (部分)
（单元测试，通过TestNG）
import org.testng.Assert;
import org.testng.annotations.BeforeMethod;
import org.testng.annotations.Test;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.function.Consumer;
/**
* RandomBST test.
*
* @author eric
* @date 2/10/19 5:50 PM
*/
public class RandomBSTTest {
private int n = 100;
private int avgRound = (1 << 18); // avg round for each node, when get random value,
private RandomBST<Integer> mbst; // minimal BST,
private RandomBST<Integer> ebst; // empty BST,
@BeforeMethod
public void init() {
// init minimal BST,
mbst = CreateMinimalBST.createRandomFromNumRange(0, n);
// init empty BST,
ebst = new RandomBST<>();
}
// other non-random related test cases are removed,
// randomValue()
@Test
public void testRandomValue() {
int round = n * avgRound; // total round,
System.out.printf("tree size: %d, total round: %d, result:\n", n, round);
Map<Integer, Integer> freqMap = new LinkedHashMap<>();
// init map,
for (int i = 0; i < n; i++) {
freqMap.put(i, 0);
}
// get random value & count frequency,
for (int i = 0; i < round; i++) {
int rv = mbst.randomValue();
freqMap.put(rv, freqMap.get(rv) + 1);
}
double avgPercentage = 100 / n; // average percentage,
// print result,
for (int x : freqMap.keySet()) {
int freq = freqMap.get(x);
double percentage = freq * 100.0 / round;
double diffPercentage = percentage - avgPercentage;
System.out.printf("\trandom value: %2d, chosen count: %d, percentage: %.4f %%, differ: %.4f %%\n", x, freq, percentage, diffPercentage);
Assert.assertTrue(Math.abs((freq - avgRound) * 1.0 / avgRound) <= 0.01); // differ <= 0.01, means <= 1 / 100,
}
// empty tree,
Assert.assertNull(ebst.randomValue());
}
}
(所有测试用例都会通过。)
测试方法的输出testRandomValue():
tree size: 100, total round: 26214400, result:
random value: 0, chosen count: 262162, percentage: 1.0001 %, differ: 0.0001 %
random value: 1, chosen count: 262166, percentage: 1.0001 %, differ: 0.0001 %
random value: 2, chosen count: 262897, percentage: 1.0029 %, differ: 0.0029 %
random value: 3, chosen count: 261887, percentage: 0.9990 %, differ: -0.0010 %
random value: 4, chosen count: 262428, percentage: 1.0011 %, differ: 0.0011 %
random value: 5, chosen count: 262094, percentage: 0.9998 %, differ: -0.0002 %
random value: 6, chosen count: 261662, percentage: 0.9982 %, differ: -0.0018 %
random value: 7, chosen count: 262034, percentage: 0.9996 %, differ: -0.0004 %
random value: 8, chosen count: 261218, percentage: 0.9965 %, differ: -0.0035 %
random value: 9, chosen count: 262054, percentage: 0.9997 %, differ: -0.0003 %
random value: 10, chosen count: 261821, percentage: 0.9988 %, differ: -0.0012 %
random value: 11, chosen count: 262401, percentage: 1.0010 %, differ: 0.0010 %
random value: 12, chosen count: 262056, percentage: 0.9997 %, differ: -0.0003 %
random value: 13, chosen count: 262119, percentage: 0.9999 %, differ: -0.0001 %
random value: 14, chosen count: 261878, percentage: 0.9990 %, differ: -0.0010 %
random value: 15, chosen count: 262191, percentage: 1.0002 %, differ: 0.0002 %
random value: 16, chosen count: 261224, percentage: 0.9965 %, differ: -0.0035 %
random value: 17, chosen count: 262471, percentage: 1.0012 %, differ: 0.0012 %
random value: 18, chosen count: 261906, percentage: 0.9991 %, differ: -0.0009 %
random value: 19, chosen count: 262752, percentage: 1.0023 %, differ: 0.0023 %
random value: 20, chosen count: 262762, percentage: 1.0024 %, differ: 0.0024 %
random value: 21, chosen count: 262245, percentage: 1.0004 %, differ: 0.0004 %
random value: 22, chosen count: 261942, percentage: 0.9992 %, differ: -0.0008 %
random value: 23, chosen count: 262339, percentage: 1.0007 %, differ: 0.0007 %
random value: 24, chosen count: 262266, percentage: 1.0005 %, differ: 0.0005 %
random value: 25, chosen count: 261584, percentage: 0.9979 %, differ: -0.0021 %
random value: 26, chosen count: 263036, percentage: 1.0034 %, differ: 0.0034 %
random value: 27, chosen count: 261412, percentage: 0.9972 %, differ: -0.0028 %
random value: 28, chosen count: 262305, percentage: 1.0006 %, differ: 0.0006 %
random value: 29, chosen count: 261236, percentage: 0.9965 %, differ: -0.0035 %
random value: 30, chosen count: 261681, percentage: 0.9982 %, differ: -0.0018 %
random value: 31, chosen count: 262829, percentage: 1.0026 %, differ: 0.0026 %
random value: 32, chosen count: 262411, percentage: 1.0010 %, differ: 0.0010 %
random value: 33, chosen count: 263766, percentage: 1.0062 %, differ: 0.0062 %
random value: 34, chosen count: 262448, percentage: 1.0012 %, differ: 0.0012 %
random value: 35, chosen count: 262074, percentage: 0.9997 %, differ: -0.0003 %
random value: 36, chosen count: 261986, percentage: 0.9994 %, differ: -0.0006 %
random value: 37, chosen count: 261971, percentage: 0.9993 %, differ: -0.0007 %
random value: 38, chosen count: 262403, percentage: 1.0010 %, differ: 0.0010 %
random value: 39, chosen count: 261510, percentage: 0.9976 %, differ: -0.0024 %
random value: 40, chosen count: 262020, percentage: 0.9995 %, differ: -0.0005 %
random value: 41, chosen count: 262410, percentage: 1.0010 %, differ: 0.0010 %
random value: 42, chosen count: 261910, percentage: 0.9991 %, differ: -0.0009 %
random value: 43, chosen count: 262240, percentage: 1.0004 %, differ: 0.0004 %
random value: 44, chosen count: 261923, percentage: 0.9992 %, differ: -0.0008 %
random value: 45, chosen count: 261856, percentage: 0.9989 %, differ: -0.0011 %
random value: 46, chosen count: 262708, percentage: 1.0022 %, differ: 0.0022 %
random value: 47, chosen count: 262695, percentage: 1.0021 %, differ: 0.0021 %
random value: 48, chosen count: 262882, percentage: 1.0028 %, differ: 0.0028 %
random value: 49, chosen count: 262596, percentage: 1.0017 %, differ: 0.0017 %
random value: 50, chosen count: 262872, percentage: 1.0028 %, differ: 0.0028 %
random value: 51, chosen count: 262343, percentage: 1.0008 %, differ: 0.0008 %
random value: 52, chosen count: 261969, percentage: 0.9993 %, differ: -0.0007 %
random value: 53, chosen count: 261301, percentage: 0.9968 %, differ: -0.0032 %
random value: 54, chosen count: 262206, percentage: 1.0002 %, differ: 0.0002 %
random value: 55, chosen count: 261923, percentage: 0.9992 %, differ: -0.0008 %
random value: 56, chosen count: 262577, percentage: 1.0017 %, differ: 0.0017 %
random value: 57, chosen count: 262308, percentage: 1.0006 %, differ: 0.0006 %
random value: 58, chosen count: 262600, percentage: 1.0017 %, differ: 0.0017 %
random value: 59, chosen count: 261682, percentage: 0.9982 %, differ: -0.0018 %
random value: 60, chosen count: 261983, percentage: 0.9994 %, differ: -0.0006 %
random value: 61, chosen count: 262450, percentage: 1.0012 %, differ: 0.0012 %
random value: 62, chosen count: 263582, percentage: 1.0055 %, differ: 0.0055 %
random value: 63, chosen count: 261755, percentage: 0.9985 %, differ: -0.0015 %
random value: 64, chosen count: 262773, percentage: 1.0024 %, differ: 0.0024 %
random value: 65, chosen count: 261581, percentage: 0.9979 %, differ: -0.0021 %
random value: 66, chosen count: 262071, percentage: 0.9997 %, differ: -0.0003 %
random value: 67, chosen count: 262053, percentage: 0.9997 %, differ: -0.0003 %
random value: 68, chosen count: 261491, percentage: 0.9975 %, differ: -0.0025 %
random value: 69, chosen count: 261840, percentage: 0.9988 %, differ: -0.0012 %
random value: 70, chosen count: 261837, percentage: 0.9988 %, differ: -0.0012 %
random value: 71, chosen count: 262293, percentage: 1.0006 %, differ: 0.0006 %
random value: 72, chosen count: 261928, percentage: 0.9992 %, differ: -0.0008 %
random value: 73, chosen count: 260978, percentage: 0.9956 %, differ: -0.0044 %
random value: 74, chosen count: 262260, percentage: 1.0004 %, differ: 0.0004 %
random value: 75, chosen count: 262151, percentage: 1.0000 %, differ: 0.0000 %
random value: 76, chosen count: 262981, percentage: 1.0032 %, differ: 0.0032 %
random value: 77, chosen count: 261602, percentage: 0.9979 %, differ: -0.0021 %
random value: 78, chosen count: 261938, percentage: 0.9992 %, differ: -0.0008 %
random value: 79, chosen count: 262335, percentage: 1.0007 %, differ: 0.0007 %
random value: 80, chosen count: 262213, percentage: 1.0003 %, differ: 0.0003 %
random value: 81, chosen count: 262336, percentage: 1.0007 %, differ: 0.0007 %
random value: 82, chosen count: 262356, percentage: 1.0008 %, differ: 0.0008 %
random value: 83, chosen count: 261782, percentage: 0.9986 %, differ: -0.0014 %
random value: 84, chosen count: 262610, percentage: 1.0018 %, differ: 0.0018 %
random value: 85, chosen count: 261772, percentage: 0.9986 %, differ: -0.0014 %
random value: 86, chosen count: 261874, percentage: 0.9990 %, differ: -0.0010 %
random value: 87, chosen count: 262319, percentage: 1.0007 %, differ: 0.0007 %
random value: 88, chosen count: 262144, percentage: 1.0000 %, differ: 0.0000 %
random value: 89, chosen count: 261808, percentage: 0.9987 %, differ: -0.0013 %
random value: 90, chosen count: 261980, percentage: 0.9994 %, differ: -0.0006 %
random value: 91, chosen count: 261742, percentage: 0.9985 %, differ: -0.0015 %
random value: 92, chosen count: 261994, percentage: 0.9994 %, differ: -0.0006 %
random value: 93, chosen count: 262365, percentage: 1.0008 %, differ: 0.0008 %
random value: 94, chosen count: 261954, percentage: 0.9993 %, differ: -0.0007 %
random value: 95, chosen count: 261660, percentage: 0.9982 %, differ: -0.0018 %
random value: 96, chosen count: 263220, percentage: 1.0041 %, differ: 0.0041 %
random value: 97, chosen count: 261049, percentage: 0.9958 %, differ: -0.0042 %
random value: 98, chosen count: 262000, percentage: 0.9995 %, differ: -0.0005 %
random value: 99, chosen count: 262692, percentage: 1.0021 %, differ: 0.0021 %
===============================================
Default Suite
Total tests run: 1, Failures: 0, Skips: 0
===============================================
相关class&接口：
BST是一个简单的二叉树实现。BSTNode是BST的节点实现，包含字段：value/left/right.RandomBSTDesign是RandomBST. 的接口
RandomBSTDesign$RandomBSTNodeDesign是RandomBST$RandomBSTNode. 的接口
RandomBST是随机bst impl，extendsBST，主要是重写add()/delete()方法维护parent/size字段。RandomBST$RandomBSTNode是RandomBST的节点实现，扩展BSTNode，并添加字段：parent/size.CreateMinimalBST是一个帮助构建最小高度的二叉搜索树的工具。