rank, select, floor, ceil实现和depth size count维护的BST

Question

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165

public class ExtendsBST<E extends Comparable<E>> {     private class Node {         public E e;         public Node left, right;         public int size, depth, count;         public Node(E e) { this.e = e; size = 1; count = 1; depth = 1; }         @Override         public String toString() { return e.toString(); }     }       private Node root;     private int size;       public ExtendsBST() { root = null; size = 0; }       public void add(E e) {         if (root == null) {             root = new Node(e);             return;         }           Node cur = root;         for (;;) {             int cmp = e.compareTo(cur.e);             if (cmp == 0) {                 cur.count++;                 break;             }             if (cmp < 0 && cur.left == null) {                 cur.left = new Node(e);                 size ++;                 return;             } else if(cmp > 0 && cur.right == null) {// e.compareTo(cur.e) > 0                 cur.right = new Node(e);                 size ++;                 return;             }               if (cmp < 0)                 cur = cur.left;             else // cmp > 0, 相等已经被for语句过滤了                 cur = cur.right;             cur.size ++;             cur.depth ++;         }     }       public E floor(E e) {         Node minNode = floor(root, e);         return minNode == null ? null : minNode.e;       }     private Node floor(Node node, E e) {         // 中序遍历得到最接近且比e小的节点         if (node == null)             return null;           int cmp = e.compareTo(node.e);         if (cmp == 0)             return node;         if (cmp < 0)             return floor(node.left, e);         Node rightNode = floor(node.right, e);         if (rightNode != null)             return rightNode;         else             return node;     }       public E ceil(E e) {         Node maxNode = ceil(root, e);         return maxNode == null ? null : maxNode.e;     }     private Node ceil(Node node, E e) {         if (node == null)             return null;           int cmp = e.compareTo(node.e);         if (cmp == 0)             return node;         if (cmp > 0)             return ceil(node.right, e);         Node leftNode = ceil(node.left, e);         if (leftNode != null)             return leftNode;         else             return node;     }         public int rank(E e) {         return rank(root, e);     }     private int rank(Node node, E e) {         if (node == null)             return 0;         int cmp = e.compareTo(node.e);         int leftSize = node.left == null ? 0 : node.left.size;         if (cmp == 0)             return leftSize + 1;         else if (cmp > 0)             return leftSize + 1 + rank(node.right, e);         else// cmp < 0             return rank(node.left, e);     }           public E select(int rank) {         if (rank >= size)             throw new IllegalArgumentException(                     String.format("select failed; rank out of bound; SIZE=%d, RANK=%d", size, rank));         return select(root, rank).e;     }     private Node select(Node node, int rank) {         if (node == null)             return null;         int t = node.left == null ? 0 : node.left.size;         if (t > rank)             return select(node.left, rank);         else if (t < rank)             return select(node.right, rank - t - 1);         else             return node;     }       @Override     public String toString() {         StringBuilder sb = new StringBuilder();         generateBSTString(root, 0, sb);         return sb.toString();     }       // 生成以node为节点,深度为depth的描述二叉树字符串     private void generateBSTString(Node node, int depth, StringBuilder sb) {         if (node == null) {             sb.append(generateDepthString(depth) + "null\n");             return;         }         sb.append(generateDepthString(depth) + node.e + "\n");         generateBSTString(node.left, depth+1 , sb);         generateBSTString(node.right, depth + 1, sb);     }       private String generateDepthString(int depth) {         StringBuilder sb = new StringBuilder();         for (int i = 0; i < depth; i ++)             sb.append("--");         return sb.toString();     }       public static void main(String[] args) {         ExtendsBST<Integer> bst = new ExtendsBST<>();         int[] nums = {5, 10, 20, 13, 56, 31, 88, 62, 19};         for (int i = 0; i < nums.length; i ++)             bst.add(nums[i]);         //System.out.println(bst.floor(21));         //System.out.println(bst.ceil(21)); //        System.out.println(bst.rank(56)); //        System.out.println(bst.rank(88)); //        System.out.println(bst.rank(2000));         System.out.println(bst.select(3));     }   }

Answer 1

liuyubobobo 2018-06-11 05:34:58

感谢分享：）继续加油！：）

• 晚上吃什么啊 #1

  感觉他这个floor是不是写的有问题

• liuyubobobo 回复 晚上吃什么啊 #2

  我没有细看，可以自己验证测试一下：）另外，我在我的课程《算法与数据结构》的官方github的补充代码中，提供过BST的floor和ceil，有兴趣可以参考：）https://github.com/liuyubobobo/Play-with-Algorithms 加油！

Answer 2

ITdoge 2018-08-27 17:49:06

看了之后觉得自己是不是没有天赋...