tpl_avlRk.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
 
# ifndef TPL_AVLRK_H
# define TPL_AVLRK_H
 
# include <algorithm>
# include <ahFunction.H>
# include <tpl_arrayStack.H>
# include <tpl_binNodeXt.H>
# include <tpl_binTreeOps.H>
# include <tpl_binNodeUtils.H>
# include <avlNodeRk.H>
# include <ah-errors.H>
# include <ah-concepts.H>
 
using namespace Aleph;
 
namespace Aleph
{
  template <template <typename> class NodeType, typename Key, class Compare>
    requires StrictWeakOrder<Compare, Key>
  class Gen_Avl_Tree_Rk
  {
  public:
    using Node = NodeType<Key>; 
 
  private:
    FixedStack<Node *> avl_stack;
    Node head_node;
    Node *head_ptr;
    Node *& root;
    Compare cmp;
 
    bool avl_stack_at_base() noexcept
    {
      return not avl_stack.is_empty()
             and avl_stack.size() == 1
             and avl_stack.base() == head_ptr;
    }
 
    void clean_avl_stack() noexcept
    {
      if (avl_stack.is_empty())
        {
          avl_stack.push(head_ptr);
          return;
        }
 
      if (avl_stack.base() != head_ptr)
        {
          avl_stack.empty();
          avl_stack.push(head_ptr);
          return;
        }
 
      if (const size_t to_pop = avl_stack.size() - 1; to_pop > 0)
        avl_stack.popn(static_cast<int>(to_pop));
    }
 
    Node * search_and_stack_avl(const Key & key,
                                signed char & cmp_result) noexcept
    {
      assert(avl_stack_at_base());
 
      Node *p = root;
      Node *candidate = nullptr;  // Tracks potential duplicate when going right
      size_t candidate_pos = 0;   // Stack size when candidate was set
 
      do
        {
          __builtin_prefetch(LLINK(p));
          __builtin_prefetch(RLINK(p));
          avl_stack.push(p);
          if (cmp(key, KEY(p)))  // key < KEY(p)
            {
              cmp_result = CmpLess;
              p = LLINK(p);
            }
          else  // key >= KEY(p), could be equal
            {
              candidate = p;
              candidate_pos = avl_stack.size();
              cmp_result = CmpGreater;
              p = RLINK(p);
            }
        }
      while (p != Node::NullPtr);
 
      // Optimistic duplicate check: when going right, key >= KEY(candidate)
      // If also KEY(candidate) >= key (i.e., not less), then key == KEY(candidate)
      if (candidate != nullptr and not cmp(KEY(candidate), key)) [[unlikely]]
        {
          cmp_result = CmpEqual;
          // Truncate stack: remove nodes pushed after candidate
          const size_t to_pop =
              avl_stack.size() > candidate_pos ?
              avl_stack.size() - candidate_pos : 0;
          if (to_pop > 0)
            avl_stack.popn(static_cast<int>(to_pop));
          return candidate;
        }
 
      return avl_stack.top();
    }
 
    Node * search_dup_and_stack_avl(const Key & key,
                                    signed char & cmp_result) noexcept
    {
      assert(avl_stack_at_base());
      cmp_result = CmpEqual;
 
      Node *p = root;
      do
        {
          __builtin_prefetch(LLINK(p));
          __builtin_prefetch(RLINK(p));
          avl_stack.push(p);
          if (cmp(key, KEY(p))) // key < KEY(p)?
            {
              cmp_result = CmpLess;
              p = LLINK(p);
            }
          else // key >= KEY(p)
            {
              cmp_result = CmpGreater;
              p = RLINK(p);
            }
        }
      while (p != Node::NullPtr);
 
      return avl_stack.top();
    }
 
    // Rotate to left with counter update
    [[gnu::always_inline]] static Node * rotateLeft(Node *p) noexcept
    {
      assert(DIFF(p) == 2);
      assert(RLINK(p) != Node::NullPtr);
 
      Node *q = RLINK(p);
      RLINK(p) = LLINK(q);
      LLINK(q) = p;
 
      // Update counters
      COUNT(p) = COUNT(LLINK(p)) + COUNT(RLINK(p)) + 1;
      COUNT(q) = COUNT(LLINK(q)) + COUNT(RLINK(q)) + 1;
 
      if (DIFF(q) == 0)
        {
          DIFF(q) = -1;
          DIFF(p) = 1;
        }
      else
        DIFF(q) = DIFF(p) = 0;
 
      return q;
    }
 
