Scapegoat Tree

pick a language to open the code

ALPHA = 2 / 3


def size_of(node):
    return 0 if node is None else 1 + size_of(node.left) + size_of(node.right)


def flatten(node, line):
    if node is not None:
        flatten(node.left, line)
        line.append(node)
        flatten(node.right, line)


def build(line, lo, hi):
    if lo >= hi:
        return None
    mid = (lo + hi) // 2
    line[mid].left = build(line, lo, mid)
    line[mid].right = build(line, mid + 1, hi)
    return line[mid]


def insert(node, key, room):
    if node is None:
        return Node(key), room < 1
    if key < node.key:
        node.left, deep = insert(node.left, key, room * ALPHA)
        kid = node.left
    else:
        node.right, deep = insert(node.right, key, room * ALPHA)
        kid = node.right
    if deep and size_of(kid) > ALPHA * size_of(node):
        line = []
        flatten(node, line)
        return build(line, 0, len(line)), False
    return node, deep

const ALPHA = 2 / 3;

function sizeOf(node) {
  if (node === null) return 0;
  return 1 + sizeOf(node.left) + sizeOf(node.right);
}

function flatten(node, line) {
  if (node === null) return;
  flatten(node.left, line);
  line.push(node);
  flatten(node.right, line);
}

function build(line, lo, hi) {
  if (lo >= hi) return null;
  const mid = (lo + hi) >> 1;
  line[mid].left = build(line, lo, mid);
  line[mid].right = build(line, mid + 1, hi);
  return line[mid];
}

function insert(node, key, room) {
  if (node === null) return [makeNode(key), room < 1];
  const side = key < node.key ? 'left' : 'right';
  const [kid, deep] = insert(node[side], key, room * ALPHA);
  node[side] = kid;
  if (deep && sizeOf(kid) > ALPHA * sizeOf(node)) {
    const line = [];
    flatten(node, line);
    return [build(line, 0, line.length), false];
  }
  return [node, deep];
}

static const double ALPHA = 2.0 / 3.0;

static int size_of(Node* n) {
    return n == NULL ? 0 : 1 + size_of(n->left) + size_of(n->right);
}

static int flatten(Node* n, Node* line[], int at) {
    if (n == NULL) return at;
    at = flatten(n->left, line, at);
    line[at++] = n;
    return flatten(n->right, line, at);
}

static Node* build(Node* line[], int lo, int hi) {
    if (lo >= hi) return NULL;
    int mid = (lo + hi) / 2;
    line[mid]->left = build(line, lo, mid);
    line[mid]->right = build(line, mid + 1, hi);
    return line[mid];
}

Node* insert(Node* n, int key, double room, int* deep) {
    if (n == NULL) {
        Node* fresh = calloc(1, sizeof(Node));
        fresh->key = key;
        *deep = room < 1.0;
        return fresh;
    }
    if (key < n->key) n->left = insert(n->left, key, room * ALPHA, deep);
    else n->right = insert(n->right, key, room * ALPHA, deep);
    Node* kid = key < n->key ? n->left : n->right;
    if (*deep && size_of(kid) > ALPHA * size_of(n)) {
        int count = size_of(n);
        Node** line = malloc(count * sizeof(Node*));
        flatten(n, line, 0);
        n = build(line, 0, count);
        free(line);
        *deep = 0;
    }
    return n;
}

const double ALPHA = 2.0 / 3.0;

int size_of(Node* n) {
    return n == nullptr ? 0 : 1 + size_of(n->left) + size_of(n->right);
}

void flatten(Node* n, std::vector<Node*>& line) {
    if (n == nullptr) return;
    flatten(n->left, line);
    line.push_back(n);
    flatten(n->right, line);
}

Node* build(std::vector<Node*>& line, int lo, int hi) {
    if (lo >= hi) return nullptr;
    int mid = (lo + hi) / 2;
    line[mid]->left = build(line, lo, mid);
    line[mid]->right = build(line, mid + 1, hi);
    return line[mid];
}

Node* insert(Node* n, int key, double room, bool& deep) {
    if (n == nullptr) {
        deep = room < 1.0;
        return new Node{key};
    }
    if (key < n->key) n->left = insert(n->left, key, room * ALPHA, deep);
    else n->right = insert(n->right, key, room * ALPHA, deep);
    Node* kid = key < n->key ? n->left : n->right;
    if (deep && size_of(kid) > ALPHA * size_of(n)) {
        std::vector<Node*> line;
        flatten(n, line);
        n = build(line, 0, static_cast<int>(line.size()));
        deep = false;
    }
    return n;
}

static readonly double Alpha = 2.0 / 3.0;

static int SizeOf(Node n) {
    return n == null ? 0 : 1 + SizeOf(n.Left) + SizeOf(n.Right);
}

static int Flatten(Node n, Node[] line, int at) {
    if (n == null) return at;
    at = Flatten(n.Left, line, at);
    line[at++] = n;
    return Flatten(n.Right, line, at);
}

static Node Build(Node[] line, int lo, int hi) {
    if (lo >= hi) return null;
    int mid = (lo + hi) / 2;
    line[mid].Left = Build(line, lo, mid);
    line[mid].Right = Build(line, mid + 1, hi);
    return line[mid];
}

static Node Insert(Node n, int key, double room, ref bool deep) {
    if (n == null) {
        deep = room < 1.0;
        return new Node(key);
    }
    if (key < n.Key) n.Left = Insert(n.Left, key, room * Alpha, ref deep);
    else n.Right = Insert(n.Right, key, room * Alpha, ref deep);
    Node kid = key < n.Key ? n.Left : n.Right;
    if (deep && SizeOf(kid) > Alpha * SizeOf(n)) {
        Node[] line = new Node[SizeOf(n)];
        Flatten(n, line, 0);
        n = Build(line, 0, line.Length);
        deep = false;
    }
    return n;
}

static final double ALPHA = 2.0 / 3.0;
static boolean deep;

static int sizeOf(Node n) {
    return n == null ? 0 : 1 + sizeOf(n.left) + sizeOf(n.right);
}

static int flatten(Node n, Node[] line, int at) {
    if (n == null) return at;
    at = flatten(n.left, line, at);
    line[at++] = n;
    return flatten(n.right, line, at);
}

static Node build(Node[] line, int lo, int hi) {
    if (lo >= hi) return null;
    int mid = (lo + hi) / 2;
    line[mid].left = build(line, lo, mid);
    line[mid].right = build(line, mid + 1, hi);
    return line[mid];
}

static Node insert(Node n, int key, double room) {
    if (n == null) {
        deep = room < 1.0;
        return new Node(key);
    }
    if (key < n.key) n.left = insert(n.left, key, room * ALPHA);
    else n.right = insert(n.right, key, room * ALPHA);
    Node kid = key < n.key ? n.left : n.right;
    if (deep && sizeOf(kid) > ALPHA * sizeOf(n)) {
        Node[] line = new Node[sizeOf(n)];
        flatten(n, line, 0);
        n = build(line, 0, line.length);
        deep = false;
    }
    return n;
}