十二、树
访问 www.coding-time.cn 阅读原文动画效果，体验更佳。
1. 二叉搜索树（Binary Search Tree）
在计算机科学中，二叉搜索树（Binary Search Tree，BST），有时也被称为有序或排序二叉树，是一种特殊的容器数据结构，用于在内存中存储“项”（例如数字、名称等）。它们允许快速查找、添加和删除项，并可用于实现动态集合或查找表，通过键（例如通过名称查找人的电话号码）来查找项。
二叉搜索树保持其键的有序性，以便查找和其他操作可以利用二分查找的原理：在树中从根到叶子进行遍历，通过与树节点中存储的键进行比较，并根据比较结果决定是继续在左子树还是右子树中查找。平均而言，这意味着每次比较可以跳过树的大约一半的节点，因此每次查找、插入或删除的时间与存储在树中的项的数量的对数成比例。这比在（未排序的）数组中按键查找项所需的线性时间要好得多，但比哈希表的相应操作要慢。
一个大小为9、深度为3的二叉搜索树，根节点为8。 未绘制叶子节点。
二叉搜索树
1）基本操作的伪代码
插入
insert(value) 前置条件：value已通过自定义类型检查，类型为T 后置条件：value已放置在树的正确位置 如果 root = ø root ← 节点(value) 否则 insertNode(root, value) 结束如果 结束插入 insertNode(current, value) 前置条件：current为起始节点 后置条件：value已放置在树的正确位置 如果 value < current.value 如果 current.left = ø current.left ← 节点(value) 否则 InsertNode(current.left, value) 结束如果 否则 如果 current.right = ø current.right ← 节点(value) 否则 InsertNode(current.right, value) 结束如果
1）基本操作的伪代码
插入
insert(value) 前置条件：value已通过自定义类型检查，类型为T 后置条件：value已放置在树的正确位置 如果 root = ø root ← 节点(value) 否则 insertNode(root, value) 结束如果 结束插入
insertNode(current, value) 前置条件：current为起始节点 后置条件：value已放置在树的正确位置 如果 value < current.value 如果 current.left = ø current.left ← 节点(value) 否则 InsertNode(current.left, value) 结束如果 否则 如果 current.right = ø current.right ← 节点(value) 否则 InsertNode(current.right, value) 结束如果 结束如果 结束insertNode
查找
contains(root, value) 前置条件：root为树的根节点，value为要查找的值 后置条件：确定value是否被找到 如果 root = ø 返回 false 结束如果 如果 root.value = value 返回 true 否则，如果 value < root.value 返回 contains(root.left, value) 否则 返回 contains(root.right, value) 结束如果 结束contains
带你读《图解算法小抄》十二、树（2）https://developer.aliyun.com/article/1348186?groupCode=tech_library
