树形数据结构
树形数据结构
树形数据结构是一种非线性的抽象数据类型，具有基于层次结构的结构。它由通过链接连接的节点（数据存储的位置）组成。树形数据结构源于一个称为根节点的单个节点，并具有连接到根节点的子树。
重要术语
以下是与树形相关的重要术语。
路径 −路径是指沿着树的边缘的节点序列。
根 − 树顶部的节点称为根节点。每棵树只有一个根节点，并且从根节点到任何节点都有一条路径。
父节点 − 除根节点外，任何节点都有一条向上的边连接到称为父节点的节点。
子节点 − 给定节点下方通过其向下的边连接的节点称为其子节点。
叶子节点 − 没有任何子节点的节点称为叶节点。
子树 − 子树表示节点的后代。
访问 −访问是指在控制节点上时检查节点的值。
遍历 − 遍历是指按特定顺序遍历节点。
层级 − 节点的层级表示节点的代数。如果根节点位于层级 0，则其下一个子节点位于层级 1，其孙节点位于层级 2，依此类推。
键 − 键表示节点的值，基于该值对节点执行搜索操作。
树的类型
树有三种类型 −
通用树
二叉树
二叉搜索树
通用树
通用树是一种无序树形数据结构，其根节点至少有 0 个子树，最多有 n 个子树。
通用树的层次结构没有任何限制。因此，根节点就像所有其他子树的超集。
二叉树
二叉树是一种通用树，其根节点最多只能容纳 2 个子树：左子树和右子树。根据子节点的数量，二叉树分为三种类型。
满二叉树
满二叉树是一种二叉树类型，其中每个节点都有 0 个或 2 个子节点。
完全二叉树
完全二叉树是一种二叉树类型，其中所有叶节点都必须位于同一层。然而，完全二叉树的根节点和内部节点可以有 0 个、1 个或 2 个子节点。
完美二叉树
完美二叉树是一种二叉树类型，其中所有叶节点都位于同一层，并且除叶节点外的每个节点都有 2 个子节点。
二叉搜索树
二叉搜索树拥有二叉树的所有属性，此外还基于一些约束条件，额外添加了一些属性，这使得它们比二叉树更高效。
二叉搜索树 (BST) 中的数据始终以这样的方式存储：左子树的值始终小于大于根节点的值，且右子树的值始终大于根节点的值，即左子树 < 根节点 ≤ 右子树。
二叉搜索树 (BST) 的优势
二叉搜索树比二叉树更高效，因为执行各种操作的时间复杂度降低了。
由于键的顺序仅基于父节点，因此搜索操作变得更简单。
二叉搜索树 (BST) 的对齐特性也有利于范围查询，范围查询用于查找两个键之间存在的值。这有助于数据库管理系统。
二叉搜索树 (BST) 的缺点
二叉搜索树的主要缺点是，如果节点中的所有元素都大于或小于根节点，树就会变得倾斜。简而言之，树会完全向一侧倾斜。
这种倾斜会使树变成链表而不是二叉搜索树，因为搜索操作的最坏情况时间复杂度变为 O(n)。
为了克服二叉搜索树的倾斜问题，引入了平衡二叉搜索树的概念。
平衡二叉搜索树
考虑一棵二叉搜索树，其左子树的高度为"m"，右子树的高度为"n"。如果 (m-n) 的值等于 0、1 或 -1，则该树被称为平衡二叉搜索树。
树的设计方式是，一旦高度差超过 1，它们就会自平衡。二叉搜索树使用旋转作为自平衡算法。旋转有四种不同的类型：左左、右右、左右、右左。
自平衡二叉搜索树有多种类型 −
