Data Structures Algorithms 简明教程

Tree Data Structure

Tree Data Structrue

树是一个具有基于层次结构的非线性抽象数据类型。它包括通过链接连接的存储数据的节点。树数据结构源自一个称为根节点的单个节点，并具有连接到根节点的子树。

A tree is a non-linear abstract data type with a hierarchy-based structure. It consists of nodes (where the data is stored) that are connected via links. The tree data structure stems from a single node called a root node and has subtrees connected to the root.

tree data structure

Important Terms

以下是关于树的一些重要术语。

Following are the important terms with respect to tree.

  1. Path − Path refers to the sequence of nodes along the edges of a tree.

  2. Root − The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node.

  3. Parent − Any node except the root node has one edge upward to a node called parent.

  4. Child − The node below a given node connected by its edge downward is called its child node.

  5. Leaf − The node which does not have any child node is called the leaf node.

  6. Subtree − Subtree represents the descendants of a node.

  7. Visiting − Visiting refers to checking the value of a node when control is on the node.

  8. Traversing − Traversing means passing through nodes in a specific order.

  9. Levels − Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.

  10. Keys − Key represents a value of a node based on which a search operation is to be carried out for a node.

Types of Trees

有三种类型的树：

There are three types of trees −

  1. General Trees

  2. Binary Trees

  3. Binary Search Trees

General Trees

通用树是无序树数据结构，其中根节点具有最小 0 或最大“n”个子树。

General trees are unordered tree data structures where the root node has minimum 0 or maximum ‘n’ subtrees.

通用树对其层次结构没有限制。因此，根节点充当所有其他子树的超集。

The General trees have no constraint placed on their hierarchy. The root node thus acts like the superset of all the other subtrees.

General Trees

Binary Trees

二叉树是在其中根节点最多只能容纳 2 个子树（左子树和右子树）的通用树。根据子节点的数量，二叉树分为三类。

Binary Trees are general trees in which the root node can only hold up to maximum 2 subtrees: left subtree and right subtree. Based on the number of children, binary trees are divided into three types.

Full Binary Tree

Full Binary Tree

  1. A full binary tree is a binary tree type where every node has either 0 or 2 child nodes.

Complete Binary Tree

Complete Binary Tree

  1. A complete binary tree is a binary tree type where all the leaf nodes must be on the same level. However, root and internal nodes in a complete binary tree can either have 0, 1 or 2 child nodes.

Perfect Binary Tree

Perfect Binary Tree

  1. A perfect binary tree is a binary tree type where all the leaf nodes are on the same level and every node except leaf nodes have 2 children.

Binary Trees

Binary Search Trees

二叉查找树具有二叉树的所有属性，还包括基于一些约束的额外属性，使其比二叉树更高效。

Binary Search Trees possess all the properties of Binary Trees including some extra properties of their own, based on some constraints, making them more efficient than binary trees.

二叉查找树 (BST) 中的数据总是以这样的方式存储：左子树中的值始终小于根节点中的值，右子树中的值始终大于根节点中的值，即左子树 < 根节点 ≤ 右子树。

The data in the Binary Search Trees (BST) is always stored in such a way that the values in the left subtree are always less than the values in the root node and the values in the right subtree are always greater than the values in the root node, i.e. left subtree < root node ≤ right subtree.

binary serach tree

Advantages of BST

  1. Binary Search Trees are more efficient than Binary Trees since time complexity for performing various operations reduces.

  2. Since the order of keys is based on just the parent node, searching operation becomes simpler.

  3. The alignment of BST also favors Range Queries, which are executed to find values existing between two keys. This helps in the Database Management System.

Disadvantages of BST

二叉查找树的主要缺点是，如果节点中的所有元素都大于或小于根节点，* 则树会变得不平衡 *。简而言之，树会完全向一侧倾斜。

The main disadvantage of Binary Search Trees is that if all elements in nodes are either greater than or lesser than the root node,* the tree becomes skewed*. Simply put, the tree becomes slanted to one side completely.

此 skewness 会使树成为链表而不是 BST，因为搜索操作的最坏情况时间复杂度变为 O(n)。

This skewness will make the tree a linked list rather than a BST, since the worst case time complexity for searching operation becomes O(n).

为了克服二叉查找树中的这种不平衡问题，引入了 Balanced Binary Search Trees 的概念。

To overcome this issue of skewness in the Binary Search Trees, the concept of Balanced Binary Search Trees was introduced.

Balanced Binary Search Trees

考虑一棵二叉查找树，左子树的高度为“m”，右子树的高度为“n”。如果 (m-n) 的值等于 0、1 或 -1，则该树被称为 Balanced Binary Search Tree 。

Consider a Binary Search Tree with ‘m’ as the height of the left subtree and ‘n’ as the height of the right subtree. If the value of (m-n) is equal to 0,1 or -1, the tree is said to be a Balanced Binary Search Tree.

这些树的设计方式是，一旦高度差超过 1，它们就会进行自我平衡。二叉查找树使用旋转作为自我平衡算法。有四种不同类型的旋转：左左旋转、右右旋转、左右旋转和右左旋转。

The trees are designed in a way that they self-balance once the height difference exceeds 1. Binary Search Trees use rotations as self-balancing algorithms. There are four different types of rotations: Left Left, Right Right, Left Right, Right Left.

有各种类型的自平衡二叉查找树 -

There are various types of self-balancing binary search trees −

  1. AVL Trees

  2. Red Black Trees

  3. B Trees

  4. B+ Trees

  5. Splay Trees

  6. Priority Search Trees