Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
tree_234.cpp File Reference

A demo 2-3-4 tree implementation. More...

#include <array>
#include <cassert>
#include <fstream>
#include <iostream>
#include <memory>
#include <queue>
#include <string>
Include dependency graph for tree_234.cpp:

Classes

class  data_structures::tree_234::Node
 2-3-4 tree node class More...
 
class  data_structures::tree_234::Tree234
 2-3-4 tree class More...
 

Namespaces

namespace  data_structures
 for IO operations
 
namespace  tree_234
 Functions for 2–3–4 tree
 

Functions

static void test1 ()
 simple test to insert a given array and delete some item, and print the tree
 
static void test2 (int64_t n)
 simple test to insert continuous number of range [0, n), and print the tree
 
int main (int argc, char *argv[])
 Main function.
 

Detailed Description

A demo 2-3-4 tree implementation.

2–3–4 tree is a self-balancing data structure that is an isometry of red–black trees. Though we seldom use them in practice, we study them to understand the theory behind Red-Black tree. Please read following links for more infomation. 2–3–4 tree 2-3-4 Trees: A Visual Introduction We Only implement some basic and complicated operations in this demo. Other operations should be easy to be added.

Author
liuhuan

Function Documentation

◆ main()

int main ( int argc,
char * argv[] )

Main function.

Parameters
argccommandline argument count (ignored)
argvcommandline array of arguments (ignored)
Returns
0 on exit
1298 {
1299 if (argc < 2) {
1300 test1(); // execute 1st test
1301 } else {
1302 test2(std::stoi(argv[1])); // execute 2nd test
1303 }
1304
1305 return 0;
1306}
static void test2()
Self-implementations, 2nd test.
Definition dsu_path_compression.cpp:186
T stoi(T... args)
static void test1()
simple test to insert a given array and delete some item, and print the tree
Definition tree_234.cpp:1263
Here is the call graph for this function:

◆ test1()

static void test1 ( )
static

simple test to insert a given array and delete some item, and print the tree

1263 {
1264 std::array<int16_t, 13> arr = {3, 1, 5, 4, 2, 9, 10, 8, 7, 6, 16, 13, 14};
1266
1267 for (auto i : arr) {
1268 tree.Insert(i);
1269 }
1270
1271 // tree.Remove(10);
1272 tree.Remove(5);
1273 tree.Print();
1274}
2-3-4 tree class
Definition tree_234.cpp:323
void Print(const char *file_name=nullptr)
Print tree into a dot file.
Definition tree_234.cpp:1131
bool Remove(int64_t item)
Remove item from tree.
Definition tree_234.cpp:929
void Insert(int64_t item)
Insert item to tree.
Definition tree_234.cpp:655
Here is the call graph for this function:

◆ test2()

static void test2 ( int64_t n)
static

simple test to insert continuous number of range [0, n), and print the tree

Parameters
nupper bound of the range number to insert
1281 {
1283
1284 for (int64_t i = 0; i < n; i++) {
1285 tree.Insert(i);
1286 }
1287
1288 tree.Traverse();
1289 tree.Print((std::to_string(n) + ".dot").c_str());
1290}
void Traverse()
In-order traverse.
Definition tree_234.cpp:562
T to_string(T... args)
Here is the call graph for this function: