java - 为什么我的 BST 的平均身高这么高?
问题描述
我目前正在从事一个 uni 项目,并且我的二叉搜索树有些困难,每个节点都必须有一个值,但如果一个节点的余额值大于父母则需要根据孩子坐的一侧向左或向右旋转树。
public class RandomBST {
class Node {
int x;
double balanceValue;
Node parent;
Node LChild;
Node RChild;
public Node(int i, double b) {
x = i;
balanceValue = b;
parent = this;
LChild = RChild = null;
}
}
Node root;
public double randomDouble() {
Random Ran = new Random();
return (0 + (1 - 0) * Ran.nextDouble());
}
public void insert(int i) {
double b = randomDouble();
root = Rec_insert(root, i, b);
Node p = findParent(root,i,-1);
if (p.balanceValue < b ){
if (p.x > i){
rotateLeft();
}else{
rotateRight();
}
}
}
Node Rec_insert(Node root, int i, double b) {
if (root == null) {
root = new Node(i, b);
return root;
}
if (i < root.x)
root.LChild = Rec_insert(root.LChild, i, b);
else if (i > root.x)
root.RChild = Rec_insert(root.RChild, i, b);
return root;
}
static Node findParent(Node node,int i, int parent) {
if (node == null)
return null;
if (node.x == i) {
return node.parent;
} else {
findParent(node.LChild, i, node.x);
findParent(node.RChild, i, node.x);
}
return node.parent;
}
int findMax(int a, int b){
if(a >= b)
return a;
else
return b;
}
int findHeight(Node root){
if(root == null)
return 0;
return findMax(findHeight(root.LChild), findHeight(root.RChild)) + 1;
}
public void rotateRight(){
Node previoius = root;
if (root.RChild!=null){
root = root.RChild;
}
previoius.RChild = root.LChild;
root.LChild = previoius;
}
public void rotateLeft(){
Node previoius = root;
if (root.LChild!=null){
root = root.LChild;
}
previoius.LChild = root.RChild;
root.RChild = previoius;
}
public static void main(String[] args) {
int total = 0;
for (int j = 0; j<1000;j++) {
RandomBST RBST = new RandomBST();
for (int i = 0; i < 1000; i++) {
RBST.insert(i);
}
int height = RBST.findHeight(RBST.root);
total =total + height;
}
System.out.println(total/1000);
}
}
任何关于我在哪里出错的建议都很棒,输出应该在 20 到 21 左右,但我得到了 850 左右。
解决方案
制作一个全新的随机数生成器
Random Ran = new Random();
可能会使您的随机数...有点随机。
在您的应用程序中创建一个生成器并将所有调用定向到它。
推荐阅读
- mysql - 是否有一个 MySQL 查询来查找多个字段的最佳匹配?
- php - 如何将html href按钮放在php代码中
- gradle - 使实现依赖在另一个子模块中可用
- python - Python端口扫描器在使用for循环和范围函数时将每个端口标记为关闭
- signal-processing - 负幅值的快速傅里叶变换
- python-3.x - 读取文件并计算python中列中的单词
- angular - 如何根据一个select选项确定剩下的select需要绑定的值?
- c - 使用管道,从父进程中读取 2 个数字,子进程计算它们的总和并为父进程提供打印结果
- mongodb - 在Mongodb中,主键(IDHACK)和辅助键(IXSCAN)的工作流程有什么区别?
- html - 如何在网站中使用 html 和 css 使用没有背景的图像(即使它不应该有白色背景)