    // Rotate to right with counter update
    [[gnu::always_inline]] static Node * rotateRight(Node *p) noexcept
    {
      assert(DIFF(p) == -2);
      assert(LLINK(p) != Node::NullPtr);
 
      Node *q = LLINK(p);
      LLINK(p) = RLINK(q);
      RLINK(q) = p;
 
      // Update counters
      COUNT(p) = COUNT(LLINK(p)) + COUNT(RLINK(p)) + 1;
      COUNT(q) = COUNT(LLINK(q)) + COUNT(RLINK(q)) + 1;
 
      if (DIFF(q) == 0)
        {
          DIFF(q) = 1;
          DIFF(p) = -1;
        }
      else
        DIFF(q) = DIFF(p) = 0;
 
      return q;
    }
 
    // Double rotate left with counter update
    [[gnu::always_inline]] static Node * doubleRotateLeft(Node *p) noexcept
    {
      assert(DIFF(p) == 2 or DIFF(p) == -2);
      assert(RLINK(p) != Node::NullPtr and LLINK(RLINK(p)) != Node::NullPtr);
 
      Node *q = RLINK(p);
      Node *r = LLINK(q);
      RLINK(p) = LLINK(r);
      LLINK(q) = RLINK(r);
      LLINK(r) = p;
      RLINK(r) = q;
 
      // Update counters
      COUNT(p) = COUNT(LLINK(p)) + COUNT(RLINK(p)) + 1;
      COUNT(q) = COUNT(LLINK(q)) + COUNT(RLINK(q)) + 1;
      COUNT(r) = COUNT(LLINK(r)) + COUNT(RLINK(r)) + 1;
 
      unsigned char b, c;
      if (DIFF(r) == 1)
        {
          c = 1;
          b = 0;
        }
      else if (DIFF(r) == -1)
        {
          c = 0;
          b = 1;
        }
      else
        c = b = 1;
 
      DIFF(r) = 0;
      DIFF(p) = b - 1;
      DIFF(q) = 1 - c;
 
      return r;
    }
 
    // Double rotate right with counter update
    [[gnu::always_inline]]
    static Node * doubleRotateRight(Node *p) noexcept
    {
      assert(DIFF(p) == 2 or DIFF(p) == -2);
      assert(LLINK(p) != Node::NullPtr and RLINK(LLINK(p)) != Node::NullPtr);
 
      Node *q = LLINK(p);
      Node *r = RLINK(q);
      LLINK(p) = RLINK(r);
      RLINK(q) = LLINK(r);
      RLINK(r) = p;
      LLINK(r) = q;
 
      // Update counters
      COUNT(p) = COUNT(LLINK(p)) + COUNT(RLINK(p)) + 1;
      COUNT(q) = COUNT(LLINK(q)) + COUNT(RLINK(q)) + 1;
      COUNT(r) = COUNT(LLINK(r)) + COUNT(RLINK(r)) + 1;
 
      unsigned char b, c;
      if (DIFF(r) == 1)
        {
          c = 1;
          b = 0;
        }
      else if (DIFF(r) == -1)
        {
          c = 0;
          b = 1;
        }
      else
        c = b = 1;
 
      DIFF(r) = 0;
      DIFF(p) = 1 - c;
      DIFF(q) = b - 1;
 
      return r;
    }
 
    enum Rotation_Type
    {
      ROTATE_LEFT, ROTATE_RIGHT, DOUBLE_ROTATE_LEFT, DOUBLE_ROTATE_RIGHT
    };
 
    static Rotation_Type rotation_type(Node *p) noexcept
    {
      assert(DIFF(p) == 2 or DIFF(p) == -2);
 
      Node *pc;
      if (DIFF(p) == 2)
        {
          pc = RLINK(p);
          if (DIFF(pc) == 1 or DIFF(pc) == 0)
            return ROTATE_LEFT;
          return DOUBLE_ROTATE_LEFT;
        }
 
      pc = LLINK(p);
      if (DIFF(pc) == -1 or DIFF(pc) == 0)
        return ROTATE_RIGHT;
 
      return DOUBLE_ROTATE_RIGHT;
    }
 
    static Node * restore_avl(Node *p, Node *pp) noexcept
    {
      assert(LLINK(pp) == p or RLINK(pp) == p);
      assert(DIFF(p) == -2 or DIFF(p) == 2);
 
      Node **link = LLINK(pp) == p ? &LLINK(pp) : &RLINK(pp);
      switch (rotation_type(p))
        {
        case ROTATE_LEFT: return *link = rotateLeft(p);
        case ROTATE_RIGHT: return *link = rotateRight(p);
        case DOUBLE_ROTATE_LEFT: return *link = doubleRotateLeft(p);
        case DOUBLE_ROTATE_RIGHT: return *link = doubleRotateRight(p);
        default:
          AH_ERROR("Invalid rotation type");
          break;
        }
 
      return nullptr;
    }
 
