avlNode.H File Reference

AVL tree node with balance factor. More...

#include <tpl_binNodeUtils.H>

Include dependency graph for avlNode.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	AvlNode_Data
	Data portion of an AVL tree node. More...
class	AvlNode< Key >
	Declare AvlNode type with 40-byte pool allocation. More...
class	AvlNodeVtl< Key >

Macros
#define	DIFF(p)   ((p)->getDiff())
	Access the balance factor of node p.

Functions
template<class Node >
bool	is_avl (Node *p)
	Validate that a tree satisfies AVL properties.

Detailed Description

AVL tree node with balance factor.

This file defines the AvlNode structure for AVL trees, including the balance factor (height difference) attribute and validation functions.

AVL Tree Properties

An AVL tree maintains the invariant that for every node: |height(left) - height(right)| ≤ 1

The balance factor (diff) stores: height(right) - height(left) Valid values are -1, 0, or +1.

Balance Factor Meaning

diff	Meaning
-1	Left subtree is 1 taller
0	Both subtrees have equal height
+1	Right subtree is 1 taller

See also

tpl_avl.H AVL tree implementation

rbNode.H Red-Black tree node (alternative balancing)

Author

Leandro Rabindranath León

Definition in file avlNode.H.

Macro Definition Documentation

DIFF

#define DIFF

(

p

)

((p)->getDiff())

Access the balance factor of node p.

Definition at line 95 of file avlNode.H.

Function Documentation

is_avl()

template<class Node >

bool is_avl

(

Node *

p

)

Validate that a tree satisfies AVL properties.

Checks that:

• The stored balance factor matches actual height difference
• The balance factor is in range [-1, +1]
• All subtrees also satisfy AVL properties

Template Parameters

Node	AVL node type

Parameters

p	Root of subtree to validate

Returns

true if tree is a valid AVL tree

Note

This function computes heights recursively, so it's O(n²). Use only for testing/debugging.

Example

Avl_Tree<int> tree;
// ... insertions ...
assert(is_avl(tree.getRoot()));

Definition at line 123 of file avlNode.H.

References Aleph::computeHeightRec(), Aleph::diff(), DIFF, is_avl(), Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by is_avl(), TEST(), and Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::verify().