TreeTrace and TreeView

TreeTrace holds the steps of a binary tree. Each TreeStep has the nodes (an id, a label and the ids of the left and right child), the root, the highlighted nodes, the path walked to them, a found node and a note. Every step is laid out once when the trace is made, with layout::tidy_tree; a node with one child leans it to its side. with_layout(TreeLayout::Tree) lays the steps out again with the tree layout of the graph layouts (GraphLayout::Tree): the children are centred under their parent, so a single child sits straight below it.

• TreeTrace::bst(&values) starts a search tree with the values inserted. insert, search and remove walk down from the root one node a step, noting which way they go; remove replaces a node with two children by the smallest node on its right.
• TreeTrace::max_heap(&values) and min_heap start a heap. push adds at the bottom and sifts up, pop takes the root and sifts the last node down, a compare and a swap a step. Nodes keep their values, so swapped nodes trade places.

TreeView draws the trace as round nodes radius pixels, spacing pixels between slots and level pixels between depths. Highlighted nodes light up, the path is outlined, a found node turns green, nodes slide to their new places (two swapped nodes pass side by side), new ones drop in and removed ones fade. Gallery scenes: TreeView (a search tree: an insert, a search and a remove), Heap (a push and a pop).

TreeView 13 sPlayUnmuteCopy render command

Heap 10 sPlayUnmuteCopy render command

use fframes_kit::prelude::*;

let bst = TreeTrace::bst(&[50, 30, 70]).insert(40).remove(30).finish();
let last = bst.steps().last().unwrap();
assert_eq!(last.nodes.len(), 3);
assert_eq!(last.note, "40 moves up");

fn tree<'a>(ui: &mut Ui<'a, '_, '_>, trace: &'a TreeTrace) -> Svgr<'a> {
    ui.show(TreeView {
        trace: Some(trace),
        step_time: 0.8,
        ..ui.defaults()
    })
}

API

Components are plain structs. Set the fields you need and fill the rest with ..ui.defaults(): the defaults below come from the current theme (theme. values are fields of Theme).

TreeView

A binary tree: round nodes radius pixels with their values, spacing pixels between neighbouring slots and level pixels between depths, centred on center (units of ui.space). It plays a TreeTrace, one step every step_time seconds from delay: the nodes a step looks at light up, the path to them is outlined, nodes slide to their new places as the tree changes (swapped heap nodes pass each other), new nodes drop in and removed ones fade. The whole figure fades with enter and exit.

Field	Type	Default	Description
trace	Option<&TreeTrace>	None	The recorded steps to play (TreeTrace); None draws nothing.
delay	f32	0.0	Seconds after the container’s start before the first step.
step_time	f32	0.8	Seconds each step of the trace takes.
center	(f64, f64)	(0.0, 0.0)	The middle of the tree, in units of ui.space.
spacing	f32	100.0	Pixels between neighbouring node slots in a depth.
level	f32	120.0	Pixels between depths.
radius	f32	30.0	Radius of a node in pixels.
notes	bool	true	Whether the step’s note is written under the tree.
colors	CellColors	CellColors::themed(theme)	Colours of the nodes in each state (looked at, moved, found).
edge_color	Color	theme.colors.muted	Colour of the edges between nodes.
path_color	Color	theme.colors.accent	Colour of the outline of the path to the nodes a step looks at.
value_style	TextStyle	value_style	The font of the values in the nodes.
small_style	TextStyle	theme.typography.caption	The font of the notes.
enter	Option<FadeIn>	None	Fade in at the start; None for none.
exit	Option<FadeOut>	None	Fade out before the end; None for none.

Feature cs · Source