    void restore_avl_after_insertion(Node *p) noexcept
    {
      Node *pp = avl_stack.pop();
      if (LLINK(pp) == p)
        --DIFF(pp);
      else
        ++DIFF(pp);
 
      if (DIFF(pp) == 0)
        {
          clean_avl_stack();
          return;
        }
 
      if (avl_stack_at_base())
        return;
 
      do
        {
          Node *gpp = avl_stack.pop();
          if (LLINK(gpp) == pp)
            --DIFF(gpp);
          else
            ++DIFF(gpp);
 
          if (DIFF(gpp) == 0)
            break;
          if (DIFF(gpp) == -2 or DIFF(gpp) == 2)
            {
              Node *ggpp = avl_stack.pop();
              restore_avl(gpp, ggpp);
              break;
            }
 
          pp = gpp;
        }
      while (not avl_stack_at_base());
 
      clean_avl_stack();
    }
 
    Node * swapWithSuccessor(Node *p, Node *& pp) noexcept
    {
      Node *& ref_to_stack_top = avl_stack.top();
 
      Node *fSucc = p;
      Node *succ = RLINK(p);
 
      avl_stack.push(succ);
 
      while (LLINK(succ) != Node::NullPtr)
        {
          fSucc = succ;
          succ = LLINK(succ);
          avl_stack.push(succ);
        }
 
      ref_to_stack_top = succ;
      avl_stack.top() = p;
 
      if (LLINK(pp) == p)
        LLINK(pp) = succ;
      else
        RLINK(pp) = succ;
 
      LLINK(succ) = LLINK(p);
      LLINK(p) = Node::NullPtr;
 
      if (RLINK(p) == succ)
        {
          RLINK(p) = RLINK(succ);
          RLINK(succ) = p;
          pp = succ;
        }
      else
        {
          Node *succr = RLINK(succ);
          RLINK(succ) = RLINK(p);
          LLINK(fSucc) = p;
          RLINK(p) = succr;
          pp = fSucc;
        }
 
      // Swap balance factors
      DIFF(succ) = DIFF(p);
 
      // Swap counters
      COUNT(succ) = COUNT(p);
 
      return succ;
    }
 
    void restore_avl_after_deletion(bool left_deficit) noexcept
    {
      Node *pp = avl_stack.top(1);
      Node *ppp = avl_stack.popn(3);
 
      while (true)
        {
          if (left_deficit)
            ++DIFF(pp);
          else
            --DIFF(pp);
 
          if (DIFF(pp) == -2 or DIFF(pp) == 2)
            pp = restore_avl(pp, ppp);
 
          if (DIFF(pp) != 0 or pp == root)
            break;
 
          left_deficit = LLINK(ppp) == pp;
          pp = ppp;
          ppp = avl_stack.pop();
        }
 
      clean_avl_stack();
    }
 
    // Update counters along the stack after insertion
    void update_counters_after_insertion() noexcept
    {
      // Stack contains: [head_ptr, ..., nodes in path, ..., closest to insertion]
      // top(0) = closest node, top(size-1) = head_ptr (don't update)
      const size_t sz = avl_stack.size();
      for (size_t i = 0; i < sz - 1; ++i)
        ++COUNT(avl_stack.top(i));
    }
 
    // Update counters along the stack after deletion
    void update_counters_after_deletion() noexcept
    {
      const size_t sz = avl_stack.size();
      for (size_t i = 0; i < sz - 1; ++i)
        --COUNT(avl_stack.top(i));
    }
 
  public:
    using key_type = Key; 
 
    [[nodiscard]] constexpr Compare &key_comp() noexcept { return cmp; }
 
    [[nodiscard]] constexpr Compare &get_compare() noexcept { return key_comp(); }
 
    Gen_Avl_Tree_Rk(Compare cmf_fct = Compare()) noexcept
      : avl_stack(Node::MaxHeight), head_ptr(&head_node),
        root(RLINK(head_ptr)), cmp(cmf_fct)
    {
      avl_stack.push(head_ptr);
    }
 
    void swap(Gen_Avl_Tree_Rk & tree) noexcept
    {
      std::swap(root, tree.root);
      std::swap(cmp, tree.cmp);
    }
 
    virtual ~Gen_Avl_Tree_Rk() noexcept { assert(avl_stack_at_base()); }
 
    [[nodiscard]] constexpr Node *&getRoot() noexcept { return root; }
 
    [[nodiscard]] constexpr Node * getRoot() const noexcept { return root; }
 
    [[nodiscard]] size_t size() const noexcept { return COUNT(root); }
 
    [[nodiscard]] constexpr bool is_empty() const noexcept { return root == Node::NullPtr; }
 
    [[nodiscard]] Node * search(const Key & key) const noexcept
    {
      Node *result = searchInBinTree<Node, Compare>(root, key, cmp);
      return result == Node::NullPtr ? nullptr : result;
    }
 
    [[nodiscard]] Node * insert(Node *p) noexcept
    {
      if (root == Node::NullPtr)
        return root = p;
 
      signed char cmp_result = CmpEqual;
      Node *pp = search_and_stack_avl(KEY(p), cmp_result);
      if (cmp_result == CmpLess)
        LLINK(pp) = p;
      else if (cmp_result == CmpGreater)
        RLINK(pp) = p;
      else
        {
          clean_avl_stack();
          return nullptr;
        }
 
      update_counters_after_insertion();
      restore_avl_after_insertion(p);
 
      return p;
    }
 
    [[nodiscard]] Node * search_or_insert(Node *p) noexcept
    {
      if (root == Node::NullPtr)
        return root = p;
 
      signed char cmp_result = CmpEqual;
      Node *pp = search_and_stack_avl(KEY(p), cmp_result);
      if (cmp_result == CmpLess)
        LLINK(pp) = p;
      else if (cmp_result == CmpGreater)
        RLINK(pp) = p;
      else
        {
          clean_avl_stack();
          return pp;
        }
 
      update_counters_after_insertion();
      restore_avl_after_insertion(p);
 
      return p;
    }
 
    [[nodiscard]] Node * insert_dup(Node *p) noexcept
    {
      if (root == Node::NullPtr)
        return root = p;
 
      signed char cmp_result = CmpEqual;
      Node *pp = search_dup_and_stack_avl(KEY(p), cmp_result);
      if (cmp_result == CmpLess)
        LLINK(pp) = p;
      else
        RLINK(pp) = p;
 
      update_counters_after_insertion();
      restore_avl_after_insertion(p);
 
      return p;
    }
 
    [[nodiscard]] Node * remove(const Key & key) noexcept
    {
      if (root == Node::NullPtr)
        return nullptr;
 
      signed char cmp_result = CmpEqual;
      Node *p = search_and_stack_avl(key, cmp_result);
      if (cmp_result != CmpEqual)
        {
          clean_avl_stack();
          return nullptr;
        }
 
      Node *pp = avl_stack.top(1);
      bool left_deficit;
 
      while (true)
        {
          left_deficit = LLINK(pp) == p;
          if (LLINK(p) == Node::NullPtr)
            {
              if (LLINK(pp) == p)
                LLINK(pp) = RLINK(p);
              else
                RLINK(pp) = RLINK(p);
              break;
            }
 
          if (RLINK(p) == Node::NullPtr)
            {
              if (LLINK(pp) == p)
                LLINK(pp) = LLINK(p);
              else
                RLINK(pp) = LLINK(p);
              break;
            }
 
          swapWithSuccessor(p, pp);
        }
 
      p->reset();
 
      if (pp == head_ptr)
        {
          clean_avl_stack();
          return p;
        }
 
      update_counters_after_deletion();
      restore_avl_after_deletion(left_deficit);
 
      return p;
    }
 
    Node * select(const size_t i) const
    {
      return Aleph::select(root, i);
    }
 
    std::pair<long, Node *> position(const Key & key) const noexcept
    {
      std::pair<long, Node *> ret_val;
 
      ret_val.first = BinTreeXt_Operation<Node, Compare>(cmp).
          inorder_position(root, key, ret_val.second);
 
      return ret_val;
    }
 
    std::pair<long, Node *> find_position(const Key & key) const noexcept
    {
      std::pair<long, Node *> r(-2, nullptr);
 
      r.first = BinTreeXt_Operation<Node, Compare>(cmp).
          find_position(root, key, r.second);
 
      return r;
    }
 
    [[nodiscard]] bool verify() const noexcept
    {
      return is_avl_rk(root) and check_rank_tree(root);
    }
 
  private:
    // Compute height of AVL tree in O(log n) using balance factors
    static size_t avl_height(Node *p) noexcept
    {
      size_t h = 0;
      while (p != Node::NullPtr)
        {
          ++h;
          // Follow the taller subtree
          if (DIFF(p) >= 0)
            p = RLINK(p); // right is taller or equal
          else
            p = LLINK(p); // left is taller
        }
      return h;
    }
 
    // Extract and remove the minimum node from tree rooted at p
    // Returns the extracted node and updates p to the new root
    static Node * extract_min(Node *& p) noexcept
    {
      if (p == Node::NullPtr)
        return Node::NullPtr;
 
      if (LLINK(p) == Node::NullPtr)
        {
          Node *ret = p;
          p = RLINK(p);
          LLINK(ret) = RLINK(ret) = Node::NullPtr;
          COUNT(ret) = 1;
          DIFF(ret) = 0;
          return ret;
        }
 
      // Stack for rebalancing
      FixedStack<Node **> stack(Node::MaxHeight);
      Node **pp = &p;
 
      while (LLINK(*pp) != Node::NullPtr)
        {
          stack.push(pp);
          pp = &LLINK(*pp);
        }
 
      Node *ret = *pp;
      *pp = RLINK(ret);
 
      // Update counts and rebalance going up
      while (not stack.is_empty())
        {
          Node **parent_ptr = stack.pop();
          Node *parent = *parent_ptr;
          --COUNT(parent);
          ++DIFF(parent); // left subtree got shorter
 
          if (DIFF(parent) == 2)
            {
              // Need to rebalance
              Node *q = RLINK(parent);
              if (DIFF(q) >= 0)
                *parent_ptr = rotateLeft(parent);
              else
                *parent_ptr = doubleRotateLeft(parent);
            }
          else if (DIFF(parent) == 1)
            break; // height didn't change
        }
 
      LLINK(ret) = RLINK(ret) = Node::NullPtr;
      COUNT(ret) = 1;
      DIFF(ret) = 0;
      return ret;
    }
 
