标签: top-down

我正在O(log n)时间内实现带有插入,搜索和删除功能的红黑树.插入和搜索工作正常.但是我坚持删除.我在互联网上找到了这个ppt幻灯片,显示了RBT删除的算法:http://www.slideshare.net/piotrszymanski/red-black-trees#btnNext ,第56页起.我知道我问的有点太多但是我已经坚持了两个多星期而且我找不到问题.我理解自上而下删除的方式,你必须相应地旋转和重新着色节点,直到你找到要删除的节点的前身.当你找到这个节点 - 它是一个叶子或一个有一个右子节点的节点时,用这个节点的数据替换节点被删除数据并删除这个节点就像正常的BST删除一样,对吗？

根据我从幻灯片中学到的内容,这是我所做的代码.如果有人愿意接受它,我会非常感激!或者至少如果您认为算法比我使用的算法更好,请告诉我!

 public void delete(int element){

    if (root == null){ 
        System.out.println("Red Black Tree is Empty!");

    } else {

      Node X = root; 
      parent = null; 
      grandParent = null; 
      sibling = null; 

      if (isLeaf(X)){

          if (X.getElement() == element){
              emptyRBT();
          } 

      } else {

      if (checkIfBlack(root.getLeftChild()) && checkIfBlack(root.getRightChild())){
          root.setIsBlack(false);

          if (X.getElement() > element && X.getLeftChild() != null){ 
              X = moveLeft(X);

          } else if (X.getElement() < element && X.getRightChild() != null){
              X = moveRight(X);
          } 

          Step2(X, element); …

扩展

假设您正在查看6种基本类型的UML图(来自UML 2.0样式的元素)

1. 类图
2. 用例图
3. 状态机图
4. 活动图
5. 序列图
6. 物理图

假装你疯了,你想为你的系统绘制所有6个图表.

你会从哪开始的？那你要去哪？如果您非常清楚自己希望系统做什么,那么访问每个图表的最佳顺序是什么？

我认为你应该从物理图开始,然后按照自己的方式进行类图.自上而下,我总是说..？我错了吗？

我试图解决以下问题:

找到具有k 1位的最小n位整数c,并且是两个n位整数的总和,其中g,h位设置为1. g,h,k <= n

首先,这里的n位整数意味着我们可以使用所有n位,即max.这样一个整数的值是2^n - 1.所描述的整数可能根本不存在.很明显,这种情况k > g + h没有解决方案,g + h = k答案只是2^k - 1(第一位k是1位,k - n前面是零).

至于程序应该做什么的一些例子:

g = h = k = 4, n = 10 :
0000001111 + 0000001111 = 0000011110
15 + 15 = 30 (30 should be the output)


(4, 6, 5, 10):
0000011110 + 0000111111 = 0001011101
30 + 63 = 93

(30, 1, 1, 31): …

我了解到动态规划（DP）有两种：自上而下和自下而上。

在自顶向下中，您使用递归和记忆。在自下而上中，您只需填充一个数组（一个表）。

此外，这两种方法都使用相同的时间复杂度。就我个人而言，我发现自上而下的方法更容易、更自然地遵循。给定的 DP 问题是否可以使用这两种方法中的任何一种来解决？或者我是否会遇到只能通过两种方法之一解决的问题？