Tag Archives: Binary trees

Computer Algorithms: Finding the Lowest Common Ancestor

algorithms, data structures, , , , , , , , , , , , ,

Introduction

Here’s one task related to the tree data structure. Given two nodes, can you find their lowest common ancestor?

In a matter of fact this task always has a proper solution, because at least the root node is a common ancestor of all pairs of nodes. However here the task is to find the lowest one, which can be quite far from the root.

Finding the Lowest Common Ancestor
Finding the Lowest Common Ancestor

We don’t care what kind of trees we have. However the solution, as we will see, can be very different depending on the tree type. Indeed finding the lowest common ancestor can have linear complexity for binary search trees, which isn’t true for ordinary trees. Continue reading Computer Algorithms: Finding the Lowest Common Ancestor →

Computer Algorithms: Balancing a Binary Search Tree

algorithms, data structures, , , , , , , , , , , , , , , , , , , ,

Introduction

The binary search tree is a very useful data structure, where searching can be significantly faster than searching into a linked list. However in some cases searching into a binary tree can be as slow as searching into a linked list and this mainly depends on the input sequence. Indeed in case the input is sorted the binary tree will seem much like a linked list and the search will be slow.

Inserting into a binary search tree
A binary search tree may seem much like a linked lists if the input is nearly sorted!

To overcome this we must change a bit the data structure in order to stay well balanced. It’s intuitively clear that the searching process will be better if the tree is well branched. This is when finding an item will become faster with minimal effort.

Balanced tree
Searching into a balanced tree is significantly faster than searching into a non-balanced tree!

Since we know how to construct a binary search tree the only thing left is to keep it balanced. Obviously we will need to re-balance the tree on each insert and delete, which will make this data structure more difficult to maintain compared to non-balanced search trees, but searching into it will be significantly faster. Continue reading Computer Algorithms: Balancing a Binary Search Tree →

Computer Algorithms: Binary Search Tree

algorithms, data structures, , , , , , , , , , , , , , , , , , , ,

Introduction

Constructing a linked list is a fairly simple task. Linked lists are a linear structure and the items are located one after another, each pointing to its predecessor and its successor. Almost every operation is easy to code in few lines and doesn’t require advanced skills. Operations like insert, delete, etc. over linked lists are performed in a linear time. Of course on small data sets this works fine, but as the data grows these operations, especially the search operation becomes too slow.

Indeed searching in a linked list has a linear complexity and in the worst case we must go through the entire list in order to find the desired element. The worst case is when the item doesn’t belong to the list and we must check every single item of the list even the last one without success. This approach seems much like the sequential search over arrays. Of course this is bad when we talk about large data sets.

Search over Linked Lists and Arrays
Sequential search over arrays seems much like searching in linked lists and it is a basically ineffective opration!
Continue reading Computer Algorithms: Binary Search Tree →

Construct a Sorted PHP Linked List

micro tutorial, PHP, web development, , , , , , , , , ,

This is really a draft, but I somehow decided to post it. Here’s a simple linked list in PHP, where only the add() method is slightly different. When you have an item to add it’s placed on the “right” place – the result is a sorted list.

Few notes before the code! This list is designed for integers, but I plan to “extend” it somehow and it can be improved a lot. In my future posts I’ll post something more about the complexity of the algorithm and an analysis of it.

class Node
{
    public $data;
    public $next;
    public $prev;
 
    public function __construct($data, $prev, $next)
    {
        $this->data = $data;
        $this->prev = $prev;
        $this->next = $next;
    }
}
 
class LinkedList
{
    protected $front = null;
 
    public function add($data)
    {
        if (!$this->front) {
            $node = new Node($data, null, null);
            $this->front = &$node;
        } else {
            if ($data < $this->front->data) {
                $node = new Node($data, null, $this->front);
                $this->front = $node;
                return;
            }
 
            $current = $this->front;
            while ($current) {
                if ($current->data < $data && isset($current->next) && $current->next->data > $data) {
                    $node = new Node($data, $current, $current->next);
                    $current->next = $node;
                }
                if ($current->data < $data && !isset($current->next)) {
                    $node = new Node($data, $current, $current->next);
                    $current->next = $node;
                }
                $current = $current->next;
            }
        }
    }
 
    public function printl()
    {
        $current = &$this->front;
        while($current) {
            echo $current->data, '<br />';
            $current = $current->next;
        }
    }
}
 
$list = new LinkedList();
$list->add(13);
$list->add(14);
$list->add(15);
$list->add(11);
$list->add(12);
$list->add(17);
$list->add(10);
$list->add(16);
 
$list->printl();