    // Extract and remove the maximum node from tree rooted at p
    static Node * extract_max(Node *& p) noexcept
    {
      if (p == Node::NullPtr)
        return Node::NullPtr;
 
      if (RLINK(p) == Node::NullPtr)
        {
          Node *ret = p;
          p = LLINK(p);
          LLINK(ret) = RLINK(ret) = Node::NullPtr;
          COUNT(ret) = 1;
          DIFF(ret) = 0;
          return ret;
        }
 
      FixedStack<Node **> stack(Node::MaxHeight);
      Node **pp = &p;
 
      while (RLINK(*pp) != Node::NullPtr)
        {
          stack.push(pp);
          pp = &RLINK(*pp);
        }
 
      Node *ret = *pp;
      *pp = LLINK(ret);
 
      while (not stack.is_empty())
        {
          Node **parent_ptr = stack.pop();
          Node *parent = *parent_ptr;
          --COUNT(parent);
          --DIFF(parent); // right subtree got shorter
 
          if (DIFF(parent) == -2)
            {
              Node *q = LLINK(parent);
              if (DIFF(q) <= 0)
                *parent_ptr = rotateRight(parent);
              else
                *parent_ptr = doubleRotateRight(parent);
            }
          else if (DIFF(parent) == -1)
            break;
        }
 
      LLINK(ret) = RLINK(ret) = Node::NullPtr;
      COUNT(ret) = 1;
      DIFF(ret) = 0;
      return ret;
    }
 
    // Recursive join of two AVL trees where all keys in t1 < all keys in t2
    // h1 and h2 are the heights of t1 and t2 respectively
    static Node * join_exclusive_rec(Node *t1, size_t h1,
                                     Node *t2, size_t h2) noexcept
    {
      if (t1 == Node::NullPtr)
        return t2;
      if (t2 == Node::NullPtr)
        return t1;
 
      if (h1 >= h2)
        {
          // Extract max from t1 to use as pivot
          Node *pivot = extract_max(t1);
          if (t1 != Node::NullPtr)
            h1 = avl_height(t1);
          else
            h1 = 0;
 
          return join_with_pivot(t1, h1, pivot, t2, h2);
        }
      // Extract min from t2 to use as pivot
      Node *pivot = extract_min(t2);
      if (t2 != Node::NullPtr)
        h2 = avl_height(t2);
      else
        h2 = 0;
 
      return join_with_pivot(t1, h1, pivot, t2, h2);
    }
 
    // Join t1 and t2 using pivot as the connecting node
    // All keys in t1 < pivot < all keys in t2
    static Node * join_with_pivot(Node *t1, const size_t h1, Node *pivot,
                                  Node *t2, const size_t h2) noexcept
    {
      if (h1 <= h2 + 1 and h2 <= h1 + 1)
        {
          // Heights are close enough, pivot becomes root
          LLINK(pivot) = t1;
          RLINK(pivot) = t2;
          DIFF(pivot) = static_cast<signed char>(h2) - static_cast<signed char>(h1);
          COUNT(pivot) = COUNT(t1) + COUNT(t2) + 1;
          return pivot;
        }
 
      if (h1 > h2)
        {
          // t1 is taller, descend into right spine of t1
          Node *result = join_right(t1, h1, pivot, t2, h2);
          return result;
        }
      // t2 is taller, descend into left spine of t2
      Node *result = join_left(t1, h1, pivot, t2, h2);
      return result;
    }
 
