数据结构中的二叉树作为字典

当我们尝试实现抽象数据类型字典时，节点将与值相关联。字典基本上是一组键，该键必须是从全序集合中选出的元素。可能与每个键相关联的其他信息，但这不会导致任何概念理解。

如果使用树实现字典，那么每个节点将保存唯一键。在这里，对于树中的每个节点 u，每个键 u.l 严格小于 u.k。并且 u.r 中的每个键严格大于 u.k。一棵树根据这种被称为二叉查找树的不变性进行组织。

这种不变性的一个主要优势是，可以使用中序遍历在线性时间内查找已排序的键列表。这可以如下递归定义——一棵空树，什么也不做，否则首先在左子树上递归，取根，并报告它。然后递归到右子树。

我们可以对二叉查找树执行多项操作。搜索可以基于树的高度进行。搜索是所有其他操作中更重要的操作。

更新于：2020 年 8 月 11 日

887 次浏览

职业生涯启航

完成课程并获得认证

开始
广告