如何深入剖析普通二叉搜索树的原理与结构？

本文共计2151个文字，预计阅读时间需要9分钟。

二叉搜索树概述：二叉搜索树是一种具有特定特性的二叉树。它可以是空树，若不为空，则：若左子树不为空，则左子树上所有节点的值均小于它的根节点的值；若右子树不为空，则右子树上所有节点的值均大于它的根节点的值。

二叉搜索树概述

二叉搜索树是一种具有特殊性质的二叉树。二叉搜索树可以是一棵空树，若不为空树，其：

• 若左子树不为空，则左子树所有的节点值小于根节点值；
• 若右子树不为空，则右子树所有的节点值大于根节点值。

与二叉树一样，二叉搜索树也是递归定义的，二叉搜索树的左右子树都是二叉搜索树。

二叉搜索树的结构

二叉搜索树的结构是一棵二叉树，其左子树的节点值都小于根节点值，右子树的节点值都大于根节点值。二叉搜索树使用链式结构进行实现。

两种二叉搜索树及定义

二叉搜索树常用有两种模型：Key模型和Key-Value模型。

Key模型的二叉搜索树的节点只需要存储一个关键码Key即可，可以将关键码理解为需要搜索的值。这种模型主要用于解决快速判断一个值在不在集合中的问题。