排序二叉树

二叉查找树-二叉搜索树-BST-二叉排序树-排序二叉树

1. 梗概:

1. 一种特殊的二叉树, 规定每个子树的节点数据都遵循:
   1. 左孩子<根(双亲)<右孩子
2. 拥有相同结点的排序二叉树, 有多种形态
   1. 根据插入顺序的不同, 形态各不相同

特殊的二叉排序树

child::平衡排序二叉树

2. 排序二叉树与折半查找的区别:

2.1. 排序二叉树特点:

1. 不同的插入顺序, 形成的排序二叉树往往不同, 甚至可能形成单支树, 平均性能非常差
2. 看上去根好像是中位数, 但实际上因为左右子树规模不同, 根往往偏离中位数很远

2.2. 折半查找特点:

1. 每次取的关键字都非常接近与中位数, 平均性能良好
2. 不同的插入顺序, 所形成的记录表都一样

2.3. 相同点:

1. 两者平均性能相似

3. 操作:

1. 插入
   1. 时间复杂度: O(logn)
2. 查找
3. 删除
   1. 时间复杂度: O(logn)

4. 在c语言中的实现

4.1. 定义:

typedef struct BSTNode{
	KeyType key;
	struct BSTNode *LChild, *RChlid;
}BSTNode,*BSTree;

4.2. 查找结点

BSTNode* SearchBST(BSTree tree, KeyType key){
    BSTree q;
    q= tree;
    for(;q;){
        if(q->key==key)return q;
        if(q->key>key)q=q->LChild;
        else q=q->RChild;
    }
    return NULL;
}

4.3. 插入结点

梗概:

1. 参数需要根结点指针的地址
   1. 当连树都不存在时候
      1. 就在该地址放上一个根结点
2. 找到将插入位置的双亲结点
   1. 在该双亲的对应孩子结点地址放上新的结点 代码:

void InsertBST(BSTree *tree, KeyType key){
	BSTNode *parent=NULL,*p;
	for(p=*tree;p;){
		parent = p;
		if(key>p->key) p=p->RChild;
		else p=p->LChild;
	}
	BSTNode* s=(BSTNode*)calloc(1,sizeof(BSTNode));
	s->key=key; s->LChild=s->RChild=NULL;
	if(!parent)*tree=s;
	else if(parent->LChild==p)
		parent->LChild=s;
	else parent->RChild=s;
}

4.4. 创建二叉排序树

void CreateBST(BSTree tree){
    KeyType key;
    tree=NULL;
    scanf("%d",&key);
    for(;key!=-1;){
        InsertBST(tree,key);
        scanf("%d",&key);
    }
}

4.5. 删除结点

梗概:

1. 按复杂程度分两种大情况:
   1. 目标只有左子树或右子树
   2. 目标两个子树都有
2. 目标只有左子树或右子树
   1. 则把子树接上目标双亲结点, 再删掉目标结点即可
3. 两个子树都有
   1. 还需要额外找出两个结点, 分别是直接前驱(数值上的), 前驱的双亲
      1. 直接前驱在左子树的最右结点
   2. 把直接前驱拿过来, 顶上目标结点
      1. 相当于也删除该结点, 但该节点必定没有右子树
         1. 所以直接把前驱的左子树接上前驱的双亲即可
   3. 实际上只要释放掉前驱节点即可 代码:

BSTree DelBST(BSTree tree, KeyType key){
	BSTNode *tar, *par_tar, *front, *par_front;
	tar=tree; par_tar=NULL;
	/*查找目标并记录其双亲*/
	for(;tar;){
		if(tar->key==key) break;
		par_tar=tar;
		if(tar->key>key)tar=tar->LChild;
		else tar=tar->RChild;
	}
	if(tar==NULL) return tree;
	/*先判断右子树是否独立*/
	if(tar->LChild==NULL){
		/*把目标的右子树直接接上*/
		if(par_tar==NULL) tree=tar->RChild;
		else if(par_tar->LChild==tar)par_tar->LChild=tar->RChild;
		else par_tar->RChild=tar->RChild;
		free(tar);
	}
	/*处理左子树*/
	else{
		par_front=tar;
		/*找左子树的最右结点,并记录其双亲*/
		front=tar->LChild;
		for(;front->RChild;){
			par_front=front; front=front->RChild;
		}
		if(par_front==tar) par_front->LChild=front->LChild;
		/*先用更前驱顶上前驱*/
		else par_front->RChild=front->LChild;
		/*前驱顶上目标*/
		tar->key=front->key;
		free(front);
	}
	return tree;
}

5. 在ts/js中的实现:

5.1. 定义:

type keytype = number;
class BSTNode{
    constructor(key:keytype,LChild?:BSTNode,RChild?:BSTNode){
        this.key=key;
        this.LChild=LChild?LChild:null;
        this.RChild=RChild?RChild:null;
    }
    key:keytype;
    LChild:BSTNode|null;
    RChild:BSTNode|null;
}

5.2. 插入/创建/查找:

class BSTree{
    constructor(){
        this.root=null;
    }
    root:BSTNode|null;
    SearchBST(key:keytype){
        let q = this.root;
        for(;q;){
            console.log(q.key);
            if(q.key==key)return q;
            else if(q.key<key)q=q.RChild;
            else q=q.LChild;
        }
        return null;
    }
    InsertBST(key:keytype){
        if(this.root==null){
            this.root=new BSTNode(key);
            return;
        }
        let parent:BSTNode|null = this.root;
        let q:BSTNode|null = this.root;
        for(;q;){
            parent=q;
            if(q.key<key)
                q=q.RChild;
            else q=q.LChild;
        }
        let NewNode = new BSTNode(key);
        if(parent.key<key)parent.RChild=NewNode;
        else parent.LChild=NewNode;
    }
    CreatBST(keys:keytype[]){
        for(let i=0;i<keys.length;++i){
            this.InsertBST(keys[i]);
        }
    }
}