数据结构之二叉搜索树
2018-12-12 本文已影响27人
人魔七七
基本概念
- 二叉搜索树是由二叉树组成的，专门用于搜索和查找为目的的一种树。
- 当前结点比其左子树的其他结点都大，相反当前结点比其右子树的其他结点都小。
- 这个二叉搜索树和我们之前构建堆的思路很相似，参考这个链接。
基本的操作
- 插入操作，通常这也是构建的方法。
- 删除操作，删除操作分几种情况。
- 删除的结点有左右孩子
- 删除的结点没有左右孩子
- 删除的结点有一个左孩子
- 删除的结点有一个右孩子
- 查找操作，这也是经常用的操作，删除也依赖这个操作。
插入操作
思路
- 如果要插入的结点比根结点小，则往左边调整，继续比较。相反如果要插入的结点比根结点大，则往右边调整。
- 循环的按照上述步骤走。
- 直到走到要对比的结点不存在右孩子或者左孩子跳出循环。
- 插入结束。
动画
代码
- (void)insertObject:(NSObject *)newObj
{
//创建一个结点根据newObject
DSTreeNode *treeNode = [[DSTreeNode alloc] init];
treeNode.object = newObj;
treeNode.compareSelector = self.root.compareSelector;
//currentNode 和 parentNode指向根结点
DSTreeNode *currentNode = self.root;
DSTreeNode *parentNode = self.root;
while (YES) {
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Warc-performSelector-leaks"
//比较当前结点和新插入结点大小
NSComparisonResult result = (NSComparisonResult)[newObj performSelector : currentNode.compareSelector withObject : currentNode.object];
#pragma clang diagnostic pop
//如果新结点比current指针指向的结点大
if (result >= 0) {
//且当前结点不存在右结点则插入 两个结点指针调整互指 然后结束循环
if (!currentNode.rightChild) {
currentNode.rightChild = treeNode;
treeNode.parent = parentNode;
break;
}
//否则向下移动current 和 parentNode指针继续循环执行上面的操作
else {
currentNode = currentNode.rightChild;
parentNode = currentNode;
}
}
//和上面的思路类似
else {
if (!currentNode.leftChild) {
currentNode.leftChild = treeNode;
treeNode.parent = parentNode;
break;
}
else {
currentNode = currentNode.leftChild;
parentNode = currentNode;
}
}
}
}
查找操作
思路
- 从树的最顶端开始查找
- 如果查找的结点值小于当前位置结点向左走，反之向右走。
- 既不大于也不小于也就是结束，找到这个结点了。
动画
代码
//查找方法
- (DSTreeNode *)find:(NSObject *)obj
{
//当前指针指向根结点
DSTreeNode *currentNode = self.root;
while (YES) {
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Warc-performSelector-leaks"
//比较当前结点和查找结点
NSComparisonResult result = (NSComparisonResult)[obj performSelector : currentNode.compareSelector withObject : currentNode.object];
#pragma clang diagnostic pop
//如果查找结点值大于根结点说明在右子树上
if (result > 0) {
//当前结点存在右结点 指针下移动
if (currentNode.rightChild) {
currentNode = currentNode.rightChild;
}
else
return nil;
}
//这个查找左边子树的思路和上面一样
else if (result < 0) {
if (currentNode.leftChild) {
currentNode = currentNode.leftChild;
}
else
return nil;
}
else {
break;
}
}
return currentNode;
}
删除操作
思路
- 上面已经说分几种情况了，这里说一种最复杂的情况就是这个被删除结点存在左右孩子，其他的也就好理解了，看代码注释。
- 删除这个结点。
- 找到被删除结点右子树中最小的结点替换被删除的结点，或者左子树中最大的结点替换被删除的结点。
动画
代码
//删除某个结点
- (DSTreeNode *)deleteObject:(NSObject *)obj
{
//找到当前结点
DSTreeNode *node = [self find:obj];
if (node) {
//如果被删除的结点存在左右孩子
if (node.leftChild && node.rightChild) {
//找到后继结点也就是右子树的最小结点
// DSTreeNode *tmpCell = node.rightChild;
// while (tmpCell.leftChild) {
// tmpCell = tmpCell.leftChild;
// }
//找到后继结点也就是左子树的最大结点
DSTreeNode *tmpCell = node.leftChild;
while (tmpCell.rightChild) {
tmpCell = tmpCell.rightChild;
}
//交换这两个结点指针
NSObject *temp;
temp = [node.object copy];
node.object = [tmpCell.object copy];
tmpCell.object = temp;
//删除这个被替换掉的结点
if ([tmpCell isLeftChildOfParent]) {
tmpCell.parent.leftChild = nil;
}
else {
tmpCell.parent.rightChild = nil;
}
}
//如果不存在左右孩子 又分几种情况没有左右孩子，有一个左孩子，有一个右孩子
else {
if (node.leftChild != nil) {
node = node.leftChild;
}
else if (node.rightChild != nil) {
node = node.rightChild;
}
if ([node isLeftChildOfParent]) {
node.parent.leftChild = nil;
}
else {
node.parent.rightChild = nil;
}
}
}
return node;
}
总结
-
其实这些操作过程时间复杂度主要在对比查找的过程。
-
最坏的情况下，只需要查找一个分支上的数据即可，不需要检索每个数据。因此复杂度是O（lgn）,这样的情况下树是相对平衡的。
-
如果这个数只有一个单独的右分支的情况下查找结点的复杂度就是O（n）了，其实就是从头到尾检索所有的结点。
没有对比没有伤害
看下图这个情况，这样的查找效率最低
理想的状态
下回预告
综上所述保持二叉搜索树处于平衡状态很重要，这样我们能提高查找的效率。让其平衡有一种方法就是将二叉搜索树实现为AVL树。
参考链接
https://www.jianshu.com/p/f35e700748e9
https://www.bysocket.com/?p=1209
https://github.com/raywenderlich/swift-algorithm-club/tree/master/Binary%20Search%20Tree
https://github.com/EvgenyKarkan/EKAlgorithms/tree/master/EKAlgorithms/Data%20Structures/BinarySearchTree
书籍
算法精解
算法动画图解
