data_structures::tree_234::Node Class Reference

2-3-4 tree node class More...

Collaboration diagram for data_structures::tree_234::Node:

Public Member Functions
	Node (int64_t item)
	Node constructor. More...
int8_t	GetCount ()
	Get the item count that current saved in the node. More...
void	SetCount (int8_t c)
	Set the item count of the node. More...
bool	IsLeaf ()
	Check if node is a leaf. More...
bool	IsFull ()
	Check if node is a full (4-node) More...
bool	Is2Node ()
	Check if node is a 2-node. More...
bool	Is34Node ()
	Check if node is a 3-node or 4-node, this is useful when we delete item from 2-3-4 tree. More...
bool	Contains (int64_t item)
	Check if item is in the node. More...
int8_t	GetItemIndex (int64_t item)
	Get the index of the item in the node, 0-based. More...
int64_t	GetMaxItem ()
	Get max item (rightmost) in the current node. More...
int64_t	GetMinItem ()
	get min item (leftmost) in the current node More...
int64_t	GetItem (int8_t index)
	Get item of the \index index. More...
void	SetItem (int8_t index, int64_t new_item)
	Set item value at position of index. More...
int	InsertItem (int item)
	Insert item to the proper position of the node and return the position index. More...
void	InsertItemByIndex (int8_t index, int64_t item, Node *with_child, bool to_left=true)
	Insert a value to the index position. More...
Node *	RemoveItemByIndex (int8_t index, bool keep_left)
	Insert a value to the index position. More...
int8_t	GetChildIndex (Node *child)
	Get the child's index of the children array. More...
Node *	GetChild (int8_t index)
	Get the child pointer at position of index. More...
void	SetChild (int8_t index, Node *child)
	Set child pointer to the position of index. More...
Node *	GetRightmostChild ()
	Get rightmose child of the current node. More...
Node *	GetLeftmostChild ()
	Get leftmose child of the current node. More...
Node *	GetItemLeftChild (int8_t item_index)
	Get left child of item at item_index. More...
Node *	GetItemRightChild (int8_t item_index)
	Get right child of item at item_index. More...
Node *	GetNextPossibleChild (int64_t item)
	Get next node which is possibly contains item. More...

Private Attributes
std::array< int64_t, 3 >	items
	store items
std::array< Node *, 4 >	children
	store the children pointers
int8_t	count = 0
	track the current item count

Detailed Description

2-3-4 tree node class

Constructor & Destructor Documentation

Node()

data_structures::tree_234::Node::Node ( int64_t  item )

inlineexplicit

Node constructor.

Parameters

item	the first value we insert to the node

        : count(1),
          items({{item, 0, 0}}),
          children({{nullptr, nullptr, nullptr, nullptr}}) {}

Member Function Documentation

Contains()

bool data_structures::tree_234::Node::Contains ( int64_t  item )

inline

Check if item is in the node.

Parameters

item	item to check

Returns

true if item in the node, otherwise false

                                {
        for (int8_t i = 0; i < count; i++) {
            if (item == items[i]) {
                return true;
            }
        }
        return false;
    }

GetChild()

Node* data_structures::tree_234::Node::GetChild ( int8_t  index )

inline

Get the child pointer at position of index.

Parameters

index

index of child to get

Returns

the child pointer

{ return children[index]; }

GetChildIndex()

int8_t data_structures::tree_234::Node::GetChildIndex ( Node *  child )

inline

Get the child's index of the children array.

Parameters

child

child pointer of which to get the index

Returns

the index of child

                                      {
        for (int8_t i = 0; i < count + 1; i++) {
            if (children[i] == child) {
                return i;
            }
        }
 
        return -1;
    }

GetCount()

int8_t data_structures::tree_234::Node::GetCount ( )

inline

Get the item count that current saved in the node.

Returns

item count

{ return count; }

GetItem()

int64_t data_structures::tree_234::Node::GetItem ( int8_t  index )

inline

Get item of the \index index.

Parameters

index

the item index to get

Returns

the item

{ return items[index]; }

GetItemIndex()

int8_t data_structures::tree_234::Node::GetItemIndex ( int64_t  item )

inline

Get the index of the item in the node, 0-based.

Parameters

item	item to check

Returns

0-based index of the item in the node, if not in the node, -1 is returned

                                      {
        for (int8_t i = 0; i < count; i++) {
            if (items[i] == item) {
                return i;
            }
        }
        return -1;
    }

GetItemLeftChild()

Node* data_structures::tree_234::Node::GetItemLeftChild ( int8_t  item_index )

inline

Get left child of item at item_index.

Parameters

item_index

index of the item whose left child to be get

Returns

left child of items[index]'s

                                              {
        if (item_index < 0 || item_index > count - 1) {
            return nullptr;
        }
 
        return children[item_index];
    }

GetItemRightChild()

Node* data_structures::tree_234::Node::GetItemRightChild ( int8_t  item_index )

inline

Get right child of item at item_index.

Parameters

item_index

index of the item whose right child to be get

Returns

right child of items[index]'s

                                               {
        if (item_index < 0 || item_index > count - 1) {
            return nullptr;
        }
 
        return children[item_index + 1];
    }

GetLeftmostChild()

Node* data_structures::tree_234::Node::GetLeftmostChild ( )

