平衡二叉树和折半查找

平衡二叉树是一种特殊的二叉搜索树，它的左右子树的高度差不超过1，从而保证了树的高度始终保持在O(log n)级别，避免了二叉搜索树退化成链表的情况。平衡二叉树的常见实现有红黑树、AVL树、B树等。

折半查找（Binary Search）是一种在有序数组中查找目标元素的算法。它的基本思想是每次将待查找区间折半，缩小查找范围，直到找到目标元素或者确定目标元素不存在为止。折半查找的时间复杂度为O(log n)。