二叉排序树

二叉排序树

二叉排序树

像数组、链表、散列表等这种数据结构,数组查找性能高,但是插入、删除性能差.链表插入、删除性能高,但查找性能差.在不考虑散列冲突的话,散列表的插入、删除、查找性能都很高,但是前提是没有散列冲突,此外,散列表存储的数据是无序的,散列表的扩容非常麻烦,涉及到散列冲突时,性能不稳定,另外,散列表用起来爽,构造起来可不简单,要考虑散列函数的设计、哈希冲突的解决、扩容缩容等一系列问题.因此需要引入一种插入、删除、查找性能都不错,构建起来也不是很复杂,性能还很稳定的数据结构----二叉排序树.

概述

二叉排序树又称“二叉查找树”、“二叉搜索树”。二叉排序树:或者是一棵空树,或者是具有下列性质的二叉树:

若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
它的左、右子树也分别为二叉排序树。

二叉排序树的操作,插入,查找,删除


class Node {
public $value;
public $left;
public $right;
}
class BT {
/**
* 插入
* 如果是空树,则将其作为根节点
* 否则判断插入节点数据与当前节点数据的大小
* 如果小于当前节点,则递归遍历左子树,找到对应的位置插入
* 如果大于当前节点,则递归遍历右子树找到对应的位置插入
*/
public function level_order($root,$data)
{
if (!$root->value) {
$root->value = $data;
return;
}
while ($root) {
if ($data < $root->value) {
if (!$root->left) {
$new_left_node = '';
$new_left_node = new Node();
$new_left_node->value = $data;
$root->left =$new_left_node;
return;
}
$root = $root->left;
} elseif ($data > $root->value) {
if (!$root->right) {
$new_right_node = '';
$new_right_node = new Node();
$new_right_node->value = $data;
$root->right =$new_right_node;
return;
}
$root = $root->right;
}
}
}

/**
* 查找
*依次递归比较,直到直到对应节点,或者返回空,表示没有找到.
*/
public function find($root,$data)
{
while ($root) {
if ($data < $root->value) {
$root = $root->left;
} elseif ($data > $root->value) {
$root = $root->right;
} else {
return $root;
}
}
return null;
}

/**
* 删除
*二叉排序树的删除相对而言要复杂一些,需要分三种情况来处理:
* 第一种情况是,如果要删除的节点没有子节点,我们只需要直接将父节点中,
* 指向要删除节点的指针置为 null。比如图中的删除节点 55。
* 第二种情况是,如果要删除的节点只有一个子节点(只有左子节点或者右子节点),
* 我们只需要更新父节点中,指向要删除节点的指针,让它指向要删除节点的子节点就可以了。
* 比如图中的删除节点 13。
* 第三种情况是,如果要删除的节点有两个子节点,这就比较复杂了。
* 我们需要找到这个节点的右子树中的最小节点,把它替换到要删除的节点上。
* 然后再删除掉这个最小节点,因为最小节点肯定没有左子节点(如果有左子结点,那就不是最小节点了),
* 所以,我们可以应用上面两条规则来删除这个最小节点。
* 如上图
*/
public function delete($root,$data)
{
if (!$root) {
return;
}

$pp = null; // $root的父节点
// 查找待删除节点
while ($root && $root->value != $data) {
$pp = $root;
if ($root->value < $data) {
$root = $root->right;
} else {
$root = $root->left;
}
}
// 指定删除数据在二叉树中不存在
if ($root == null) {
return;
}

// 待删除节点有两个子节点
if ($root->left && $root->right) {
$minP = $root->right; // 右子树中的最小节点
$minPP = $root; // $minP 的父节点
// 查找右子树中的最小节点
while ($minP->left) {
$minPP = $minP;
$minP = $minP->left;
}
$root->value = $minP->value; // 将 $minP 的数据设置到 $root 中
$root = $minP; // 下面就变成删除 $minP 了
$pp = $minPP;
}

$child = null;
if ($root->left) {
$child = $root->left;
} elseif ($root->right) {
$child = $root->right;
} else {
$child = null;
}

if (!$pp) {
$root = $child; // 删除的是根节点
} elseif ($pp->left == $root) {
$pp->left = $child;
} else {
$pp->right = $child;
}
}
}
// 测试
$a = new Node();
$bst = new BT();
echo "</br>";
$bst->level_order($a,10);
$bst->level_order($a,9);
$bst->level_order($a,13);
$bst->level_order($a,7);
$bst->level_order($a,11);
$bst->level_order($a,12);


//二叉树插入
var_dump($a);


//二叉树查找
$result = $bst->find($a,13);
var_dump($result);

//二叉树删除
$bst->delete($a,12);
var_dump($a);

二叉排序树的时间复杂度

不论是插入、删除、还是查找,二叉排序树的时间复杂度都等于二叉树的高度,最好的情况当然是满二叉树或完全二叉树,此时根据完全二叉树的特性,时间复杂度是O(logn),性能相当好,最差的情况是二叉排序树退化为线性表(斜树),此时的时间复杂度是 O(n),所以二叉排序树的形状也很重要,不同的形状会影响最终的操作性能.