    // Join when h1 > h2 + 1: descend right spine of t1
    static Node * join_right(Node *t1, const size_t h1, Node *pivot,
                             Node *t2, const size_t h2) noexcept
    {
      FixedStack<Node **> stack(Node::MaxHeight);
      Node **pp = &t1;
      size_t curr_h = h1;
 
      // Descend right spine until we find a subtree of appropriate height
      while (curr_h > h2 + 1 and *pp != Node::NullPtr)
        {
          stack.push(pp);
          if (DIFF(*pp) >= 0)
            curr_h--; // right child has height curr_h - 1
          else
            curr_h -= 2; // right child has height curr_h - 2 (since left is curr_h - 1)
 
          pp = &RLINK(*pp);
        }
 
      // Now *pp points to a subtree of height <= h2 + 1
      // Join pivot with *pp and t2
      LLINK(pivot) = *pp;
      RLINK(pivot) = t2;
      const size_t left_h = (*pp != Node::NullPtr) ? avl_height(*pp) : 0;
      DIFF(pivot) = static_cast<signed char>(h2) - static_cast<signed char>(left_h);
      COUNT(pivot) = COUNT(*pp) + COUNT(t2) + 1;
      *pp = pivot;
 
      // Rebalance going up
      while (not stack.is_empty())
        {
          Node **parent_ptr = stack.pop();
          Node *parent = *parent_ptr;
          COUNT(parent) = COUNT(LLINK(parent)) + COUNT(RLINK(parent)) + 1;
 
          const size_t new_right_h = avl_height(RLINK(parent));
          const size_t new_left_h = avl_height(LLINK(parent));
          DIFF(parent) = static_cast<signed char>(new_right_h) -
                         static_cast<signed char>(new_left_h);
 
          if (DIFF(parent) == 2)
            {
              if (Node *q = RLINK(parent); DIFF(q) >= 0)
                *parent_ptr = rotateLeft(parent);
              else
                *parent_ptr = doubleRotateLeft(parent);
            }
        }
 
      return t1;
    }
 
    // Join when h2 > h1 + 1: descend left spine of t2
    static Node * join_left(Node *t1, const size_t h1, Node *pivot,
                            Node *t2, const size_t h2) noexcept
    {
      FixedStack<Node **> stack(Node::MaxHeight);
      Node **pp = &t2;
      size_t curr_h = h2;
 
      while (curr_h > h1 + 1 and *pp != Node::NullPtr)
        {
          stack.push(pp);
          if (DIFF(*pp) <= 0)
            curr_h--;
          else
            curr_h -= 2;
 
          pp = &LLINK(*pp);
        }
 
      RLINK(pivot) = *pp;
      LLINK(pivot) = t1;
      const size_t right_h = (*pp != Node::NullPtr) ? avl_height(*pp) : 0;
      DIFF(pivot) = static_cast<signed char>(right_h) - static_cast<signed char>(h1);
      COUNT(pivot) = COUNT(t1) + COUNT(*pp) + 1;
      *pp = pivot;
 
      while (not stack.is_empty())
        {
          Node **parent_ptr = stack.pop();
          Node *parent = *parent_ptr;
          COUNT(parent) = COUNT(LLINK(parent)) + COUNT(RLINK(parent)) + 1;
 
          const size_t new_right_h = avl_height(RLINK(parent));
          const size_t new_left_h = avl_height(LLINK(parent));
          DIFF(parent) = static_cast<signed char>(new_right_h) -
                         static_cast<signed char>(new_left_h);
 
          if (DIFF(parent) == -2)
            {
              if (Node *q = LLINK(parent); DIFF(q) <= 0)
                *parent_ptr = rotateRight(parent);
              else
                *parent_ptr = doubleRotateRight(parent);
            }
        }
 
      return t2;
    }
 
    // Split by key recursively
    // Returns the node containing key (or NullPtr if not found)
    // t1 gets all keys < key, t2 gets all keys > key
    Node * split_key_rec(Node *p, const Key & key,
                         Node *& t1, Node *& t2) noexcept
    {
      if (p == Node::NullPtr)
        {
          t1 = t2 = Node::NullPtr;
          return Node::NullPtr;
        }
 
      Node *found;
      if (cmp(key, KEY(p)))
        {
          // key < p->key, go left
          Node *left_t2;
          found = split_key_rec(LLINK(p), key, t1, left_t2);
 
          // p and its right subtree go to t2
          LLINK(p) = Node::NullPtr;
          const size_t left_t2_h = (left_t2 != Node::NullPtr) ? avl_height(left_t2) : 0;
          const size_t right_h = (RLINK(p) != Node::NullPtr) ? avl_height(RLINK(p)) : 0;
 
          Node *right_tree = RLINK(p);
          RLINK(p) = Node::NullPtr;
          COUNT(p) = 1;
          DIFF(p) = 0;
 
          t2 = join_with_pivot(left_t2, left_t2_h, p, right_tree, right_h);
        }
      else if (cmp(KEY(p), key))
        {
          // key > p->key, go right
          Node *right_t1;
          found = split_key_rec(RLINK(p), key, right_t1, t2);
 
          // p and its left subtree go to t1
          RLINK(p) = Node::NullPtr;
          const size_t right_t1_h = (right_t1 != Node::NullPtr) ? avl_height(right_t1) : 0;
          const size_t left_h = (LLINK(p) != Node::NullPtr) ? avl_height(LLINK(p)) : 0;
 
          Node *left_tree = LLINK(p);
          LLINK(p) = Node::NullPtr;
          COUNT(p) = 1;
          DIFF(p) = 0;
 
          t1 = join_with_pivot(left_tree, left_h, p, right_t1, right_t1_h);
        }
      else
        {
          // Found the key
          t1 = LLINK(p);
          t2 = RLINK(p);
          LLINK(p) = RLINK(p) = Node::NullPtr;
          COUNT(p) = 1;
          DIFF(p) = 0;
          found = p;
        }
 
      return found;
    }
 
