0

我有 2-3-4 树，但修改后只有叶子有值。我不确定叶子是否是确切的词。叶子（在我的描述中）是树底部具有最大深度的节点（这些是树末端的节点）。每个假期都有一个值。其他节点（不是叶子）具有其子节点中最小值的“值”。所以这是有效的树：

      2
    /   \
  3      2
/ | \  / | \
8 3 4  7 2  5

我需要编写一些具有最大复杂度 O(log n) 的伪代码。我必须写最小值（从树返回最小值），插入（k）（插入具有 k 值的新休假），减少键（x，k）（将列表 x 中的键更改为 k），删除（x）从树中删除休假并提取 min （删除最小值）。

我试图自己写一些东西，但我不确定我是否做得对，以及我是否满足复杂性条件。

class Node234 {
int value;
int count;
Node234 []childrens;
Node234 parent;
}

Node234 minimum()
{
  minimum(root);
}

Node234 minimum(Node234 node)
{
  if(node.count == 0)
  {
    return node;
  }

  for(i = 0; i < node.count; i++)
  {
     if(node.value == node.childrens[i].value)
        return minimum(node.childrens[i]);
  }
}

insert(int newValue)
{
  insert(newValue, root);
}

insert(int newValue, Node234 node)
{
  if(node.count == 0)
  {
    Node234 newNode = new Node234(newValue);
    insert(newNode, newValue, node);
  }
  else
  {
     insert(newValue, node.childrens[node.count-1]);
  }
}

insert(Node234 newNode, int newValue, Node234 node)
{
if(node.parent == null)
{
  Node234 newNodeParent = new Node234(newValue);
  newNodeParent.childrens[0] = node;
  node.parent = newNodeParent;
  newNodeParent.childrens[1] = newNode;
  newNode.parent = newNodeParent;
  if(node.value < newNode.value)
    newNodeParent.value = node.value;
}
else
{
  if(node.parent.count == 4) 
  {
     Node234 newNodeParent = new Node234(newValue);
     node.parent.count--;
      if(node.parent.value == node.value)
      {
         setMinForNode(node.parent);
      }
      newNodeParent.childrens[0] = node;
      node.parent = newNodeParent;
      newNodeParent.childrens[1] = newNode;
      newNode.parent = newNodeParent;

      if(node.value < newValue)
        newNodeParent.value = node.value;
      insert(newNodeParent, newNode.value, node.parent);
  }
  else
  {
    node.parent.childrens[node.parent.count] = newNode;
      node.parent.count++;
      if(newNode.value < node.parent.value)
      {
        changeAllParentKeys(newNode, newNode.value);
      }
  }
}
}

changeAllParentKeys(Node234 node, int newValue)
{
  if(node.parent != null && node.parent.value > newValue)
  {
    node.parent.value = newValue;
    changeAllParentKeys(node.parent, newValue);
  }
}

setMinForNode(Node234 parent)
{
  parent.value = parent.childrens[0].value;
  for(i = 1; i < parent.count; i++)
  {
     if(parent.value > parent.childrens[i].value)
        parent.value = parent.childrens[i].value;
  }
}

我希望最小功能可以，但是插入功能可以吗？是不是太复杂了？你能帮我满足复杂性条件吗？你能帮我处理其他功能吗（文字算法就足够了:)）。

4

0 回答 0