Несогласованность указателя в модифицированном шаблоне структуры очереди с использованием AVL ⇐ C++

[Anonymous]

Я создаю модифицированный шаблон структуры очереди, используя дерево AVL, чтобы обеспечить перемещение элементов вперед. Если я использую обычную реализацию связанного списка, перемещение данного элемента вперед на позиции x будет иметь значение O(n), поэтому я хочу использовать AVL.
Я держу указатели на заголовок (самый левый node), который нужно вытолкнуть, и хвост (самый правый) для последнего нажатия. Существует функция jump_forward(Ref node, k), которая перемещает узел, заданный ссылкой, вперед на k позиций ближе к голове.
У меня проблема с функцией pop_first(), что приводит к ошибкам сегментации.
Я также не уверен, как реализовать сохранение порядка позиции (значение позиции узла должно увеличиваться при его вставке, поэтому новый узел всегда является новым максимумом)
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* root;
Node* head;
Node* 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* node;
Ref(Node* 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* newNode = new Node(x, count++, tail);
tail->right = newNode;
tail = newNode;

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


Подробнее здесь: https://stackoverflow.com/questions/791 ... -using-avl