- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- The left and right subtree must each also be a binary tree.
- There must be no duplicate nodes.
In Following case, We use Binary Search Tree
They can be used as a quick way to sort data. Insert data into a binary search tree at O(log(n)). Then traverse the tree in order to sort them.
/** Create Node Class **/
class Node
{
public $parent = null;
public $left = null;
public $right = null;
public $data = null;
public function __construct($data)
{
$this->data = $data;
}
public function __toString()
{
return $this->data;
}
}
/** Create BinarySearchTree Class **/
class BinarySearchTree
{
protected $_root = null;
protected function _insert(&$new, &$node)
{
if ($node == null) {
$node = $new;
return;
}
if ($new->data <= $node->data) {
if ($node->left == null) {
$node->left = $new;
$new->parent = $node;
} else {
$this->_insert($new, $node->left);
}
} else {
if ($node->right == null) {
$node->right = $new;
$new->parent = $node;
} else {
$this->_insert($new, $node->right);
}
}
}
protected function _search(&$target, &$node)
{
if ($target == $node) {
return 1;
} else if ($target->data > $node->data && isset($node->right)) {
return $this->_search($target, $node->right);
} else if ($target->data <= $node->data && isset($node->left)) {
return $this->_search($target, $node->left);
}
return 0;
}
public function insert($node)
{
$this->_insert($node, $this->_root);
}
public function search($item)
{
return $this->_search($item, $this->_root);
}
}
/* Add Data in Nodes **/
$node1 = new Node(43);
$node2 = new Node(52);
$node3 = new Node(44);
$node4 = new Node(47);
$node5 = new Node(65);
/* Create Object **/
$obj = new BinarySearchTree();
$obj->insert($node1);
$obj->insert($node2);
$obj->insert($node3);
$obj->insert($node4);
$obj->insert($node5);
