Python二叉树查找：千树梨花一夜春，排序与平衡树详解？

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

什么是树表查询？借助具有特殊性质的质量的树数据结构进行关键字查找。

涉及到的特殊结构质量的树包括：+ 二叉排序树+ 平衡二叉树

使用树结构存储数据时，因其本身特性，在查找数据时效率较高。

什么是树表查询？

借助具有特殊性质的树数据结构进行关键字查找。

本文所涉及到的特殊结构性质的树包括：

• 二叉排序树。
• 平衡二叉树。

使用上述树结构存储数据时，因其本身对结点之间的关系以及顺序有特殊要求，也得益于这种限制，在查询某一个结点时会带来性能上的优势和操作上的方便。

树表查询属于动态查找算法。

所谓动态查找，不仅仅能很方便查询到目标结点。而且可以根据需要添加、删除结点，而不影响树的整体结构，也不会影响数据的查询。

本文并不会深入讲解树数据结构的基本的概念，仅是站在使用的角度说清楚动态查询。阅读此文之前，请预备一些树的基础知识。

1. 二叉排序树

二叉树是树结构中具有艳明特点的子类。

二叉树要求树的每一个结点（除叶结点）的子结点最多只能有 2 个。在二叉树的基础上，继续对其进行有序限制则变成二叉排序树。