    // Split by key for duplicates: keys <= key go to t1, keys > key go to t2
    void split_key_dup_rec(Node *p, const Key & key,
                           Node *& t1, Node *& t2) noexcept
    {
      if (p == Node::NullPtr)
        {
          t1 = t2 = Node::NullPtr;
          return;
        }
 
      if (cmp(key, KEY(p)))
        {
          // key < p->key, p goes to t2
          Node *left_t2;
          split_key_dup_rec(LLINK(p), key, t1, left_t2);
 
          LLINK(p) = Node::NullPtr;
          const size_t left_t2_h = (left_t2 != Node::NullPtr) ? avl_height(left_t2) : 0;
          const size_t right_h = (RLINK(p) != Node::NullPtr) ? avl_height(RLINK(p)) : 0;
 
          Node *right_tree = RLINK(p);
          RLINK(p) = Node::NullPtr;
          COUNT(p) = 1;
          DIFF(p) = 0;
 
          t2 = join_with_pivot(left_t2, left_t2_h, p, right_tree, right_h);
        }
      else
        {
          // key >= p->key, p goes to t1
          Node *right_t1;
          split_key_dup_rec(RLINK(p), key, right_t1, t2);
 
          RLINK(p) = Node::NullPtr;
          const size_t right_t1_h = (right_t1 != Node::NullPtr) ? avl_height(right_t1) : 0;
          const size_t left_h = (LLINK(p) != Node::NullPtr) ? avl_height(LLINK(p)) : 0;
 
          Node *left_tree = LLINK(p);
          LLINK(p) = Node::NullPtr;
          COUNT(p) = 1;
          DIFF(p) = 0;
 
          t1 = join_with_pivot(left_tree, left_h, p, right_t1, right_t1_h);
        }
    }
 
    // Split by position recursively
    // Nodes with position < pos go to t1, nodes with position >= pos go to t2
    void split_pos_rec(Node *p, size_t pos, Node *& t1, Node *& t2) noexcept
    {
      if (p == Node::NullPtr)
        {
          t1 = t2 = Node::NullPtr;
          return;
        }
 
      if (const size_t left_count = COUNT(LLINK(p)); pos <= left_count)
        {
          // Split point is in left subtree or at p
          Node *left_t2;
          split_pos_rec(LLINK(p), pos, t1, left_t2);
 
          // p goes to t2
          LLINK(p) = Node::NullPtr;
          const size_t left_t2_h = (left_t2 != Node::NullPtr) ? avl_height(left_t2) : 0;
          const size_t right_h = (RLINK(p) != Node::NullPtr) ? avl_height(RLINK(p)) : 0;
 
          Node *right_tree = RLINK(p);
          RLINK(p) = Node::NullPtr;
          COUNT(p) = 1;
          DIFF(p) = 0;
 
          t2 = join_with_pivot(left_t2, left_t2_h, p, right_tree, right_h);
        }
      else
        {
          // Split point is in right subtree
          Node *right_t1;
          split_pos_rec(RLINK(p), pos - left_count - 1, right_t1, t2);
 
          // p goes to t1
          RLINK(p) = Node::NullPtr;
          const size_t right_t1_h = (right_t1 != Node::NullPtr) ? avl_height(right_t1) : 0;
          const size_t left_h = (LLINK(p) != Node::NullPtr) ? avl_height(LLINK(p)) : 0;
 
          Node *left_tree = LLINK(p);
          LLINK(p) = Node::NullPtr;
          COUNT(p) = 1;
          DIFF(p) = 0;
 
          t1 = join_with_pivot(left_tree, left_h, p, right_t1, right_t1_h);
        }
    }
 
  public:
    void join_exclusive(Gen_Avl_Tree_Rk & t) noexcept
    {
      if (t.root == Node::NullPtr)
        return;
 
      if (root == Node::NullPtr)
        {
          root = t.root;
          t.root = Node::NullPtr;
          return;
        }
 
      // Collect nodes from t in preorder and insert them one by one
      // This is O(m log(n+m)) but guarantees correctness
      FixedStack<Node *> stack(Node::MaxHeight);
      stack.push(t.root);
      t.root = Node::NullPtr;
 
      while (not stack.is_empty())
        {
          Node *p = stack.pop();
          Node *left = LLINK(p);
          Node *right = RLINK(p);
 
          // Reset node and insert
          LLINK(p) = RLINK(p) = Node::NullPtr;
          COUNT(p) = 1;
          DIFF(p) = 0;
          (void)insert(p);
 
          if (right != Node::NullPtr)
            stack.push(right);
          if (left != Node::NullPtr)
            stack.push(left);
        }
    }
 
