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:

Go to the source code of this file.

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

Definition in file tree_234.cpp.

Function Documentation

main()

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

Main function.

Parameters

argc	commandline argument count (ignored)
argv	commandline array of arguments (ignored)

Returns

0 on exit

Definition at line 1298 of file tree_234.cpp.

                                 {
    if (argc < 2) {
        test1();  // execute 1st test
    } else {
        test2(std::stoi(argv[1]));  // execute 2nd test
    }
 
    return 0;
}

test1()

static void test1 ( )

static

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

Definition at line 1263 of file tree_234.cpp.

                    {
    std::array<int16_t, 13> arr = {3, 1, 5, 4, 2, 9, 10, 8, 7, 6, 16, 13, 14};
    data_structures::tree_234::Tree234 tree;
 
    for (auto i : arr) {
        tree.Insert(i);
    }
 
    // tree.Remove(10);
    tree.Remove(5);
    tree.Print();
}

test2()

static void test2 ( int64_t n )

static

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

Parameters

n	upper bound of the range number to insert

Definition at line 1281 of file tree_234.cpp.

                             {
    data_structures::tree_234::Tree234 tree;
 
    for (int64_t i = 0; i < n; i++) {
        tree.Insert(i);
    }
 
    tree.Traverse();
    tree.Print((std::to_string(n) + ".dot").c_str());
}