casoncaly/balancetree

Binary balanced search tree: AVL, red-black tree recursive/non-recursive C++ code implementation (non-third-party library)

BalanceTree

本项目为平衡树的性能对比C++测试工程，非调用第三方库，包括：

1. AVL 基于节点高度差的增删逻辑，c++递归实现。
2. AVL 基于节点高度差的增删逻辑，c++非递归实现。
3. AVL 基于节点平衡因子的增删逻辑，c++递归实现。
4. AVL 基于节点平衡因子的增删逻辑，c++非递归实现。
5. RBT 红黑树的增删逻辑，包含C++多种递归删除方案的实现。
6. RBT 红黑树的增删逻辑，C++非递归的实现。
7. 各平衡树的校验逻辑，及性能测试。
8. 结论：顺序插入1000w数值，该代码中AVL增删速度要优于红黑树、STL::Set

BalanceTree

This project is a C++ test project for the performance comparison of balanced tree, which does not call third-party libraries, including:

1. AVL based on node height difference of addition and deletion logic, c++ recursive implementation.
2. AVL based on the node height difference of addition and deletion logic, c++ non-recursive implementation.
3. AVL based on node balance factor add and delete logic, c++ recursive implementation.
4. AVL based on node balance factor add and delete logic, c++ non-recursive implementation.
5. RBT red black tree addition and deletion logic, including C++ a variety of recursive deletion scheme implementation.
6. RBT red black tree addition and deletion logic, C++ non-recursive implementation.
7. Verification logic of each balance tree and performance test.
8. Conclusion: With sequential insertion of 1000w values, AVL in this code is faster than red-black tree and STL::Set

Video

对应的视频教程：https://space.bilibili.com/1700469421

Screenshots

AVL

RBTree