    Node * split_key(const Key & key, Gen_Avl_Tree_Rk & t1,
                     Gen_Avl_Tree_Rk & t2) noexcept
    {
      if (root == Node::NullPtr)
        return nullptr;
 
      // Simple O(n) implementation: iterate through tree and partition
      Node *found = nullptr;
      FixedStack<Node *> stack(Node::MaxHeight);
      stack.push(root);
      root = Node::NullPtr;
 
      while (not stack.is_empty())
        {
          Node *p = stack.pop();
          Node *left = LLINK(p);
          Node *right = RLINK(p);
 
          if (right != Node::NullPtr)
            stack.push(right);
          if (left != Node::NullPtr)
            stack.push(left);
 
          LLINK(p) = RLINK(p) = Node::NullPtr;
          COUNT(p) = 1;
          DIFF(p) = 0;
 
          if (cmp(KEY(p), key))
            (void)t1.insert(p);
          else if (cmp(key, KEY(p)))
            (void)t2.insert(p);
          else
            found = p; // Found the key
        }
 
      return found;
    }
 
    void split_key_dup(const Key & key, Gen_Avl_Tree_Rk & t1,
                       Gen_Avl_Tree_Rk & t2) noexcept
    {
      if (root == Node::NullPtr)
        return;
 
      FixedStack<Node *> stack(Node::MaxHeight);
      stack.push(root);
      root = Node::NullPtr;
 
      while (not stack.is_empty())
        {
          Node *p = stack.pop();
          Node *left = LLINK(p);
          Node *right = RLINK(p);
 
          if (right != Node::NullPtr)
            stack.push(right);
          if (left != Node::NullPtr)
            stack.push(left);
 
          LLINK(p) = RLINK(p) = Node::NullPtr;
          COUNT(p) = 1;
          DIFF(p) = 0;
 
          if (cmp(key, KEY(p)))
            (void)t2.insert(p);
          else
            (void)t1.insert_dup(p);
        }
    }
 
    void split_pos(const size_t pos, Gen_Avl_Tree_Rk & t1,
                   Gen_Avl_Tree_Rk & t2) noexcept
    {
      if (root == Node::NullPtr)
        return;
 
      if (pos == 0)
        {
          t2.root = root;
          root = Node::NullPtr;
          return;
        }
 
      if (pos >= size())
        {
          t1.root = root;
          root = Node::NullPtr;
          return;
        }
 
      // Simple O(n) implementation using inorder traversal
      size_t count = 0;
      FixedStack<Node *> stack(Node::MaxHeight);
      Node *curr = root;
      root = Node::NullPtr;
 
      // Inorder traversal
      while (curr != Node::NullPtr or not stack.is_empty())
        {
          while (curr != Node::NullPtr)
            {
              stack.push(curr);
              Node *left = LLINK(curr);
              LLINK(curr) = Node::NullPtr; // Disconnect
              curr = left;
            }
 
          curr = stack.pop();
          Node *right = RLINK(curr);
          RLINK(curr) = Node::NullPtr;
          COUNT(curr) = 1;
          DIFF(curr) = 0;
 
          if (count < pos)
            (void)t1.insert(curr);
          else
            (void)t2.insert(curr);
 
          ++count;
          curr = right;
        }
    }
 
    class Iterator : public BinTreeXt_Iterator<Gen_Avl_Tree_Rk, Node, Key, Compare>
    {
      using Base = BinTreeXt_Iterator<Gen_Avl_Tree_Rk, Node, Key, Compare>;
 
    public:
      using Base::Base;
      using Base::operator=;
    }; // end class Iterator
  };
 
 
  template <typename Key, class Compare = Aleph::less<Key>>
    requires StrictWeakOrder<Compare, Key>
  struct Avl_Tree_Rk : public Gen_Avl_Tree_Rk<AvlNodeRk, Key, Compare>
  {
    using Base = Gen_Avl_Tree_Rk<AvlNodeRk, Key, Compare>;
    using Base::Base;
  };
 
 
  template <typename Key, class Compare = Aleph::less<Key>>
    requires StrictWeakOrder<Compare, Key>
  struct Avl_Tree_Rk_Vtl : public Gen_Avl_Tree_Rk<AvlNodeRkVtl, Key, Compare>
  {
    using Base = Gen_Avl_Tree_Rk<AvlNodeRkVtl, Key, Compare>;
    using Base::Base;
  };
} // end namespace Aleph
 
# endif // TPL_AVLRK_H