目录
- 二叉搜索树概念
- 二叉搜索树的接口设计，包括增，删，改，查
- 平衡二叉搜索树
一 二叉搜索树
二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，英文简称为 BST
- 又被称为:二叉查找树、二叉排序树
- 任意一个节点的值都大于其左子树所有节点的值
- 任意一个节点的值都小于其右子树所有节点的值
- 它的左右子树也是一棵二叉搜索树
二叉搜索树可以大大提高搜索数据的效率
二叉搜索树存储的元素必须具备可比较性
- 比如 int、double 等
- 如果是自定义类型，需要指定比较方式
- 不允许为 null
二叉搜索树.png
二 二叉搜索树的接口设计
/**
* 清除所有元素
*/
- (void)clear;
/**
* 是否包含某个元素
* @param element
* @return bool
*/
- (bool)contains:(id)element;
/**
* 添加元素到尾部
* @param element
*/
- (void)add:(id)element;
/**
* 删除元素
* @param element
*/
- (void)remove:(id)element;
2.1 添加节点
添加步骤
1.找到父节点 parent
2.创建新节点 node
3.parent.left = node 或者 parent.right = node
遇到值相等的元素如何处理？ 覆盖旧的值
- 代码实现
- (void)add:(id)element {
[self elementNotNullCheck:element];
// 添加第一个节点
if (_root == nil) {
_root = [[TreeNode alloc] initWithElement:element parent:nil];
_size++;
return;
}
// 添加的不是第一个节点
// 找到父节点
TreeNode *parent = _root;
TreeNode *node = _root;
int cmp = 0;
while (node != nil) {
cmp = [self compare:element element2:node.element];
parent = node;
if (cmp > 0) { // 右节点
node = node.right;
} else if (cmp < 0) { // 左节点
node = node.left;
} else { // 相对 - 覆盖
node.element = element;
return;
}
}
// 查看插入到父节点的哪个位置
TreeNode *newNode = [[TreeNode alloc] initWithElement:element parent:parent];
if (cmp > 0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
_size++;
}
- 测试代码
// 打印一棵二叉树
- (void)test1 {
NSArray *data = @[@7, @4, @9, @2, @5, @8, @11, @3, @12, @1];
BST *tree = [[BST alloc] init];
for (int i = 0; i < data.count; i++) {
[tree add:data[i]];
}
NSLog(@"tree = %@",tree);
}
-
运行结果
添加节点.png
2.2 根据元素内容获取节点
- 核心代码如下
- (TreeNode *)node:(id)element {
TreeNode *node = _root;
int cmp = 0;
while (node != nil) {
cmp = [self compare:element element2:node.element];
if (cmp == 0) { // 当前节点
return node;
} else if (cmp > 0) { // 右子树
node = node.right;
} else { // 左子树
node = node.left;
}
}
return nil;
}
2.3 删除节点
接下来我们分为三种情况分别处理，即 叶子节点，度为1的节点，度为2的节点
2.3.1 删除节点 - 叶子节点
直接删除
- 为左子树节点
node == node.parent.left，则node.parent.left = nil - 为右子树节点
node == node.parent.right，则node.parent.right = nil - 为根节点
node.parent == nil，则root = nil
删除叶子节点.png
2.3.2 删除节点 - 度为1的节点
用子节点代替原节点的位置
其中 child是node.left或者child是node.right
用child替代node的位置
- 如果node是
左子节点
child.parent = node.parent
node.parent.left = child
- 如果node是
右子节点
child.parent = node.parent
node.parent.right = child
- 如果node是根节点
root = child
child.parent = nil
删除度为1的节点.png
2.3.3 删除节点 - 度为2的节点
如下图所示：先删除5，再删除4
- 先用
前驱或者后继节点的值覆盖原节点的值 - 然后
删除相应的前驱或者后继节点
如果一个节点的度为2，那么它的
前驱，后继节点的度只可能是1或者0
删除度为2的节点.png
- 代码实现如下
/// 删除节点 node
- (void)removeNode:(TreeNode *)node {
if (node == nil) {
return;
}
self.size--;
if (node.hasTwoChildren) { // 度为2的节点
// 找到后继节点
TreeNode *s = [self successor:node];
// 用后继节点的值覆盖度为2的节点的值
node.element = s.element;
// 删除后继节点
node = s;
}
// 删除node节点(node的度必然是1或者0)
TreeNode *replacement = node.left != nil ? node.left : node.right;
if (replacement != nil) { // 1.node是度为1的节点
// 更改parent
replacement.parent = node.parent;
// 更改parent的left,right的指向
if (node.parent == nil) { // node是度为1的节点并且是根节点
self.root = replacement;
} else if (node == node.parent.left) { // 左子节点
node.parent.left = replacement;
} else { // node == node.parent.right
node.parent.right = replacement;
}
} else if (node.parent == nil) { // 2.node是叶子节点并且是根节点
self.root = nil;
} else { // 3.node是叶子节点,但不是根节点
if (node == node.parent.left) {
node.parent.left = nil;
} else { // node == node.parent.right
node.parent.right = nil;
}
}
}
- 测试代码
// 删节点
- (void)removeNode {
NSArray *data = @[@7, @4, @9, @2, @5, @8, @11, @3, @12, @1];
BST *tree = [[BST alloc] init];
for (int i = 0; i < data.count; i++) {
[tree add:data[i]];
}
NSLog(@"tree = %@",tree);
[tree remove:@7];
NSLog(@"tree = %@",tree);
}
-
运行结果
image.png
三 平衡二叉搜索树
3.1 二叉搜索树的复杂度分析
- 如果是按照 7、4、9、2、5、8、11 的顺序添加节点
image.png
复杂度：O(h) == O(logn)
- 如果是从小到大添加节点 2，4，5，7，8，9，11
image.png
复杂度：O(h) == O(h)
- 当 n 比较大时，两者的性能差异比较大
- 比如 n = 1000000 时，二叉搜索树的最低高度是 20
3.2 退化成链表的另一种情况
删除节点时也可能会导致二叉搜索树退化成链表
7
4 9
2 5 8 11
- 添加、删除节点时，都可能会导致二叉搜索树退化成链表
- 有没有办法防止二叉搜索树退化成链表? 让添加、删除、搜索的复杂度维持在 O(logn)
3.3 平衡（Balance）
平衡:当节点数量固定时，左右子树的高度越接近，这棵二叉树就越平衡(高度越低)
image.png
3.4 理想平衡
最理想的平衡，就是像完全二叉树、满二叉树那样，高度是最小的
image.png
3.5 如何改进二叉搜索树
首先，节点的添加、删除顺序是无法限制的，可以认为是随机的
- 所以，改进方案是:在节点的添加、删除操作之后，想办法让二叉搜索树恢复平衡(减小树的高度)
- 如果接着继续调整节点的位置，完全可以达到理想平衡，但是付出的代价可能会比较大
- 比如调整的次数会比较多，反而增加了时间复杂度
总结来说，比较合理的改进方案是:用尽量少的调整次数达到适度平衡即可
- 一棵达到适度平衡的二叉搜索树，可以称之为:平衡二叉搜索树
3.6 平衡二叉搜索树（Balanced Binary）
英文简称为:BBST
经典常见的平衡二叉搜索树有
AVL树
- Windows NT 内核中广泛使用
红黑树
- C++ STL(比如 map、set )
- Java 的 TreeMap、TreeSet、HashMap、HashSet
- Linux 的进程调度
- Ngix 的 timer 管理
一般也称它们为:自平衡的二叉搜索树(Self-balancing Binary Search Tree)
本文会持续更新中，更多精彩内容敬请期待。
本文参考 MJ老师的 恋上数据结构与算法
本人技术水平有限，如有错误欢迎指正。
书写整理不易，您的打赏点赞是对我最大的支持和鼓励，欢迎点赞打赏。
