戴-斯托特-沃伦

选一种语言就能看到代码

def tree_to_vine(pseudo):
    size = 0
    tail = pseudo
    rest = tail.right
    while rest is not None:
        if rest.left is None:
            tail = rest
            rest = rest.right
            size += 1
            continue
        pivot = rest.left
        rest.left = pivot.right
        pivot.right = rest
        tail.right = pivot
        rest = pivot
    return size


def compress(pseudo, count):
    scanner = pseudo
    for _ in range(count):
        child = scanner.right
        scanner.right = child.right
        scanner = scanner.right
        child.right = scanner.left
        scanner.left = child


def balance(root):
    pseudo = Node(0)
    pseudo.right = root
    size = tree_to_vine(pseudo)
    rest = (1 << ((size + 1).bit_length() - 1)) - 1
    compress(pseudo, size - rest)
    while rest > 1:
        rest //= 2
        compress(pseudo, rest)
    return pseudo.right

function treeToVine(pseudo) {
  let size = 0;
  let tail = pseudo;
  let rest = tail.right;
  while (rest !== null) {
    if (rest.left === null) {
      tail = rest;
      rest = rest.right;
      size++;
      continue;
    }
    const pivot = rest.left;
    rest.left = pivot.right;
    pivot.right = rest;
    tail.right = pivot;
    rest = pivot;
  }
  return size;
}

function compress(pseudo, count) {
  let scanner = pseudo;
  for (let i = 0; i < count; i++) {
    const child = scanner.right;
    scanner.right = child.right;
    scanner = scanner.right;
    child.right = scanner.left;
    scanner.left = child;
  }
}

function balance(root) {
  const pseudo = makeNode(0);
  pseudo.right = root;
  const size = treeToVine(pseudo);
  let rest = 2 ** (31 - Math.clz32(size + 1)) - 1;
  compress(pseudo, size - rest);
  while (rest > 1) {
    rest = Math.floor(rest / 2);
    compress(pseudo, rest);
  }
  return pseudo.right;
}

static int tree_to_vine(Node* pseudo) {
    int size = 0;
    Node* tail = pseudo;
    Node* rest = tail->right;
    while (rest != NULL) {
        if (rest->left == NULL) {
            tail = rest;
            rest = rest->right;
            size++;
            continue;
        }
        Node* pivot = rest->left;
        rest->left = pivot->right;
        pivot->right = rest;
        tail->right = pivot;
        rest = pivot;
    }
    return size;
}

static void compress(Node* pseudo, int count) {
    Node* scanner = pseudo;
    for (int i = 0; i < count; i++) {
        Node* child = scanner->right;
        scanner->right = child->right;
        scanner = scanner->right;
        child->right = scanner->left;
        scanner->left = child;
    }
}

Node* balance(Node* root) {
    Node pseudo = {0, NULL, root};
    int size = tree_to_vine(&pseudo);
    int rest = 1;
    while (rest * 2 <= size + 1) rest *= 2;
    rest -= 1;
    compress(&pseudo, size - rest);
    while (rest > 1) {
        rest /= 2;
        compress(&pseudo, rest);
    }
    return pseudo.right;
}

int tree_to_vine(Node* pseudo) {
    int size = 0;
    Node* tail = pseudo;
    Node* rest = tail->right;
    while (rest != nullptr) {
        if (rest->left == nullptr) {
            tail = rest;
            rest = rest->right;
            size++;
            continue;
        }
        Node* pivot = rest->left;
        rest->left = pivot->right;
        pivot->right = rest;
        tail->right = pivot;
        rest = pivot;
    }
    return size;
}

void compress(Node* pseudo, int count) {
    Node* scanner = pseudo;
    for (int i = 0; i < count; i++) {
        Node* child = scanner->right;
        scanner->right = child->right;
        scanner = scanner->right;
        child->right = scanner->left;
        scanner->left = child;
    }
}

Node* balance(Node* root) {
    Node pseudo{0, nullptr, root};
    int size = tree_to_vine(&pseudo);
    int rest = 1;
    while (rest * 2 <= size + 1) rest *= 2;
    rest -= 1;
    compress(&pseudo, size - rest);
    while (rest > 1) {
        rest /= 2;
        compress(&pseudo, rest);
    }
    return pseudo.right;
}

static int TreeToVine(Node pseudo) {
    int size = 0;
    Node tail = pseudo;
    Node rest = tail.Right;
    while (rest != null) {
        if (rest.Left == null) {
            tail = rest;
            rest = rest.Right;
            size++;
            continue;
        }
        Node pivot = rest.Left;
        rest.Left = pivot.Right;
        pivot.Right = rest;
        tail.Right = pivot;
        rest = pivot;
    }
    return size;
}

static void Compress(Node pseudo, int count) {
    Node scanner = pseudo;
    for (int i = 0; i < count; i++) {
        Node child = scanner.Right;
        scanner.Right = child.Right;
        scanner = scanner.Right;
        child.Right = scanner.Left;
        scanner.Left = child;
    }
}

static Node Balance(Node root) {
    Node pseudo = new Node(0) { Right = root };
    int size = TreeToVine(pseudo);
    int rest = 1;
    while (rest * 2 <= size + 1) rest *= 2;
    rest -= 1;
    Compress(pseudo, size - rest);
    while (rest > 1) {
        rest /= 2;
        Compress(pseudo, rest);
    }
    return pseudo.Right;
}

static int treeToVine(Node pseudo) {
    int size = 0;
    Node tail = pseudo;
    Node rest = tail.right;
    while (rest != null) {
        if (rest.left == null) {
            tail = rest;
            rest = rest.right;
            size++;
            continue;
        }
        Node pivot = rest.left;
        rest.left = pivot.right;
        pivot.right = rest;
        tail.right = pivot;
        rest = pivot;
    }
    return size;
}

static void compress(Node pseudo, int count) {
    Node scanner = pseudo;
    for (int i = 0; i < count; i++) {
        Node child = scanner.right;
        scanner.right = child.right;
        scanner = scanner.right;
        child.right = scanner.left;
        scanner.left = child;
    }
}

static Node balance(Node root) {
    Node pseudo = new Node(0);
    pseudo.right = root;
    int size = treeToVine(pseudo);
    int rest = Integer.highestOneBit(size + 1) - 1;
    compress(pseudo, size - rest);
    while (rest > 1) {
        rest /= 2;
        compress(pseudo, rest);
    }
    return pseudo.right;
}