Data Structures Algorithms 简明教程
Tree Data Structure
Important Terms
以下是关于树的一些重要术语。
-
Path - 路径是指沿着树的边的一系列节点。
-
Root - 树顶部的节点称为根。每棵树只有一个根，且从根节点到任何节点只有一条路径。
-
Parent - 除了根节点之外的任何节点向上只有一个边到一个称为父节点的节点。
-
Child - 通过其向下边缘连接在给定节点之下的节点称为其子节点。
-
Leaf - 没有子节点的节点称为叶节点。
-
Subtree - 子树表示节点的后代。
-
Visiting - 访问是指在控件位于节点上时检查节点的值。
-
Traversing − 遍历指按照特定顺序经过节点。
-
Levels - 节点的级别表示节点的代。如果根节点位于第 0 级，则其下一个子节点位于第 1 级，而其孙节点位于第 2 级，依此类推。
-
Keys - 键表示节点的值，基于该值对节点执行搜索操作。
Binary Trees
二叉树是在其中根节点最多只能容纳 2 个子树（左子树和右子树）的通用树。根据子节点的数量，二叉树分为三类。
Full Binary Tree
-
满二叉树是一种二叉树类型，其中每个节点要么有 0 个，要么有 2 个子节点。
Complete Binary Tree
-
完全二叉树是一种二叉树类型，其中所有的叶子节点必须位于同一层级。然而，完全二叉树中的根节点和内部节点可以有 0 个、1 个或 2 个子节点。
Perfect Binary Tree
-
完美二叉树是一种二叉树类型，其中所有的叶子节点都位于同一层级，且除叶子节点外的每个节点都有 2 个子节点。
Binary Search Trees
二叉查找树具有二叉树的所有属性，还包括基于一些约束的额外属性，使其比二叉树更高效。
二叉查找树 (BST) 中的数据总是以这样的方式存储：左子树中的值始终小于根节点中的值，右子树中的值始终大于根节点中的值，即左子树 < 根节点 ≤ 右子树。
Advantages of BST
-
二叉查找树比二叉树更有效率，因为执行各种操作的时间复杂度降低了。
-
由于键的顺序仅基于父节点，因此搜索操作变得更简单。
-
BST 的对齐方式也支持范围查询，该查询用于查找存在于两个键之间的值。这有助于数据库管理系统。
Disadvantages of BST
二叉查找树的主要缺点是，如果节点中的所有元素都大于或小于根节点，* 则树会变得不平衡 *。简而言之，树会完全向一侧倾斜。
此 skewness 会使树成为链表而不是 BST，因为搜索操作的最坏情况时间复杂度变为 O(n)。
为了克服二叉查找树中的这种不平衡问题，引入了 Balanced Binary Search Trees 的概念。