数据结构中的树类型

电玩女神 2023-10-04 09:03 52阅读 0赞

##  ##

[发表评论][Link 1]/[ DSA][DSA] /作者：[ Neeraj Mishra][Neeraj Mishra]

在本文中，我们将学习树和数据结构中一些常见的树类型。

计算机科学中的树就像现实世界中的一棵树，唯一的区别是计算机科学中的树是颠倒的，根部在顶部，而分支从树的根部到叶子一直延伸。树数据结构可用于各种实际应用程序，因为它可以使用父子层次结构显示各种节点之间的关系。因此，它也被称为分层数据结构。它被广泛用于简化和加快搜索和排序操作。它被认为是最强大和最先进的数据结构之一。

树是一种非线性数据结构。可以使用各种原始或用户定义的数据类型来表示树。为了实现树，我们可以使用数组，链接列表，类或其他类型的数据结构。它是彼此相关的节点的集合。为了显示这种关系，节点与边连接。

![通用树结构][0ba8eb9b6e42aaa5da9da8b1d9976e91.png]

图1：常规树结构（[源][Link 2]）

**树中的关系：**

*  A是树的根
 *  A是B，C和D的父母
 *  B是A的孩子
 *  B，C和D是兄弟姐妹
 *  A是E，F，G，H和I的祖父母

**树的属性：**

*  每棵树都有一个称为根节点的特殊节点。根节点可用于遍历树的每个节点。之所以称为根，是因为该树仅起源于根。
 *  如果一棵树有N个顶点（节点），则边的数量总是比节点（顶点）的数量少1，即N-1。如果它有N-1个以上的边，则称为图而不是树。
 *  每个孩子只有一个父母，但父母可以有多个孩子。

### 数据结构中的树类型 ###

#### 普通树 ####

当树的层次结构上没有任何约束时，该树称为普通树。在“通用树”中，每个节点可以具有无限数量的子代。该树是所有其他类型树的超集。图1所示的树是“通用树”。

#### 二叉树 ####

二叉树是每个父母最多可以有两个孩子的树的类型。这些孩子被称为左孩子或右孩子。这是最常用的树之一。当对Binary树施加某些约束和属性时，它会导致许多其他广泛使用的树，例如BST（二进制搜索树），AVL树，RBT树等。随着我们的前进，我们将详细了解所有这些类型。

![二叉树][23f992747ae68162a5f42b7537ce0a77.png]

无花果2：二叉树（[来源][Link 3]）

#### 二进制搜索树 ####

二进制搜索树（BST）是二进制树的扩展，带有一些附加的约束。在BST中，节点的左子节点的值必须小于或等于其父节点的值，而右子节点的值始终大于或等于其父节点的值。二进制搜索树的此属性使其适合于搜索操作，因为在每个节点上，我们都可以准确地确定该值是在左子树中还是在右子树中。因此，它称为搜索树。

![二进制搜索树][89980178561979bcc6965703f4db08a1.png]

无花果3：二叉树（[Source][]）

#### AVL树 ####

AVL树是一种自平衡二进制搜索树。名称为AVL的是其发明者Adelson-Velshi和Landis的名字。这是第一棵动态平衡树。在AVL树中，为每个节点分配一个平衡因子，基于此平衡因子，可以计算树是否平衡。在AVL树中，节点的子节点的高度最多相差1。在AVL树中，有效的平衡因子为1、0和-1。将新节点添加到AVL树后，树变得不平衡，则进行旋转以确保树保持平衡。查找，插入和删除等常见操作在AVL树中花费O（log n）时间。它广泛用于查找操作。

![AVL树][AVL]

图4：[来源][Link 4]

#### 红黑树 ####

红黑是另一类自平衡树。之所以使用名称Red-Black，是因为根据Red-Black树的属性，将Red-Black树中的每个节点涂成红色或黑色。这样可以确保树保持平衡。尽管红黑树不是完全平衡的树，但是它的属性可确保搜索操作仅花费O（log n）时间。每当将新节点添加到Red-Black Tree时，如果需要维护Red-Black Tree的属性，则将旋转并再次绘制节点。

![红黑树][dcc5af0fbf733e26d520701ffcbe20ec.png]

图5：红黑树（[来源][Link 5]）

#### N元树 ####

在N元树中，一个节点可以具有的最大子节点数限制为N。由于二叉树中的每个节点最多具有2个子节点，因此二叉树是2元树。Trie数据结构是N元树的最常用实现之一。完整的N元树是其中节点的子代为0或N的树。完整的N元树是其中所有叶节点处于同一级别的树。

![N元树（5元树）][N_5]

图6：N元树（5元）

希望您对数据结构中一些常见的树类型有所了解。如果您有任何疑问，请随时在评论部分提问。

[Link 1]: https://www.thecrazyprogrammer.com/2019/09/types-of-trees-in-data-structure.html#respond
[DSA]: https://www.thecrazyprogrammer.com/category/dsa
[Neeraj Mishra]: https://www.thecrazyprogrammer.com/author/admin
[0ba8eb9b6e42aaa5da9da8b1d9976e91.png]: https://img-blog.csdnimg.cn/img_convert/0ba8eb9b6e42aaa5da9da8b1d9976e91.png
[Link 2]: https://algorithmtutor.com/Data-Structures/Tree/Tree-ADT/
[23f992747ae68162a5f42b7537ce0a77.png]: https://img-blog.csdnimg.cn/img_convert/23f992747ae68162a5f42b7537ce0a77.png
[Link 3]: https://static.javatpoint.com/ds/images/binary-tree.png
[89980178561979bcc6965703f4db08a1.png]: https://img-blog.csdnimg.cn/img_convert/89980178561979bcc6965703f4db08a1.png
[Source]: https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/2000px-Binary_search_tree.svg.png
[AVL]: https://img-blog.csdnimg.cn/img_convert/6687ec3eb00dee6ffc86f9b5c11bbae9.png
[Link 4]: https://upload.wikimedia.org/wikipedia/commons/thumb/a/ad/AVL-tree-wBalance_K.svg/262px-AVL-tree-wBalance_K.svg.png
[dcc5af0fbf733e26d520701ffcbe20ec.png]: https://img-blog.csdnimg.cn/img_convert/dcc5af0fbf733e26d520701ffcbe20ec.png
[Link 5]: https://upload.wikimedia.org/wikipedia/commons/thumb/6/66/Red-black_tree_example.svg/500px-Red-black_tree_example.svg.png
[N_5]: https://img-blog.csdnimg.cn/img_convert/7db61cf4101c4bd3ddb58db2bf4226ca.png