inline

Get leftmose child of the current node.

Returns

the leftmost child

{ return children[0]; }

GetMaxItem()

int64_t data_structures::tree_234::Node::GetMaxItem ( )

inline

Get max item (rightmost) in the current node.

Returns

max item

{ return items[count - 1]; }

GetMinItem()

int64_t data_structures::tree_234::Node::GetMinItem ( )

inline

get min item (leftmost) in the current node

Returns

min item

{ return items[0]; }

GetNextPossibleChild()

Node* data_structures::tree_234::Node::GetNextPossibleChild ( int64_t  item )

inline

Get next node which is possibly contains item.

Parameters

item	item to search

Returns

the next node that possibly contains item

                                             {
        int i = 0;
        for (i = 0; i < count; i++) {
            if (items[i] > item) {
                break;
            }
        }
        return children[i];
    }

GetRightmostChild()

Node* data_structures::tree_234::Node::GetRightmostChild ( )

inline

Get rightmose child of the current node.

Returns

the rightmost child

{ return children[count]; }

InsertItem()

int data_structures::tree_234::Node::InsertItem ( int  item )

inline

Insert item to the proper position of the node and return the position index.

This is a helper function we use during insertion. Please mind that when insert a item, we aslo need to take care of two child pointers. One is the original child pointer at the insertion position. It can be placed as new item's either left child or right child. And the other is the new child that should be added. For our dedicated situation here, we choose to use the original child as the new item's left child, and add a null pointer to its right child. So after use the function, please update these two children pointer manually.

Parameters

item	value to be inserted to the node

Returns

index where item is inserted, caller can use this index to update its left and right child

                             {
        assert(!IsFull());
 
        if (Contains(item)) {
            return -1;
        }
 
        int8_t i = 0;
        for (i = 0; i < count; i++) {
            if (items[i] > item) {
                break;
            }
        }
 
        InsertItemByIndex(i, item, nullptr, true);
        return i;
    }

Here is the call graph for this function:

InsertItemByIndex()

void data_structures::tree_234::Node::InsertItemByIndex ( int8_t  index, int64_t  item, Node *  with_child, bool  to_left = true  )

inline

Insert a value to the index position.

Parameters

index	index where to insert item
item	value to insert
with_child	new added child pointer
to_left	true indicate adding with_child to new item's left child, otherwise to right child

                                                {
        assert(count < 3 && index >= 0 && index < 3);
 
        for (int8_t i = count - 1; i >= index; i--) {
            items[i + 1] = items[i];
        }
 
        items[index] = item;
 
        int8_t start_index = to_left ? index : index + 1;
 
        for (int8_t i = count; i >= start_index; i--) {
            children[i + 1] = children[i];
        }
 
        children[start_index] = with_child;
 
        count++;
    }

Is2Node()

bool data_structures::tree_234::Node::Is2Node ( )

inline

Check if node is a 2-node.

Returns

true if node is 2-node, otherwise false

{ return count == 1; }

Is34Node()

bool data_structures::tree_234::Node::Is34Node ( )

inline

Check if node is a 3-node or 4-node, this is useful when we delete item from 2-3-4 tree.

Returns

true if node is 3-node or 4-node, false otherwise

{ return count == 2 || count == 3; }

IsFull()

bool data_structures::tree_234::Node::IsFull ( )

inline

Check if node is a full (4-node)

Returns

true if node is full (4-node), false otherwise

{ return count == 3; }

IsLeaf()

bool data_structures::tree_234::Node::IsLeaf ( )

inline

Check if node is a leaf.

Returns

true if node is leaf, false otherwise

{ return children[0] == nullptr; }

RemoveItemByIndex()

Node* data_structures::tree_234::Node::RemoveItemByIndex ( int8_t  index, bool  keep_left  )

inline

Insert a value to the index position.

Parameters

index	index of the item to remove
keep_left	which child of the item to keep, true keep the left child, false keep the right child

Returns

the removed child pointer

                                                          {
        assert(index >= 0 && index < count);
        Node *removed_child = keep_left ? children[index + 1] : children[index];
        for (int8_t i = index; i < count - 1; i++) {
            items[i] = items[i + 1];
        }
 
        for (int8_t i = keep_left ? index + 1 : index; i < count; i++) {
            children[i] = children[i + 1];
        }
 
        count--;
        return removed_child;
    }

SetChild()

void data_structures::tree_234::Node::SetChild ( int8_t  index, Node *  child  )

inline

Set child pointer to the position of index.

Parameters

index	children index
child	pointer to set

{ children[index] = child; }

SetCount()

void data_structures::tree_234::Node::SetCount ( int8_t  c )

inline

Set the item count of the node.

This is only used when we spliting and merging node where we need to do some raw operation manually. In common inserting and removing operation the count is maintained automatically.

Parameters

c	the count to set

{ count = c; }

SetItem()

void data_structures::tree_234::Node::SetItem ( int8_t  index, int64_t  new_item  )

inline

Set item value at position of index.

Parameters

index	the index of the item to set
new_item	item value

                                                 {
        assert(index >= 0 && index <= 2);
 
        items[index] = new_item;
    }

---

The documentation for this class was generated from the following file:

• data_structures/tree_234.cpp