12,691,959 members (30,780 online)
Add your own
alternative version

215K views
5.4K downloads
105 bookmarked
Posted

# Fast Binary Tree Operations

, 22 Jan 2005
 Rate this:
Please Sign up or sign in to vote.
Describes main binary tree operations.

## Introduction

In this article, I will show you how to use the Binary Search Tree to store data. And I am using templates for keys and data values to simplify usage of any data types. If you have good experience about the theory behind the binary search trees, you can skip next sections of the background.

## Background

[1] Binary search trees are data structures which support many dynamic-set operations including search, insert, delete, minimum, maximum, predecessor, and successor. Basic operations on binary search tree take time proportional to the height of the tree. For a complete binary tree with n nodes, such operations take O(log n) time in the worst-case, as the height of randomly built binary search tree is proportional to log n. In some cases operations take O(n) time in case of sorted input, so the tree will be like a sorted list, so I used the `Red-Black` tree balancing technique, as described in the Tree Load Balancing section

A binary search tree is organized in a binary tree as shown in figure 1. Such a tree can be represented by a linked data structure in which each node is an object. In addition to the key field, each node contains fields left, right, and parent that point to the nodes corresponding to its left child, its right child, and its parent, respectively. If a child or the parent is missing, the appropriate field field contains a value NIL.

I will not dig in all `Binary Tree` functions here, I will just refer to the search function, and you can check reference [1] for more details, and I will talk about some of them in the code description, as many of them is so sophisticated like the `Delete` function.

#### Searching

The most common operation performed in binary search tree is searching for a key stored in the tree, which can be done in two ways:

1. Recursion:

```Node Search(Node, key)
{
if Node = NIL or key = Node.key
return Node
if key < Node.key
then return Search(Node.Left, key)
else return Search(Node.Right, key)
}```
2. While loop:
```Node Search(key)
{
Node = root
while Node != NIL and key != Node.key
do if key < Node.key
then Node = Node.Left
else Node = Node.Right
return Node
}```

The two ways begin search at the root and trace a path downward in the tree till they find the `key` or return `NIL` (not found case). First way code is more simple, but second way optimizes stack usage, which I am preferring in all my cases to deal with huge data without affecting the stack and the performance.

## Code Description

All Tree functions encapsulated in a template class `CBinaryTree` and `CBinaryTreeNode`.

 `GetCount` returns tree nodes count with repetition (repeated key will assigned to one node). `RemoveAll` removes all tree nodes. `Insert` inserts new `key` in the tree. `Search` searches for `key` in the tree. `Min` gets minimum node key under the input node. `Max` gets maximum node key under the input node. `Successor` gets node successor (node which comes next in the over all tree sorting). `Predecessor` gets node predecessor (node which comes previous in the over all tree sorting). `Delete` deletes node from tree and adjusts its childs' nodes. `Save` saves all tree nodes' order in a vector of integers.

In all my code here, I am avoiding recursion functions to avoid stack overflow, as I am dealing with huge data, so you will find all my code using <CODE lang=c++>while loops, sometimes code becomes complicated like the `RemoveAll` function:

#### RemoveAll function

This function removes all tree nodes, it does that by order to each node to delete its `left` child then its `right` child, then delete itself. This can be done with two ways:

1. While loop:
```// remove all tree nodes
void RemoveAll()
{
TREENODE *node = Root, *pTemp;
while(node != Nil)
{
// check for left child
if(node->Left != Nil)
node = node->Left;
// check for right child
else    if(node->Right != Nil)
node = node->Right;
else    // node has no childs
{    // save node pointer
pTemp = node;
// set node pointer at its parent to NULL
if(node->Parent != Nil)
node->Parent->Childs[node != node->Parent->Left] = Nil;
// update pointer node to its parent
node = node->Parent;
// delete the saved node
delete pTemp;
}
}
Count = Serial = 0;
Root = Nil;
Modified = false;
}```

As you can see, there is some complication at this section (node has no children).

2. Recursion way:

It simply puts `delete left` and `right` nodes at each node destructor and call `delete` for tree root.

```~CBinaryTreeNode()
{
if(Childs[0])
delete Childs[0];
if(Childs[1])
delete Childs[1];
}
// ...
delete Tree.Root;```

All the nodes will be deleted automatically through stack usage, but if you read the comments in the first way code, you will find it easy to understand it, and avoid stack usage.

#### Min function

The Minimum of a node x can be found by following `left` child from the node x until a `Nil` is encountered, as in the following code:

```// return minimum key in the tree
TREENODE* Min(TREENODE* node) const
{
// iterate in the left branch
while(node != Nil && node->Left != Nil)
node = node->Left;
return node;
}```

#### Successor function

The successor of a node x is the node with the smallest key greater than key[x]. For example, if you add keys (C I D H B F E G A J K) in sequence and will be as shown in the following figure:

Each arrow represents the direction from each node to its successor. The code in the `Successor`function takes two paths:

1. If the node has right child then return the left most node in the right sub tree.
2. Else, it goes up from node until we find a node that is to the left of its parent.
```TREENODE* Successor(TREENODE* node) const
{
// return the left most node in the right sub tree
if(node->Right != Nil)
return Min(node->Right);
// go up from node until we find a node that is the left of its parent
TREENODE* Parent = node->Parent;
while(Parent != Nil && node == Parent->Right)
{
node = Parent;
Parent = node->Parent;
}
return Parent;
}```

You can use the `Successor` function with the `Min` function to iterate tree nodes in ascending order.

#### Delete function

`Delete` function has three cases, I found it too complicated, and I hope I can describe it, The three cases are:

1. The node has no child, so we just remove it. As in you can see in figure 2, node K can be deleted by just resetting the pointer from node J.
2. The node has one child, so we need to splice it as node H in figure 2, we should make node D point to node F as a right child, and set node F parent to point to node D
3. The node has two children, so we choose its successor to take its position, and splice its successor (join successor parent and child, like the previous case) . For example, if we delete node C at figure 2, we get node C successor (D), so we will splice node D so that node I and H will be connected directly and node C will take node C place as in Figure 3.

Code in the `Delete` is optimized to handle the three cases altogether, so I find it hard to describe it here, but you can try to apply the code in each case and read comments carefully, and you will find it working well.

```void Delete(TREENODE* node)
{
TREENODE *pSplice = (node->Left == Nil ||
node->Right == Nil)?node:Successor(node);
TREENODE *pChild = pSplice->Childs[pSplice->Left == Nil];
// connect child to spliced node parent
if(pChild != Nil)
pChild->Parent = pSplice->Parent;
// connect spliced node parent to child
if(pSplice->Parent == Nil)
Root = pChild;
else
pSplice->Parent->Childs[pSplice !=
pSplice->Parent->Childs[0]] = pChild;
// put spliced node in place of node (if required)
if(pSplice != node)
{    // copy spliced node
*node = *pSplice;
// delete the spliced node
delete pSplice;
}
else
// delete the node
delete node;
Count--;
}```

#### Iterate Tree Nodes

You can call `Min(Tree.Root)` and then `Successor` in a loop to retrieve all nodes in order (ascending):

```TREENODE* node = Min(Root);
while(node)
{
// use node here then get next one
node = Successor(node);
}```

And in the same way you can call `Max(Tree.Root)` and then `Predecessor` in a loop to retrieve all nodes in a reversed order (descending):

```TREENODE* node = Max(Root);
while(node)
{
// use node here then get next one
node = Predecessor(node);
}```

## Class Usage

`CBinaryTree` usage is very simple, we just need to decide the `KEY` and `DATA` data types, then you can define the class, but you must choose a `KEY` that supports the `compare` function as it is used in the `Insert` and `Search` functions. For example:

```CBiaryTree<string, LPCSTR, int, int> tree;
tree.NoRepeat = true;
for(...)
{
// ... fill str in some way
tree.Insert(str);
}```

class `String` of the STL supports the `compare` function, but in some cases you have to add it yourself, as in case of integers' sort:

```class CInt
{
public:
int m_nKey;
int compare(int nKey)
{ return nKey == m_nKey ? 0 : (nKey >= m_nKey ? -1 : 1); }
void operator=(int nKey) { m_nKey = nKey; }
bool operator==(int nKey) { return m_nKey == nKey; }
};

CBiaryTree<CInt, int, int, int> tree;
tree.NoRepeat = true;
for(...)
{
// ... fill n in some way
tree.Insert(n);
}```

## Tree Load Balancing

Tree balancing can be achieved using many techniques. In my class here, I am using Red-Black Tree functions for the insertion in the tree. `Red-Black Tree` simply depends on keep tree height short as possible, as the search and the insertion operations time depend on the tree height. As in the following figure, if the sequence (C, A, B) is added to the tree, the height will be like case 1, but if we have an operation to change to the valid tree in case 3, it will be good as the tree height reduced.

So, I have included the functions `LeftRotate`, `RightRotate`, and `RBInsert` to can balance the tree functions.

## Sample Demo

The attached source zip file with article contains a sample that parse any folder in a recursive function and parse all its files with the extension specified in the extensions editor (any text files format), and it adds all files tokens to a binary tree. Then you can navigate all tree tokens through the tree control. You can test it in VC6 or 7.1, or just run the attached exe, and don't hesitate to mail me for any help.

## Source code files

1. BinaryTree.h: Binary Tree code.
2. RBTree.h: Red-Black Tree code.

## References

[1] Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, Algorithms 1990

## Thanks to...

I awe a lot to my colleagues for helping me in implementing and testing this code. (JAK)

## License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

## About the Author

 Other Egypt

 Pro

## Comments and Discussions

 First Prev Next
 Full Text Search Sunil Kumawat11-Jun-12 2:50 Sunil Kumawat 11-Jun-12 2:50
 License? Vu H. Pham25-Oct-10 5:20 Vu H. Pham 25-Oct-10 5:20
 Re: License? Vu H. Pham25-Oct-10 5:21 Vu H. Pham 25-Oct-10 5:21
 Key update MKirkove29-Jun-10 23:47 MKirkove 29-Jun-10 23:47
 where is code? efvallejocando20-Apr-10 8:11 efvallejocando 20-Apr-10 8:11
 How to defined Root? Hoang Nam S2-Jul-08 19:16 Hoang Nam S 2-Jul-08 19:16
 urgent, need help right away ricky sam1-May-08 11:49 ricky sam 1-May-08 11:49
 Interesting article.. Fresric Bouemont24-Feb-08 23:52 Fresric Bouemont 24-Feb-08 23:52
 red black tree code in c++ jalalp29-May-07 10:54 jalalp 29-May-07 10:54
 Thanks Mr_Noob18-Apr-07 13:59 Mr_Noob 18-Apr-07 13:59
 Delete function for RB tree hansvz3-Jan-07 13:24 hansvz 3-Jan-07 13:24
 Re: Delete function for RB tree Hatem Mostafa3-Jan-07 19:05 Hatem Mostafa 3-Jan-07 19:05
 I think it works well as at this case - "node that you are deleting has no children" - the node has two children equal to Nil, and if u check the code u can find that:Nil = NewNode();That means Nil is not equal to NULL in RBTree so Nil is a normal leaf node. So, the code is right. U can test the demo version and try to delete leaf node.Many thanks
 Re: Delete function for RB tree hansvz4-Jan-07 9:24 hansvz 4-Jan-07 9:24
 Delete function question. mattdawg2-Dec-06 9:31 mattdawg 2-Dec-06 9:31
 Re: Delete function question. Hatem Mostafa2-Dec-06 18:56 Hatem Mostafa 2-Dec-06 18:56
 Public domain? jswoofer23-Oct-06 4:54 jswoofer 23-Oct-06 4:54
 Re: Public domain? Hatem Mostafa24-Oct-06 9:57 Hatem Mostafa 24-Oct-06 9:57
 I need a code for Data structure project in c++ ursimran14-Dec-05 0:42 ursimran 14-Dec-05 0:42
 Another Question... HumanOsc7-Jun-05 5:23 HumanOsc 7-Jun-05 5:23
 Question... HumanOsc1-Jun-05 3:40 HumanOsc 1-Jun-05 3:40
 Re: Question... HatemMostafa1-Jun-05 4:07 HatemMostafa 1-Jun-05 4:07
 Re: Question... HumanOsc1-Jun-05 4:45 HumanOsc 1-Jun-05 4:45
 Re: Question... HatemMostafa1-Jun-05 6:27 HatemMostafa 1-Jun-05 6:27
 Re: Question... HumanOsc1-Jun-05 9:28 HumanOsc 1-Jun-05 9:28
 Re: Question... HumanOsc1-Jun-05 10:41 HumanOsc 1-Jun-05 10:41
 Where is the code ? Karlheinz10-Jan-05 23:35 Karlheinz 10-Jan-05 23:35
 Re: Where is the code ? HatemMostafa11-Jan-05 7:22 HatemMostafa 11-Jan-05 7:22
 051011 : No more download ? Kochise10-Jan-05 22:05 Kochise 10-Jan-05 22:05
 Re: 051011 : No more download ? HatemMostafa11-Jan-05 7:20 HatemMostafa 11-Jan-05 7:20
 You are a Lord ! Kochise11-Jan-05 22:01 Kochise 11-Jan-05 22:01
 Re: You are a Lord ! Rajesh YG4-Aug-07 1:42 Rajesh YG 4-Aug-07 1:42
 What about STL ? Tom Collins22-Dec-04 23:44 Tom Collins 22-Dec-04 23:44
 Re: What about STL ? HatemMostafa24-Dec-04 19:48 HatemMostafa 24-Dec-04 19:48
 Re: What about STL ? yafan12-Jan-05 4:09 yafan 12-Jan-05 4:09
 Re: What about STL ? .:floyd:.23-Jan-05 6:09 .:floyd:. 23-Jan-05 6:09
 Are you sure about the worst case is O(log n)? Don Clugston22-Dec-04 12:14 Don Clugston 22-Dec-04 12:14
 Re: Are you sure about the worst case is O(log n)? HatemMostafa22-Dec-04 20:44 HatemMostafa 22-Dec-04 20:44
 Last Visit: 31-Dec-99 19:00     Last Update: 17-Jan-17 13:42 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170117.1 | Last Updated 23 Jan 2005
Article Copyright 2004 by Hatem Mostafa
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid