二分搜索数的rank，老师给说下思路

# 具体遇到的问题

# 报错信息的截图

# 相关课程内容截图

# 尝试过的解决思路和结果

# 粘贴全部相关代码，切记添加代码注释（请勿截图）

在这里输入代码，可通过选择【代码语言】突出显示

rank(e){
    rank(,e,);
}
rank(Node node,e,dept){
    (==node) -;
    (node..compareTo(e)<){
      rank(node.,e,++dept);
    }
    (node..compareTo(e)==){
        -dept;
    }
   rank(node.,e,++dept);
}

学无止境呀呀呀 2020-10-23

源自：二分搜索树 2-1 集合基础和基于二分搜索树的集合实现

收起

2回答

liuyubobobo 回答被采纳获得+3积分 2020-10-24 10:49:57

rank 的大体逻辑上，如果当前节点比要寻找的元素小，往右子树找，rank 值需要把左子树和自己的节点总数添加上；

如果当前节点比要寻找的元素大，直接往左边找就可以，不需要求 floor。

另外，你的代码对于 Node 中 sz 的维护可能有问题。我写了一版代码，可以参考。另外，在代码中，也包含一个测试方式。简单来说，在一棵二分搜索树中，包含 1-n 共 n 个元素，那么元素 i 的 rank 值就应该是 i。

https://git.imooc.com/class-105/Play-Algorithms-and-Data-Structures/src/master/15-Binary-Search-Tree/Optional-02-Rank/src/BST.java

继续加油！：）

收起回答

liuyubobobo 2020-10-23 11:14:52

每个节点需要记录以这个节点为根节点的子树有多少个元素。一个节点的 rank 值就是这个节点的左子树的节点个数 + 1。

继续加油！：）

收起回答

提问者学无止境呀呀呀 #1

是这样么？ public int rank(E e){ return rank(root,e); } private int rank(Node node,E e){ if (node==null)return -1; if (node.data.compareTo(e)==0){ return node.left==null?1:node.left.size+1; } if (node.data.compareTo(e)<0){ return rank(node.right,e); } Node tempNode = floor(node.left, e); if( tempNode != null ) return tempNode.left.size+1; return node.left==null?1:node.left.size+1; } private Node add(E e,Node node){ if (node==null){ node=new Node(e); return node; } if (node.data.compareTo(e)<0){ node.right=add(e,node.right); node.size++; }else if (node.data.compareTo(e)>0){ node.left=add(e,node.left); node.size++; } return node; } private class Node{ public E data; private Node left; private Node right; private int size=0; public Node(E e,Node node){ this.data=e; this.right=node.right; this.left=node.left; } public Node(E e){ this.data=e; this.right=null; this.left=null; this.size++; } public Node(){ this.data=null; this.right=null; this.left=null; } }

2020-10-23 22:27:16