Pointer inconsistency in modified Queue struct template using AVL

Question

I'm making a modified Queue struct template using AVL tree to allow for moving elements forward. If I use normal linked list implementation, moving a given element forward by x positions will cos O(n), hence why I want to use AVL.

I keep pointers to head (the leftmost node) to be popped and tail (the rightmost) for last pushed. There is a function jump_forward(Ref node, k) which will move a node given by reference forward by k positions closer to head.

I'm having a problem in pop_first() function, resulting in seg faults. I also unsure on how to implement keeping order of position (Node's position value should increment with its insertion so new node is always new max)

struct Node {
    T value;
    int position;
    Node* left;
    Node* right;
    Node* parent;
    int depth;

Node(T val, int pos, Node* par = nullptr) : value(val), position(pos), left(nullptr), right(nullptr), parent(par), depth(1) {}
};

struct Queue {
Node<T>* root;
Node<T>* head;
Node<T>* tail;
size_t count;

Queue() : root(nullptr), head(nullptr), tail(nullptr), count(0) {}
bool empty() const {
    return count == 0;
}
size_t size() const {
    return count;
}

struct Ref {
    Node<T>* node;
    Ref(Node<T>* n = nullptr) : node(n) {};
};

Ref push_last(T x) {
    // queue is empty -> create new node
    if (root == nullptr) {
        root = new Node(x, count++);
        head = tail = root;
    } else {
        // attach new node as right child of current max -> rebalance
        Node<T>* newNode = new Node<T>(x, count++, tail);
        tail->right = newNode;
        tail = newNode;

        Node<T> *tmp = newNode->parent;
        // re-balancing the right subtree
        while (tmp) {
            updateDepth(tmp);
            tmp = reBalance(tmp);
            tmp = tmp->parent;
        }
    }
    return Ref(tail);

};
T pop_first() {
    if (empty()) throw std::out_of_range("Queue is empty");

    T headValue = head->value;
    Node<T>* oldHead = head;

    // head is root -> last element
    if(head->right == nullptr && head->parent == nullptr) {
        root = nullptr;
        head = nullptr;
        tail = nullptr;
        count = 0;
     // head is root but has right child
    } else if (head->right != nullptr && head->parent == nullptr) {
        head = head->right;
        head->parent = nullptr;
        root = head;
    // head is not root
    } else {
        // head has right child
        if (head->right) {
            head = head->right;
            head->parent = oldHead->parent;
            head->parent->left = head;
        // head has no right child
        } else {
            head = oldHead->parent;
            head->left = nullptr;
        }
    }
    delete oldHead;
    count--;

    if(root) {
        Node<T> *tmp = head->parent;
        // re-balancing the left subtree
        while (tmp) {
            updateDepth(tmp);
            tmp= reBalance(tmp);
            tmp = tmp->parent;
        }
    }
    return headValue;
}; // throw std::out_of_range if empty

int getDepth(Node<T> *node) const {
    return node ? node->depth : 0;
}
void updateParent(Node<T>* child, Node<T>* parent) {
    if (child) {
        child->parent = parent;
    }
}
void updateDepth(Node<T> *node) {
    if (node) {
        node->depth = std::max(getDepth(node->left), getDepth(node->right)) + 1;
    }
}
int getBalanceFactor(Node<T>* node) const {
    if (!node) return 0;
    return getDepth(node->left) - getDepth(node->right);
}
Node<T>* rightRotate(Node<T>* y) {
    Node<T>* x = y->left;
    Node<T>* T2 = x->right;

    x->right = y;
    y->left = T2;

    updateParent(T2, y);
    updateParent(x, y->parent);
    updateParent(y, x);

    if (y == root) {
        root = x;
        x->parent = nullptr;
    }
    updateDepth(y);
    updateDepth(x);

    return x;
}

Node<T>* leftRotate(Node<T>* x) {
    Node<T>* y = x->right;
    Node<T>* T2 = y->left;

    y->left = x;
    x->right = T2;

    updateParent(T2, x);
    updateParent(y, x->parent);
    updateParent(x, y);

    if (x == root) {
        root = y;
        y->parent = nullptr;
    }

    updateDepth(x);
    updateDepth(y);

    return y;
}

Node<T>* reBalance(Node<T>* node) {

    int balance = getBalanceFactor(node);

    // Right heavy
    if (balance > 1) {
        if (getBalanceFactor(node->left) < 0)
            node->left = leftRotate(node->left);
        return rightRotate(node); }

    // Left heavy
    if (balance < -1) {
        if (getBalanceFactor(node->right) > 0)
            node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    return node;
}
};