数据结构概述|S2（二叉树，BST，堆和哈希）

我们已经讨论过数组, 链接列表, 队列和堆栈概述。在本文中, 将讨论以下数据结构。

5.二叉树

6.二叉搜索树

7.二叉堆

9.散列

二叉树

与数组, 链表, 堆栈和队列(它们是线性数据结构)不同, 树是分层数据结构。

二叉树是一种树数据结构, 其中每个节点最多具有两个子节点, 称为左子节点和右子节点。它主要使用链接来实现。

二叉树表示：

一棵树由指向树中最高节点的指针表示。如果树为空, 则root的值为NULL。二叉树节点包含以下部分。

1.资料

2.指向左孩子的指针

3.指向正确的孩子的指针

可以通过两种方式遍历二叉树：

深度优先遍历：顺序(左-右-根), 预排序(左-左-右)和后序(左-右-根)

广度优先遍历：级别顺序遍历

二叉树属性： 

The maximum number of nodes at level ‘l’ = 2l-1.

Maximum number of nodes = 2h + 1 – 1.
Here h is height of a tree. Height is considered 
as the maximum number of edges on a path from root to leaf.

Minimum possible height =  ceil(Log2(n+1)) - 1  

In Binary tree, number of leaf nodes is always one 
more than nodes with two children.

Time Complexity of Tree Traversal: O(n)

例子：通常使用二叉树或二叉树的一个原因是要形成层次结构。它们在文件结构中很有用, 其中每个文件都位于特定目录中, 并且存在与文件和目录关联的特定层次结构。使用树的另一个示例是存储分层对象, 例如JavaScript文档对象模型, 将HTML页面视为一棵树, 其中标签嵌套作为父子关系。

二叉搜索树

在二叉搜索树中是具有以下附加属性的二叉树：

1.节点的左子树仅包含键值小于节点键值的节点。

2.节点的右子树仅包含键大于该节点的键的节点。

3.左子树和右子树也都必须是二叉搜索树。

时间复杂度：

Search :  O(h)
Insertion : O(h)
Deletion : O(h)
Extra Space : O(n) for pointers

h: Height of BST
n: Number of nodes in BST

If Binary Search Tree is Height Balanced, then h = O(Log n) 

Self-Balancing BSTs such as AVL Tree, Red-Black
Tree and Splay Tree make sure that height of BST 
remains O(Log n)

BST提供适度的访问/搜索(比"链表"更快, 比阵列慢)。

BST提供适度的插入/删除(比数组更快, 比链接列表慢)。

例子：它的主要用途是在搜索应用程序中, 其中数据不断输入/离开, 并且数据需要按排序顺序打印。例如, 在电子商务网站的实施中, 其中添加了新产品或产品缺货, 并且所有产品均按排序顺序列出。

二叉堆

二叉堆是具有以下属性的二叉树。

1)这是一棵完整的树(除了最后一个级别, 所有级别都已完全填充, 并且最后一个级别的所有键都尽可能保留)。 Binary Heap的此属性使它们适合存储在数组中。

2)二叉堆是最小堆或最大堆。在最小二叉堆中, 在二叉堆中存在的所有密钥中, 根密钥必须最小。对于二叉树中的所有节点, 相同的属性必须递归地为true。最大二叉堆类似于最小堆。它主要使用数组来实现。

Get Minimum in Min Heap: O(1) [Or Get Max in Max Heap]
Extract Minimum Min Heap: O(Log n) [Or Extract Max in Max Heap]
Decrease Key in Min Heap: O(Log n)  [Or Decrease Key in Max Heap]
Insert: O(Log n) 
Delete: O(Log n)

范例：

用于实现高效的优先级队列, 而这些优先级队列又用于调度操作系统中的进程。优先队列还用于Dijikstra和Prim的图算法中。

堆数据结构可用于有效地查找数组中的k个最小(或最大)元素, 合并k个排序的数组, 流的中位数等。

堆是一种特殊的数据结构, 不能用于搜索特定元素。

HashingHash函数：

将给定的大输入键转换为小的实际整数值的函数。映射的整数值用作哈希表中的索引。一个好的哈希函数应具有以下属性

1)高效可计算。

2)应均匀分配键(每个表在每个键上的位置均等)

哈希表：一个数组, 用于存储指向与给定电话号码对应的记录的指针。如果没有现有电话号码的哈希函数值等于该条目的索引, 则哈希表中的条目为NIL。

冲突处理：由于哈希函数会为我们提供一个较小的数字, 而这个键是一个大整数或字符串, 因此两个键可能会产生相同的值。新插入的键映射到哈希表中已占用的插槽的情况称为冲突, 必须使用某种冲突处理技术来处理。以下是处理冲突的方法：

链接：想法是使哈希表的每个单元指向具有相同哈希函数值的记录的链表。链接很简单, 但是需要在表外增加内存。

开放式寻址：在开放式寻址中, 所有元素都存储在哈希表本身中。每个表条目都包含一条记录或NIL。在搜索元素时, 我们将逐个检查表插槽, 直到找到所需的元素, 或者很明显该元素不在表中。

Space : O(n)
Search    : O(1) [Average]    O(n) [Worst case]
Insertion : O(1) [Average]    O(n) [Worst Case]
Deletion  : O(1) [Average]    O(n) [Worst Case]

对于所有操作, 散列似乎比BST更好。但是在散列中, 元素是无序的, 而在BST中, 元素是以有序的方式存储的。同样, BST易于实现, 但是散列函数的生成有时可能非常复杂。在BST中, 我们还可以有效地找到价值的底限和最高限度。

范例：散列可用于从一组元素中删除重复项。也可以用来查找所有项目的频率。例如, 在Web浏览器中, 我们可以使用哈希检查访问的URL。在防火墙中, 我们可以使用哈希检测垃圾邮件。我们需要对IP地址进行哈希处理。在O(1)时间内想要search()insert()和delete()的任何情况下都可以使用散列。

本文作者：

阿比拉拉·史密斯(Abhiraj Smit)

。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。