二叉树介绍
4.52/5 (14投票s)
2007年3月5日
7分钟阅读
110157
3094
二叉树的描述和一维数据中的快速搜索
引言
在本文中，我介绍了二叉树和分层数据结构。在示例项目中，我将二叉树与 qsort 进行了比较。二叉树使用 C++ 模板定义。它可以在任何支持 C++ 的环境中使用，并且适用于支持数据比较运算符 `<` 和 `>` 的任何数据类型。描述易于理解。要使用该模板，您需要在 C++ 项目中包含 *BTree.h*。为了平衡和优化数据插入，我使用了一种简单的重新排序方法，而不是 红黑树 和 AVL 树。优点是数据插入和树创建所需的时间略少。即使不是完美平衡，此方法也能确保数据搜索需要 `log2` 次比较操作。
我主要关注多维数据结构，因此我主要使用易于泛化为 N 维的算法。
背景
二叉树是分层数据结构，允许在一维数据中进行插入和快速的最近邻搜索。它可以用作 qsort 和二分搜索的替代方法，以快速查找数据数组中最接近的点。二叉树的优点是结构简单，可以泛化为多个维度——即所谓的 `KD Tree`。因此，了解它的工作原理以及它如何执行数据搜索很有帮助。我将保持解释清晰易懂。
首先，我们定义一个 `树`。树是由一组节点组成的数据结构。每个节点都有指向其他一些节点的链接，这些节点称为 `子节点` 和 `父节点`。它们之间的区别在于，子节点是根据某种 `准则` 选择的，而父节点链接仅仅保留了我们如何到达给定节点的历史记录。
二叉树有两个子节点——`Left` 和 `Right`，以及一个 `父节点`。父节点链接对于最近邻搜索和树的优化是必需的。
树的每个节点都包含某种类型的数据，其值为 `X`。左子节点的值 `X` 必须小于相应的右值——`X > Left->X` 和 `Right->X > X`。这是二叉树的基本准则。树还有一个 `Root`。根是唯一没有 `Parent` 的节点。当需要将一个值为 `X` 的新节点添加到树中时，我们总是从 `Root` 开始，并沿着树向下，直到到达一个空位置。每次通过一个节点时，我们通过将值 `X` 与节点的值进行比较来决定向左还是向右——如果 `X` 较小，我们向左走；如果 `X` 较大，我们向右走。
在上面的例子中，新值是 `100`。要找到这个值的位置，请按照树中的步骤操作。从根节点开始，我们检查 `100` 是小于还是大于 `127`。在这种情况下，它较小，所以我们向左走到值为 `111` 的节点。现在，`100` 小于 `111`，所以我们向左走到节点 `60`。这次 `100` 较大，但 `60` 没有 `Right` 子节点，它是一个空位置，所以我们将 `100` 附加到这里。
现在让我们看看二叉树如何用于一些有用的事情。让我们看看如何找到限定范围和最近邻。例如，我们选择一个新值 `125`。在两个现有树值之间，我们需要确定哪个是 `125`。同样，我们开始搜索 `125` 的 `Parent` 节点，经过几个步骤，我们到达节点 `115`。
现在很清楚，由于 `125` 是 `115` 的 `Right` 子节点，`125` 是最左侧邻居中最接近的。但搜索右值并不那么简单。在这种情况下，树的 `Root` 是 `127`。二叉树的规则是，限制值是第一个值大于 `125` 的 `Parent` 节点。所以我们必须向上遍历树，直到找到一个值大于 `125` 的 `Parent`。在某些情况下，节点可能只有一个限制邻居。下面给出了二叉树声明、数据插入和最近邻搜索的代码。
代码
二叉树的声明和实现位于 *BTree.h* 中。 `BTNode` 类包含 `insert` 和 `remove` 函数。模板类型是 `X`，带有两个指向 `left` 和 `right` 子节点的指针，以及一个指向 `parent` 的指针。我对标准二叉树只做了两个小的扩展，并添加了一个成员属性——定义为 `bool` 的 `ParentOrientation`，以及一个成员函数——用于优化插入的 `moveup()`。
//Binary Tree Node
template <class>
class BTNode
{
public:
BTNode();
BTNode(Xtype x);
bool Delete_Tree(BTNode<xtype>* Root);
BTNode(BTNode<xtype>* k1, BTNode<xtype>* k2);
BTNode<xtype> *Left, *Right, *Parent;
BTNode<xtype>* place(BTNode<xtype>* T);
BTNode<xtype>* insert(Xtype x,bool&root_changed,bool optimize=true);
bool insert(BTNode<xtype>* node,bool&root_changed,bool optimize=true);
void remove();
int count_childs();
bool moveup();
Xtype x;
bool ParentOrientation ; //where is child WRT parent ? 0=left 1=right
};
`ParentOrientation` 成员用于优化插入和最近邻搜索。它标识子节点相对于其 `parent` 的方向；如果为 `0`，则子节点在父节点的左侧；如果为 `1`，则在右侧。当然，我们只需比较子节点和父节点的值即可确定，但由于比较运算符 `<` 和 `>` 可能很慢，我使用了这个标志来减少它们的使用。成员函数 `moveup()` 尝试将节点向上移动到树中。它改善了树的平衡并优化了 `insert` 操作。然后 `Insert` 看起来像这样。
//insert node to the tree, starts from current node
template <class>
bool
BTNode<xtype>::insert(BTNode<xtype>* node,bool&root_changed, bool optimize)
{
BTNode<xtype>* pNext = this;
BTNode<xtype>* pFather;
while(pNext) //do not insert if already exist
{
pFather = pNext;
if(node->x < pNext->x)
pNext = pNext->Left;
else if(node->x > pNext->x)
pNext = pNext->Right;
else
return false;
}
if(!pNext) //empty place, do not insert value twice
{
node->Parent = pFather;
if(node->x < pFather->x)
{
pFather->Left = node;
node->ParentOrientation = 0 ;
}
else
{
pFather->Right = node;
node->ParentOrientation = 1;
}
if(optimize)
root_changed = node->moveup();
else
root_changed = false ;
return true;
}
return false;
}
最近邻搜索在上一节中已经解释。以下是代码：
/* nearest neighbours search
input:
Root - the root of the tree
x - template type with search target value
output:
l - the left limiting value or INVALID_VALUE if there
is no neighbour to left
r - the right limiting value or INVALID_VALUE if there
is no neighbour to right
returns:
- the closest value to x
- INVALID_VALUE - empty tree
*/
template <class>
Xtype FindNearest(BTNode<xtype>* Root, Xtype x, Xtype* l, Xtype* r)
{
Xtype left,right;
BTNode<xtype>* pNext = Root;
BTNode<xtype>* pFather;
bool ParentOrientation ;
while(pNext)
{
pFather = pNext;
if(x<pnext->x)
{
pNext = pNext->Left;
ParentOrientation = false;
}
else if(x>pNext->x)
{
pNext = pNext->Right;
ParentOrientation = true;
}
else
{
*l = pNext->x;
*r = pNext->x;
return pNext->x;
}
}
if(!ParentOrientation) //x < pFather->x
{
right = pFather->x;
//go up in the tree and search for the left limit
ParentOrientation = pFather->ParentOrientation ;
pFather = pFather->Parent;
while(pFather && !ParentOrientation)
{
//search parent to the left
ParentOrientation = pFather->ParentOrientation ;
pFather = pFather->Parent;
}
if(!pFather)
{
*l = INVALID_VALUE; //no neighbour to the left
*r = right;
return right;
}
else
{
*l = pFather->x;
*r = right;
return (x-pFather->x < right-x ? pFather->x:right);
}
}
else //x > pFather->x
{
left = pFather->x;
// go up in the tree and search for the right limit
ParentOrientation = pFather->ParentOrientation ;
pFather = pFather->Parent;
while(pFather && ParentOrientation)
{
//search parent to the right
ParentOrientation = pFather->ParentOrientation ;
pFather = pFather->Parent;
}
if(!pFather)
{
*l = left;
*r = INVALID_VALUE; //no neighbour to the right
return left;
}
else
{
*l = left;
*r = pFather->x;
return (x-left < pFather->x-x ? left:pFather->x);;
}
}
return INVALID_VALUE; //empty tree
}
如上所述，树的优化是通过 `moveup()` 例程实现的。为什么需要优化？嗯，如果树中包含的值以随机（无序）序列出现，树将自然平衡。但是，不能保证值不会以某种非随机模式出现。例如，如果它是 `2,5,8,11`…，那么二叉树将变成一个链表，最近邻搜索将变成顺序搜索，这是无效的。有很多平衡方法——红黑树、AVL… 我更喜欢我自己的局部树优化，它消除了最坏的情况。下面的插图展示了它的工作原理：
这里，`N` 是要插入的节点，`P` 是它的父节点，`G` 是它的祖父节点。如果像上面左侧所示的两种情况，或者它的镜像情况那样发生，则可以将 `P` 或 `N` 向上移动，并将 `G` 向下移动到树中。三个节点——`N`、`P` 和 `G` 按照右侧所示重新排序。通过这种方式，树的高度减小，最坏的情况得到纠正，树的平衡得到改善。从我进行的测试中，我发现 `插入` 操作和树创建的速度慢不到 10%。如果你增加随机选择数据的平均高度，你会发现性能仍然慢 10%，但这个百分比随数据大小而增加，并确保平均高度始终是 log2N，其中 N 是数据大小。这意味着我们在大型数组（100,000）中查找值时将经过的平均路径约为 20，因为 2 的 20 次方是 100,000。项目源代码包含执行这些测试的应用程序。如果你想检查不同点的平均树高，请更改 `POINTS_NUM` 的数字，如果太大，请更改 `generate_random_point()` 例程。
许可证
本文未附加明确的许可证，但可能在文章文本或下载文件本身中包含使用条款。如有疑问，请通过下面的讨论区联系作者。
作者可能使用的许可证列表可以在此处找到。