Всем привет ! Недавно (если быть точным - вчера) я задался вопросом, что же такое бинарное дерево поиска, как оно реализуется, какова логика и где это применимо, в частности, применимо ли это в PHP программировании. Порыскал по интернету, нашёл теоретическое описание (очень хорошее даёт википедия), и пример формирования его на различных языках. Вот чего я не смог найти - так это реализации его на PHP. Возможно это связано с тем, что дереву просто нет применения в PHP программировании - я не знаю. Но понять что это такое без примера понятной реализации (а в полной мере для меня понятен только PHP) я не мог. Интерес загрыз, и сегодня с самого утра я размышлял, как можно его реализовать, и под вечер сел и вот за пару часов написал вот такое вот чудо, прошу любить и жаловать. Реализовано только добавление потомка и поиск по ключу, т.к. этого хватило для понимания структуры дерева и основных его особенностей. Открыто для обсуждения: другие примеры реализации на PHP, и самое главное - применение на PHP (возможно в связке с БД) PHP: <?php function shuffle_assoc(&$array) { $keys = array_keys($array); shuffle($keys); foreach($keys as $key) { $new[$key] = $array[$key]; } $array = $new; return true; } /** * A tree-node class, contains all attributes for creating nodes */ class TreeNode { public $leftChild = null; public $rightChild = null; public $key = null; public $value = null; } /** * A binary search tree handler class, contains methods to manipulate with trees */ class BinarySearchTreeHandler { /** * The raw binary search tree variable * * @access protected * @var object */ protected $_tree = null; /** * The raw variable to store lines of tree-building log * * @access protected * @var array */ protected $_buildLog = array (); /** * The raw variable to store lines of tree-searching log * * @access protected * @var array */ protected $_searchLog = array (); /** * Class constructor, builds a binary search tree if array is given * * @access public * @param array given array, indexes must be integers */ public function __construct ($array = null) { if ($array !== null) { $this->buildTree ($array); } } /** * Method which build new binary search tree from given array * * @access public * @param array given array, indexes must be integers * @return obj binary search tree */ public function buildTree ($array) { $this->_tree = new TreeNode; shuffle_assoc ($array); foreach ($array as $key => $value) { $this->appendChild ($this->_tree, $key, $value); } return $this->_tree; } /** * Method to append new node to the tree * * @access public * @param viod object - binary search tree to append to * OR string - keyword SELF to append to already formed tree * OR boolean (null) - if we have ran into the bottom of the * tree and have to create a leaf * @param int key of new node * @param void value of new node */ public function appendChild ($tree, $key, $value) { if (is_string ($tree)) { if (strtoupper ($tree) === "SELF") { $tree = $this->_tree; } } if ($tree->key === null) { $tree->key = $key; $tree->value = $value; return $tree; } if ($tree->key > $key) { if ($tree->leftChild !== null) { $this->_buildLog[] = "key given (<strong>key</strong> = <u>" . $key . "</u>, <strong>value</strong> = <u>" . $value . "</u>) is smaller than key of current node (<em><strong>key</strong>: <u>" . $tree->key . "</u>, <strong>value</strong>: <u>" . $tree->value . "</u></em>), but this node already has LEFT CHILD. So <strong>passing</strong> key-value pair to the LEFT CHILD (<em><strong>key</strong>: <u>" . $tree->leftChild->key . "</u>, <strong>value</strong>: <u>" . $tree->leftChild->value . "</u></em>)."; return $this->appendChild ($tree->leftChild, $key, $value); } else { $this->_buildLog[] = "<strong>appending</strong> LEFT CHILD to node (<em><strong>key</strong>: <u>" . $tree->key . "</u>, <strong>value</strong>: <u>" . $tree->value . "</u></em>): <strong>key</strong> = <u>" . $key . "</u>, <strong>value</strong> = <u>" . $value . "</u>"; return $tree->leftChild = $this->appendChild (new TreeNode, $key, $value); } } if ($tree->key <= $key) { if ($tree->rightChild !== null) { $this->_buildLog[] = "key given (<strong>key</strong> = <u>" . $key . "</u>, <strong>value</strong> = <u>" . $value . "</u>) is bigger than key of current node (<em><strong>key</strong>: <u>" . $tree->key . "</u>, <strong>value</strong>: <u>" . $tree->value . "</u></em>), but this node already has RIGHT CHILD. So <strong>passing</strong> key-value pair to the RIGHT CHILD (<em><strong>key</strong>: <u>" . $tree->rightChild->key . "</u>, <strong>value</strong>: <u>" . $tree->rightChild->value . "</u></em>)."; return $this->appendChild ($tree->rightChild, $key, $value); } else { $this->_buildLog[] = "<strong>appending</strong> RIGHT CHILD to node (<em><strong>key</strong>: <u>" . $tree->key . "</u>, <strong>value</strong>: <u>" . $tree->value . "</u></em>): <strong>key</strong> = <u>" . $key . "</u>, <strong>value</strong> = <u>" . $value . "</u>"; return $tree->rightChild = $this->appendChild (new TreeNode, $key, $value); } } } /** * Method to search a node in binary search tree * * Tries to find a node in a binary search tree with given key * If finds - returns it's value * If fails - returns false * * @access public * @param int key of node to find * @param viod object - binary search tree to search in * OR string - keyword SELF to search in already formed tree * OR boolean (null) - if we fail to find what we look for * @return void false on failure, node value on success */ public function find ($key, $tree) { if (is_string ($tree)) { if (strtoupper ($tree) === "SELF") { $tree = $this->_tree; } } if (!is_object ($tree) AND $tree !== null) { $this->_searchLog[] = "given tree isn't a tree at all"; return false; } if ($tree === null) { $this->_searchLog[] = "requested key <strong>wasn't found</strong>"; return false; } if ($tree->key === $key) { $this->_searchLog[] = "given key <strong>found</strong>, returned value is " . $tree->value; return $tree->value; } if ($tree->key > $key) { $this->_searchLog[] = "given key (" . $key . ") is <strong>smaller</strong> than the key in the node (" . $tree->key . "), trying to find in LEFT child..."; return $this->find ($key, $tree->leftChild); } if ($tree->key < $key) { $this->_searchLog[] = "given key (" . $key . ") is <strong>bigger</strong> than the key in the node (" . $tree->key . "), trying to find in RIGHT child..."; return $this->find ($key, $tree->rightChild); } } /** * Returns requested log, buildLog by default * * @access public * @param string keyword for log, can be either "build" or "search" * @return string html log of operations */ public function getLog ($type = "build") { $type = strtolower ($type); if (!in_array ($type, array ("build", "search"))) { $type = "build"; } $name = "_" . $type . "Log"; return implode ("<br />", $this->$name); } }?> P.S. функция shuffle_assoc подсмотрена на php.net
Пример использования: PHP: <?php $a = array (8 => 1, 3 => 2, 5 => 3, 9 => 4, 18 => 5, 13 => 6, 16 => 7, 19 => 8, 1 => 9, 7 => 10, 12 => 11, 4 => 12, 10 => 13, 20 => 14, 11 => 15, 14 => 16, 6 => 17, 2 => 18, 15 => 19, 17 => 20); $b = new BinarySearchTreeHandler ($a); echo "<pre>"; var_dump ($b); echo "</pre>"; echo $b->getLog (); echo $s = $b->find (13, "SELF"); echo $b->getLog ("search"); $b->appendChild ("SELF", 34, "straight"); $b->appendChild ("SELF", 24, "dexterity"); $b->appendChild ("SELF", 35, "intellegence"); $b->appendChild ("SELF", 31, "someworlsd"); echo "<pre>"; var_dump ($b); echo "</pre>"; echo $b->getLog (); ?>