AVL Tree - 计数 N_Nodes 按位置打印元素 c++

Question

你好 Whosebug 成员，我是新来的，我需要你的帮助。我正在解决一个问题，我必须以最有效的方式来解决这个问题。这个程序的要点是通过某个位置读取值、删除值和打印值（那是我的问题）。我必须在其中创建（维护）一个 O(N * log(N)) 解决方案。输入就像。读取 N 行。

输入：

8 (N-> N Numbers)
INS 100 (Add 100 to the tree)
INS 200 (Add 200 to the tree)
INS 300 (Add 300 to the tree)
REM 200 (Remove the number 200 from the tree)
PER 1 (Have to output the biggest number in the tree-> Shoud print 300)
INS 1000 (Add 1000 to the tree)
PER 1 ((Have to output the biggest number in the tree-> Shoud print 1000))
PER 2 (I have to output the second biggest number so:  300)

有我的完整代码

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;

// An AVL tree node
struct node
{
    int key;
    struct node *left;
    struct node *right;
    int height;
};
// A utility function to get maximum of two integers
int max(int a, int b);
// A utility function to get height of the tree
int height(struct node *N)
{
    if (N == NULL)
            return 0;
    return N->height;
}
// A utility function to get maximum of two integers
int max(int a, int b)
{
    return (a > b)? a : b;
}
/* Helper function that allocates a new node with the given key and
    NULL left and right pointers. */
struct node* newNode(int key)
{
    struct node* node = (struct node*)
                                            malloc(sizeof(struct node));
    node->key   = key;
    node->left   = NULL;
    node->right  = NULL;
    node->height = 1;  // new node is initially added at leaf
    return(node);
}
// A utility function to right rotate subtree rooted with y
// See the diagram given above.
struct node *rightRotate(struct node *y)
{
    struct node *x = y->left;
    struct node *T2 = x->right;
    // Perform rotation
    x->right = y;
    y->left = T2;
    // Update heights
    y->height = max(height(y->left), height(y->right))+1;
    x->height = max(height(x->left), height(x->right))+1;
    // Return new root
    return x;
}
// A utility function to left rotate subtree rooted with x
// See the diagram given above.
struct node *leftRotate(struct node *x)
{
    struct node *y = x->right;
    struct node *T2 = y->left;
    // Perform rotation
    y->left = x;
    x->right = T2;
    //  Update heights
    x->height = max(height(x->left), height(x->right))+1;
    y->height = max(height(y->left), height(y->right))+1;
    // Return new root
    return y;
}
// Get Balance factor of node N
int getBalance(struct node *N)
{
    if (N == NULL)
            return 0;
    return height(N->left) - height(N->right);
}
struct node* insert(struct node* node, int key)
{
    /* 1.  Perform the normal BST rotation */
    if (node == NULL)
            return(newNode(key));
    if (key < node->key)
            node->left  = insert(node->left, key);
    else
            node->right = insert(node->right, key);
    /* 2. Update height of this ancestor node */
    node->height = max(height(node->left), height(node->right)) + 1;
    /* 3. Get the balance factor of this ancestor node to check whether
           this node became unbalanced */
    int balance = getBalance(node);
    // If this node becomes unbalanced, then there are 4 cases
    // Left Left Case
    if (balance > 1 && key < node->left->key)
            return rightRotate(node);
    // Right Right Case
    if (balance < -1 && key > node->right->key)
            return leftRotate(node);
    // Left Right Case
    if (balance > 1 && key > node->left->key)
    {
            node->left =  leftRotate(node->left);
            return rightRotate(node);
    }
    // Right Left Case
    if (balance < -1 && key < node->right->key)
    {
            node->right = rightRotate(node->right);
            return leftRotate(node);
    }
    /* return the (unchanged) node pointer */
    return node;
}
/* Given a non-empty binary search tree, return the node with minimum
   key value found in that tree. Note that the entire tree does not
   need to be searched. */
struct node * minValueNode(struct node* node)
{
    struct node* current = node;
    /* loop down to find the leftmost leaf */
    while (current->left != NULL)
            current = current->left;
    return current;
}
struct node* apagaNode(struct node* root, int key)
{
    // STEP 1: PERFORM STANDARD BST DELETE
    if (root == NULL)
            return root;
    // If the key to be deleted is smaller than the root's key,
    // then it lies in left subtree
    if ( key < root->key )
            root->left = apagaNode(root->left, key);
    // If the key to be deleted is greater than the root's key,
    // then it lies in right subtree
    else if( key > root->key )
            root->right = apagaNode(root->right, key);
    // if key is same as root's key, then This is the node
    // to be deleted
    else
    {
            // node with only one child or no child
            if( (root->left == NULL) || (root->right == NULL) )
            {
                    struct node *temp = root->left ? root->left : root->right;
                    // No child case
                    if(temp == NULL)
                    {
                            temp = root;
                            root = NULL;
                    }
                    else // One child case
                         *root = *temp; // Copy the contents of the non-empty child
                    free(temp);
            }
            else
            {
                    // node with two children: Get the inorder successor (smallest
                    // in the right subtree)
                    struct node* temp = minValueNode(root->right);
                    // Copy the inorder successor's data to this node
                    root->key = temp->key;
                    // Delete the inorder successor
                    root->right = apagaNode(root->right, temp->key);
            }
    }
    // If the tree had only one node then return
    if (root == NULL)
          return root;
    // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
    root->height = max(height(root->left), height(root->right)) + 1;
    // STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to check whether
    //  this node became unbalanced)
    int balance = getBalance(root);
    // If this node becomes unbalanced, then there are 4 cases
    // Left Left Case
    if (balance > 1 && getBalance(root->left) >= 0)
            return rightRotate(root);
    // Left Right Case
    if (balance > 1 && getBalance(root->left) < 0)
    {
            root->left =  leftRotate(root->left);
            return rightRotate(root);
    }
    // Right Right Case
    if (balance < -1 && getBalance(root->right) <= 0)
            return leftRotate(root);
    // Right Left Case
    if (balance < -1 && getBalance(root->right) > 0)
    {
            root->right = rightRotate(root->right);
            return leftRotate(root);
    }
    return root;
}

int imprime(struct node *root,int targetPos,int curPos)
{
    if(root != NULL)
    {
            int newPos = imprime(root->left, targetPos, curPos);
            newPos++;
            if (newPos == targetPos)
            {
                    printf("%d\n", root->key);
            }
            return imprime(root->right, targetPos, newPos);
    }
    else
    {
            return curPos;
    }
}

int main()
{
  struct node *root = NULL;
  int total=0;
  int n,b;
  string a;
  cin >> n;
  for (int i=0; i<n; i++)
  {
          cin >> a >> b;
          if(a=="INS")
                  {root = insert(root, b);total=total+1;}
          else
          if(a=="REM")
                   {root = apagaNode(root, b);total=total-1;}
          else
                  imprime(root, total-b+1, 0);
  }
    return 0;
}

我发现使用这棵树按位置打印数字的唯一方法是使用 O(N) 解决方案搜索它，这非常慢

我正在使用的功能：

int imprime(struct node *root,int targetPos,int curPos)
{
    if(root != NULL)
    {
            int newPos = imprime(root->left, targetPos, curPos);
            newPos++;
            if (newPos == targetPos)
            {
                    printf("%d\n", root->key);
            }
            return imprime(root->right, targetPos, newPos);
    }
    else
    {
            return curPos;
    }
}

我知道有一个 O(N * log(N)) 打印通过计算 N_nodes，在插入、删除和旋转期间。但问题是我不明白该怎么做，因为我对这个算法有点迷茫。有人可以帮我吗？

我应该只在轮换时计算 n_nodes 吗？我如何计算它们？

Answer 1

如果创建一个新节点，它的子树中只有一个节点（很明显）。
一个节点的子树中的一些元素只有在它位于从根到新 inserted/removed 节点的路径上或者它被旋转时才会改变。每个 insertion/deletion 有 O(log n) 个这样的节点，因此我们可以更新所有节点的值，而不会增加时间复杂度。

我们可以定义如下函数：

int getSubTreeSize(Node* node) {
    if (node != nullptr)
        return node->subTreeSize;
    else
        return 0;
}

void update(Node* node) {
    if (node != nullptr) {
        node->subTreeSize = getSubTreeSize(node->left) + 
                            getSubTreeSize(node->right) + 1;
    }
}

现在我们所要做的就是为我们在insert/delete一个节点的遍历过程中访问过的所有节点以及那些被旋转的节点调用这个函数。一个微妙的时刻：当我们在旋转过程中调用 update 时，我们应该更新位于较低节点之后的最高节点。

Answer 2

AVL 树不是解决此问题的最佳数据结构。提出的解决方案是增加节点以添加大小和高度信息，而原始 AVL 树只有两位平衡字段。

更好的数据结构是权重平衡树。它只存储子树的大小，不存储高度或平衡。这些算法由 Hirai 和 Yamamoto (2011) 'Balancing Weight-Balanced Trees' Journal of Functional Programming / 21 (3)：第 287-307 页，基于 Nievergelt 和 Reingold 在 1972 年的工作开发。

见Kazu Yamamoto's web page。

AVL Tree - 计数 N_Nodes 按位置打印元素 c++

AVL Tree - Counting N_Nodes to print element by postion c++

c++

algorithm

avl-tree