Binary search tree

Inserting data into a bstree

There are two main ways to insert data into the tree: using the provided insertion function along with a comparator, or writing your own insertion function. Writing your own insertion function is more performant since it avoids using a function pointer.

Loading…

1.000.000 random numbers inserted into a bstree (-O0, 100 runs)

API

#include <ds/bstree.h>

Handle

struct bstree

A node in a binary search tree.

Nodes have no associated data and should be embedded onto containers instead.

See also

container_of

Public Members

struct bstree *_parent

Parent node (null if this is the root).

struct bstree *_left

Left subtree.

struct bstree *_right

Right subtree.

Functions

void bstree_link(struct bstree **link, struct bstree *n, struct bstree *parent)

Grafts a new node into the tree at the given location.

Utility for writing external insert functions. Writing your own insert function is more performant since it avoids using a function pointer.

Parameters:

• link – Location to insert the node.

• n – The node to insert.

• parent – Parent of the node to insert.

bool bstree_insert(struct bstree **root, struct bstree *n, int (*cmp)(void*, void*))

Inserts a node at the appropriate position on the tree.

Given a node and a comparator, finds the appropriate position to insert the node while keeping the tree sorted. The comparator receives pointers to the struct bstree nodes being compared.

If the tree is empty, the root pointer will be updated.

Parameters:

• root – Handle to the root of the tree.

• n – The node to insert.

• cmp – Insertion comparator.

struct bstree *bstree_search(struct bstree *n, void *value, int (*cmp)(void*, void*))

Finds a node on the tree, if it exists.

Given a comparator finds a node that matches the given value, if it exists. Returns NULL otherwise. The comparator receives a pointer to the given value and a pointer to the struct bstree node being compared, respectively.

This function is included for completeness and may be used, but it may be more convenient to write your own search function.

Parameters:

• n – Handle to the tree to be searched.

• value – Value to search for.

• cmp – Search comparator. Compares value to a node on the tree.

struct bstree *bstree_first(struct bstree *n)

Finds the node associated with the minimum value on the tree.

Parameters:

• n – Handle to the tree to be searched.

Returns:

Handle to the minimum node on the tree.

struct bstree *bstree_last(struct bstree *n)

Finds the node associated with the maximum value on the tree.

Parameters:

• n – Handle to the tree to be searched.

Returns:

Handle to the maximum node on the tree.

struct bstree *bstree_next(struct bstree *n)

Finds the successor of a node.

Used to traverse the tree in order.

for (struct bstree* it = bstree_first(root); it; it = bstree_next(it))

Parameters:

• n – Handle to the current node.

Returns:

Handle to the successor of the node.

struct bstree *bstree_prev(struct bstree *n)

Finds the predecessor of a node.

Used to traverse the tree in reverse order.

for (struct bstree* it = bstree_last(root); it; it = bstree_prev(it))

Parameters:

• n – Handle to the current node.

Returns:

Handle to the predecessor of the node.

void bstree_remove(struct bstree **root, struct bstree *n)

Removes a node from the tree.

Removes a node while keeping the tree sorted. The tree structure may change as a result but all nodes are guaranteed to remain at the same addresses.

If the root is removed, the root pointer will be updated.

Parameters:

• root – Handle to the root of the tree.

• n – Node to remove.

Internals

Caution

Internals are documented for completeness and to make the codebase easier to understand. However, they should not be used directly.

void _transplant(struct bstree **root, struct bstree *u, struct bstree *v)

Replaces the subtree rooted at u with the subtree rooted at v.

Given two subrees u and v, transplant v to the location of u by replacing the link between us parent and u with a link between us parent and v. The original subtree will not be unlinked and u will retain a link to its parent.

If a subtree is transplanted to the root, the root pointer will be updated.

This is an internal function that should not be used directly.

Parameters:

• root – Handle to the root of the tree.

• u – The subtree to be replaced.

• v – The subtree to transplant.