二叉搜索树（Binary Search Tree）

  • 左子树上所有节点的值都小于根节点的值。
  • 右子树上所有节点的值都大于根节点的值。
  • 左右子树也都是二叉搜索树。

二叉搜索树的遍历

  • 中序遍历：左子树 -> 根节点 -> 右子树。对于二叉搜索树来说，中序遍历的结果是一个有序递增的序列。

平衡二叉搜索树

  • 对于树中的每个节点，其左子树和右子树的高度差不超过1。
  • 此时树的高度为 O(log n)，可以保证基本的搜索、插入和删除操作的时间复杂度为 O(log n)。