Tag: 二进制搜索树

从二叉搜索树中递归删除

这是作业; 请不要只给我代码 我有两种方法： remove(T data)和removeRec(Node node, T data) 。 在当前状态下，似乎我的代码只删除了BST的root 。 @Override public T remove(T data) { if (data == null) { throw new IllegalArgumentException(“Data is null”); } if (root == null) { throw new java.util.NoSuchElementException(“BST is empty”); } else { size–; BSTNode dummy = new BSTNode(null); return removeRec(root, data, dummy).getData(); //This is probably wrong […]

算法 – O（n）中二进制搜索树的每两个节点之间的距离之和？

问题是找出BinarySearchTree的每两个节点之间的距离总和，假设每个父子对由单位距离分开。 每次插入后都要计算。 例如： ->first node is inserted.. (root) total sum=0; ->left and right node are inserted (root) / \ (left) (right) total sum = distance(root,left)+distance(root,right)+distance(left,right); = 1 + 1 + 2 = 4 and so on….. 我提出的解决方案： 蛮力。 脚步： 执行DFS并跟踪所有节点： O(n) 。 选择每两个节点并使用最低公共祖先方法计算： O(nC2)_times_O(log(n))=O(n2log(n))之间的距离并将它们相加。 总体复杂性： -O(n2log(n)) 。 O(nlog(n)) 。 脚步：- 在插入之前执行DFS并跟踪所有节点： O(n) 。 计算插入节点与之间的距离： O(nlog(n)) […]

BST有重复

我知道， BST不允许重复。 例如，如果我有一个单词“RABSAB”。 上述字符串的二进制搜索树是： R /\ AS \ B 如果我们想在树中包含重复项，该怎么办？ 树怎么会改变？ 我在接受采访时被问到这个问题。 他们让我画画： 二叉树 不平衡的二进制搜索树 没有重复的二叉搜索树 带有重复项的二叉搜索树 任何帮助表示赞赏！ PS：通过绘制相关树帮助我

如何使用二叉搜索树实现Hashtable？

通过简单地使用以下数据结构，我能够使用数组实现Hashtable。 LinkedList<Item> table[] const int MAX_SIZE = 100 即链表列表（带链接的散列）。 现在在各种书中，他们说如果我们想要有序数据，我们可以用BST实现哈希表。 如何在BST中包含键和值。 虽然我可以像存储单个数据项一样存储这两个数据，但是键给出了一个整数，它就像一个散列函数之后的数组索引。 如何在BST中使用密钥？ 我不需要任何索引？ 我能想到的是我可以使用该function比较两个键，然后相应地进行正常插入和删除。 EDITS： 假设我从头开始有BST class Node { K key; V value; Node left; Node right; } class BinarySearchTree { Node root; } class Hashtable { BinarySearchTree bst; public void Hashtable() { bst = new BinarySearchTree(); } //hashfunction(K key) //get(K Key) //put(K key,V […]

如何指定随机数的范围？

我有二进制搜索树代码，随机插入数字。 我可以每次修改大小，但我想修改数字范围，例如：我希望随机数只是一位数或只是2位数。 我怎样才能做到这一点？ public static void main( String[ ] args ) { BinarySearchTree bst = new BinarySearchTree( ); Random random = new Random( System.currentTimeMillis() ); int[] randoms = new int[1000]; Random randGen = new Random(); for(int i = 0; i < randoms.length; i++) { bst.insert( random.nextInt( randoms.length ) ); } System.out.println( "\n sorted :" ); […]

二元搜索树插入中节点颜色的动画变化

我已经实现了二叉搜索树的显示。 这是代码，它在jpanel中绘制二叉树。 public void paint(Graphics g) { super.paint(g); System.out.println(” in paint”); Graphics2D g2 = (Graphics2D) g; g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON); int num = bst.size; int y = 25; int nodes = 1; int level = 1; int length = getWidth(); Queue q = new LinkedList(); Queue q2 = new LinkedList(); q.add(bst.root); while (num > 0) { int […]