binarytree

Documentation

Overview

Package binarytree implements binary search tree operations on arrays.

For any given sorted array, Copy permutes the array so that for each item with index i, the item at 2i+1 is smaller and the item at 2i+2 is larger. This permits O(log n) binary searches with strictly monotonically increasing indexes.

Algorithm from casync (camakebst.c), originally by L. Bressel, 2017.

Index

• func Copy(n int, copyFunc func(src, dest int))
• func SearchBy[T any](tree []T, start int, skip int, compare func(T) int) (int, bool)

Functions

func Copy

func Copy(n int, copyFunc func(src, dest int))

Copy rearranges a sorted array of size n into a binary search tree array. For each item at index i, items at 2i+1 are smaller and 2i+2 are larger. copyFunc is called with (sourceIndex, destinationIndex) for each element.

func SearchBy

func SearchBy[T any](tree []T, start int, skip int, compare func(T) int) (int, bool)

SearchBy searches a BST array starting at the given index. The compare function should compare the search value to the element. skip defines how many matches to ignore (for duplicate handling). Returns the index where compare returns 0, or -1, false if not found.