Lines Matching full:tree
3 Balanced Red/Black Tree
8 For these situations, Zephyr provides a balanced tree implementation
10 O(log2(N)) for a tree of size N. This is implemented using a
11 conventional red/black tree as described by multiple academic sources.
21 ``lessthan_fn`` field of the :c:struct:`rbtree` struct before any tree
24 the second in the ordering desired by the tree. Note that "equal" is
25 not allowed, nodes within a tree must have a single fixed order for
31 being tracked in the tree. Unlike the list code, the data within an
33 the binary tree topology and "manually" traverse the tree as it is for
36 Nodes can be inserted into a tree with :c:func:`rb_insert` and removed
38 tree (in the sense of the order defined by the comparison function) is
41 provided node pointer exists as an element within the tree. As
43 log time complexity in the size of the tree.
48 argument to be passed to it, and the tree code calls that function for
66 Tree Internals
70 red/black tree as described pervasively in academic sources. Low
75 The core invariant guaranteed by the tree is that the path from the root of
76 the tree to any leaf is no more than twice as long as the path to any
104 within the binary tree. Traversal of a tree for rebalancing following
109 locally as it traverses downward through the tree and updating it
113 These properties, of a balanced tree data structure that works with
118 Red/Black Tree API Reference