精华内容
下载资源
问答
  • 平衡二叉排序树

    2021-04-26 11:44:36
    平衡二叉排序树 平衡二叉排序树是在插入函数中处理 当传入的T的第一层为NULL,即为整颗树为空时,对该结点进行插入操作,并修改taller变量为TRUE,最后该函数结束返回一个TRUE;表示插入成功 或者当传入的T的第一层...

    平衡二叉排序树

    平衡二叉排序树是在插入函数中处理

    /* 若在平衡的二叉排序树T中不存在和e有相同关键字的结点,则插入一个 */
    /* 数据元素为e的新结点并返回1,否则返回0.若因插入而使二叉排序树 */
    /* 失去平衡,则作平衡旋转处理,布尔变量taller反映T长高与否 */
    Status InsertAVL(BiTree* T, int e, Status *taller)
    {
    	if (!*T) 
    	{/* 插入新结点,树"长高",置taller为TRUE */
    		*T = (BiTree)malloc(sizeof(BiTNode));
    		(*T)->data = e;
    		(*T)->lchild = (*T)->rchild = NULL;
    		(*T)->bf = EH;
    		*taller = TRUE;
    	}
    	else
    	{
    		if (e == (*T)->data)
    		{	/* 树中已存在和e有相同关键字的结点则不再插入 */
    			*taller = FALSE;
    			return FALSE;
    		}
    		if (e < (*T)->data)
    		{/* 应继续在T的左子树中进行搜索 */
    			if (!InsertAVL(&(*T)->lchild, e, taller)) /* 未插入 */
    				return FALSE;
    			if (*taller) /* 已插入到T的左子树中且左子树"长高" */
    			{
    				switch ((*T)->bf) /* 检查T的平衡度 */
    				{
    					case LH: /* 原本左子树比右子树高,需要作左平衡处理 */
    						LeftBalance(T);
    						*taller = FALSE;
    						break;
    					case EH: /* 原本左右子树等高,现在因左子树增高而树增高 */
    						(*T)->bf = LH;
    						*taller = TRUE;
    						break;
    					case RH:/* 原本右子树比左子树高,现在左、右子树等高 */
    						(*T)->bf = EH;
    						*taller = FALSE;
    						break;
    				}
    			}
    		}
    		else
    		{/* 应继续在T的右子树中进行搜索 */
    			if (!InsertAVL(&(*T)->rchild, e, taller)) /* 未插入 */
    				return FALSE;
    			if (*taller) /* 已插入到T的左子树中且左子树"长高" */
    			{
    				switch ((*T)->bf) /* 检查T的平衡度 */
    				{
    				case LH: /* 原本左子树比右子树高,现在左、右子树等高 */
    					(*T)->bf = EH;
    					*taller = FALSE;
    					break;
    				case EH:	/* 原本左右子树等高,现在因右子树增高而树增高 */
    					(*T)->bf = LH;
    					*taller = TRUE;
    					break;
    				case RH:/* 原本右子树比左子树高,需要作右平衡(左旋转)处理 */
    					RightBalance(T);
    					*taller = FALSE;
    					break;
    				}
    			}
    		}
    	}
    	return TRUE;
    }
    
    当传入的T的第一层为NULL,即为整颗树为空时,对该结点进行插入操作,并修改taller变量为TRUE,最后该函数结束返回一个TRUE;表示插入成功
    
    或者当传入的T的第一层为不为NULL,即为整颗树不为空时,
    则有三种情况:
    

    1、当要插入的结点的data值e等于T的data值时;
    taller值为FALSE,返回一个FALSE值,表示插入失败。

    2、当要插入的结点的data值e小于T的data值时;
    递归调用该函数,并传入T的左子树,e,taller;
    当递归的返回值为FALSE时;
    即插入失败,此时需要继续返回FASLE,表示插入失败,直到递归结束。

    或者当递归的返回值为TRUE时,即插入成功时;
    继续往下执行,第一次执行时,是插入结点的上一级;因为当插入成功后taller值为TRUE,即树增高,需要做相应处理;
    此时分三种情况:
    
     第一,当当前结点的bf值为1,即原本左子树比右子树高,又因为插入结点插入在当前结点的左子树,此时需要做左平衡处理,调用左平衡处理函数并将taller值修改为FALSE,因为左平衡处理后树就平衡了,即不需要再处理了,所以taller为FALSE。
     
     第二,当当前结点的bf值为0,即原本左子树和右子树等高,又因为插入结点插入在当前结点的左子树,此时需要将T的bf值修改为1,因为插入结点后因左子树增高而树增高;taller值为TRUE,即上一层还需要继续处理。
    
    第三,当当前结点的bf值为-1,即原本右子树比左子树高,又因为插入结点插入在当前结点的左子树,此时需要将T的bf值修改为0,因为插入结点后因左右子树登高;taller值为FALSE,即其它层不需要处理;因为只是在原本的基础上再加一个左子树,所以对其它层没有影响。
    

    3、当要插入的结点的data值e大于T的data值时;
    递归调用该函数,并传入T的左子树,e,taller;
    当递归的返回值为FALSE时;
    即插入失败,此时需要继续返回FASLE,表示插入失败,直到递归结束。

    或者当递归的返回值为TRUE时,即插入成功时;
    继续往下执行,第一次执行时,是插入结点的上一级;因为当插入成功后taller值为TRUE,即树增高,需要做相应处理;
    此时分三种情况:
    
     第一,当当前结点的bf值为1,即原本左子树比右子树高,又因为插入结点插入在当前结点的右子树,此时需要将T的bf值修改为0,因为插入结点后因左右子树登高;taller值为FALSE,即其它层不需要处理;因为只是在原本的基础上再加一个右子树,所以对其它层没有影响。
     
     第二,当当前结点的bf值为0,即原本左子树和右子树等高,又因为插入结点插入在当前结点的右子树,此时需要将T的bf值修改为-1,因为插入结点后因右子树增高而树增高;taller值为TRUE,即上一层还需要继续处理。
    
    第三,当当前结点的bf值为-1,即原本右子树比左子树高,又因为插入结点插入在当前结点的右子树,此时需要做右平衡处理,调用右平衡处理函数并将taller值修改为FALSE,因为右平衡处理后树就平衡了,即不需要再处理了,所以taller为FALSE。
    

    左平衡函数:

    /*对以指针T所指结点为根的二叉树作左平衡旋转处理*/
    /*本算法结束时,指针T指向新的根节点*/
    void LeftBalance(BiTree* T) 
    {
    	BiTree L, Lr;
    	L = (*T)->lchild; /*L指向T的左子树根节点*/
    	switch (L->bf)
    	{/* 检查T的左子树的平衡度,并作相应平衡处理 */
    		case LH: /* 新结点插入在T的左孩子的左子树上,要作单右旋处理 */
    			(*T)->bf = L->bf = EH; 
    			R_Rotate(T);
    			break;
    		case RH: /* 新结点插入在T的左孩子的右子树上,要作双旋处理 */
    			Lr = L->rchild; /* Lr指向T的左孩子的右子树根 */
    			switch (Lr->bf) /* 修改T及其左孩子的平衡因子 */
    			{
    				case LH:
    					(*T)->bf = RH;
    					L->bf = EH;
    					break;
    				case EH:
    					(*T)->bf = L->bf = EH;
    					 
    					break;
    				case RH:
    					(*T)->bf = EH;
    					L->bf = LH;
    					break;
    			}
    			Lr->bf = EH;
    			L_Rotate(&(*T)->lchild);/* 对T的左子树作左旋平衡处理 */
    			R_Rotate(T); /* 对T作右旋平衡处理 */
    			break;
    	}
    
    
    }
    
    当需要左平衡的时候,该T的bf值为1;
    L为T的左子树,因为需要做左平衡处理时,该树的层序至少为3;
    L的bf值不可能为0;即L的左右子树的深度差为1;
    

    当L的bf值为1时,即新插入结点在L的左子树上或为L的左子树;

    	此时满足右旋转的条件;直接将T和L的bf值都修改为0,再调用右旋转函数将T作为参数传入。
    

    当L的bf值为-1时,即插入结点在L的右子树上或为L的右子树;

    	此时不满足右旋转条件,需要将L进行左旋转再将T右旋转且将Lr的bf值修改为0,因为Lr最后会成为根节点,T指向Lr;并将T和L的bf值进行相应的修改。
    	Lr为L的右子树,
    	
    	当Lr的bf值为1时,说明新插入结点为Lr的左子树,
    	此时需要将T的bf值改为-1,L的bf值为0;
    	在双旋转后,因为是左平衡,所以新插入结点N的data值<T的data值;又因为N为Lr的左子树,所以N的data值<Lr的data值;即N<T且N<Lr;所以T的左子树为空值,所以T的bf值为-1
    	因为Lr为L的右子树,Lr的所有结点都比L大,所以N的data值>L的data值,又因为N为Lr的左子树,所以N的data值<Lr的data值,即L<N<Lr,所以L的右子树为新结点N,所以L的bf值为0;
    	
    	当Lr的bf值为0时,说明新插入结点为L的右子树,即Lr为新结点,Lr的左右子树为空;
    	在双旋转后,因为Lr不存在左右结点,所以T和L的bf值都为0;
    
    	当Lr的bf值为-1时,说明新插入结点为Lr的右子树,
    	此时需要将T的bf值改为0,L的bf值为1;
    	在双旋转后,因为是左平衡,所以新插入结点N的data值<T的data值;又因为N为Lr的右子树,所以N的data值>Lr的data值;即Lr<N<T;所以T的左子树为新结点N,所以T的bf值为0
    	因为Lr为L的右子树,Lr的所有结点都比L大,所以N的data值>L的data值,又因为N为Lr的右子树,所以N的data值>Lr的data值,即L<N且Lr<N,所以L的右子树为空,所以L的bf值为1;
    

    右平衡函数:

    /*对以指针T所指结点为根的二叉树作左平衡旋转处理*/
    /*本算法结束时,指针T指向新的根节点*/
    void RightBalance(BiTree* T)
    {
    	BiTree R, Rl;
    	R = (*T)->rchild; /*L指向T的右子树根节点*/
    	switch (R->bf)
    	{/* 检查T的右子树的平衡度,并作相应平衡处理 */
    		case LH: /* 新结点插入在T的右孩子的左子树上,要作双旋处理 */
    		
    			Rl = R->lchild; /* Lr指向T的右孩子的左子树根 */
    			switch (Rl->bf) /* 修改T及其右孩子的平衡因子 */
    			{
    				case LH:
    					(*T)->bf = EH;
    					R->bf = RH;
    					break;
    				case EH:
    					(*T)->bf = R->bf = EH;
    
    					break;
    				case RH:
    					(*T)->bf = LH;
    					R->bf = EH;
    					break;
    			}
    			Rl->bf = EH;
    			R_Rotate(&(*T)->rchild);/* 对T的右子树作右旋平衡处理 */
    			L_Rotate(T); /* 对T作左旋平衡处理 */
    			break;
    	
    
    		case RH: /* 新结点插入在T的右孩子的右子树上,要作单左旋处理 */
    			(*T)->bf = R->bf = EH;
    			L_Rotate(T);
    			break;
    	}
    }
    
    当需要右平衡的时候,该T的bf值为-1;
    R为T的右子树,因为需要做右平衡处理时,该树的层序至少为3;
    R的bf值不可能为0;即R的左右子树的深度差为1;
    

    当R的bf值为1时,即新插入结点在R的左子树上或为R的左子树;

    		此时不满足左旋转条件,需要将R进行右旋转再将T左旋转且将Rl的bf值修改为0,因为Rl最后会成为根节点,T指向Rl;并将T和R的bf值进行相应的修改。
    	Rl为R的左子树,
    	
    	当Rl的bf值为1时,说明新插入结点为Rl的左子树,
    	此时需要将T的bf值改为0,R的bf值为-1;
    	在双旋转后,因为是右平衡,所以新插入结点N的data值>T的data值;又因为N为Rl的左子树,所以N的data值<Rl的data值;即T<N<Rl;所以T的右子树为新结点N,所以T的bf值为0
    	因为Rl为R的左子树,Rl的所有结点都比L小,所以N的data值<R的data值,又因为N为Rl的左子树,所以N的data值<Lr的data值,即N<Rl且N<R,所以R的左子树为空,所以R的bf值为-1;
    	
    	当Rl的bf值为0时,说明新插入结点为R的左子树,即Rl为新结点,Rl的左右子树为空;
    	在双旋转后,因为Rl不存在左右结点,所以T和R的bf值都为0;
    
    	当Rl的bf值为-1时,说明新插入结点为Rl的右子树,
    	此时需要将T的bf值改为1,L的bf值为0;
    	在双旋转后,因为是右平衡,所以新插入结点N的data值>T的data值;又因为N为Rl的右子树,所以N的data值>Rl的data值;即Rl<N且T<N;所以T的右子树为空,所以T的bf值为1
    	因为Rl为R的左子树,Rl的所有结点都比R小,所以N的data值<R的data值,又因为N为Rl的右子树,所以N的data值>Rl的data值,即Rl<N<R,所以R的左子树为新结点N,所以R的bf值为0;	
    

    当R的bf值为-1时,即插入结点在R的右子树上或为R的右子树;
    此时满足左旋转的条件;直接将T和R的bf值都修改为0,再调用左旋转函数将T作为参数传入。

    左旋转函数:

    void L_Rotate(BiTree *p)
    {
    	BiTree R;
    	R = (*p)->rchild; /*L指向p的右子树根结点*/
    	(*p)->rchild = R->lchild;/*将p的右子树指向 p的左子树的右子树*/
    	R->lchild = (*p);/*p的右子树的右子树指向P*/
    	(*p) = R; /*p指向R*/
    }
    

    将T的左子树L的右子树置为T的左子树,将T置为L的右子树,T指向L,表示L为根结点;
    若L的右子树不存在则T不存在左子树;直接将T置为L的右子树;

    右旋转函数:

    void R_Rotate(BiTree *p) 
    {
    	BiTree L;
    	L = (*p)->lchild; /*L指向p的左子树根节点*/
    	(*p)->lchild = L->rchild;/*将p的左子树指向 p的左子树的右子树*/
    	L->rchild = (*p);/*p的左子树的右子树指向P*/
    	(*p) = L; /*p指向L*/
    }
    

    将T的右子树R的左子树置为T的右子树,将T置为R的左子树,T指向R,表示R为根结点;
    若R的左子树不存在则T不存在右子树;直接将T置为R的左子树;

    在插入时,左平衡调用的是单右旋转,或者是双旋,左旋转后右旋转;
    右平衡是单左旋转,或者是双旋。又旋后左旋``

    展开全文
  • 文章目录二叉排序树1.... 平衡二叉排序树 二叉排序树 1. 二叉排序树 二叉排序树的检索 def bt_search(btree, key): bt = btree: while bt: if key < bt.val: bt = bt.left elif key > bt.val: ...

    二叉排序树

    1. 二叉排序树

    二叉排序树的检索

    def bt_search(btree, key):
        bt = btree:
        while bt:
            if key < bt.val:
                bt = bt.left
            elif key > bt.val:
                bt = bt.right
            else:
                return bt.val
        
        return None
    

    二叉排序树数据插入
    思路:

    • 若树为空,直接新建结点
    • 若树不为空:
      • 应该向左走而左结点为空,插入;
      • 应该向右走而右结点为空,插入;
      • 覆盖原有结点
    def bt_insert(btree, key):
        if btree is None:
            return TreeNode(key)
        bt = btree
        while True:
            if key < bt.val:
                if bt.letf is None:
                    bt.left = TreeNode(key)
                    return btree
                bt = bt.left
            elif key > bt.val:
                if bt.right is None:
                    bt.right = Tree.Node(key)
                    return btree
                bt = bt.right
            else:
                bt.val = key
                return btree
    

    二叉排序树数据删除
    思路:

    • 找到待删除数值和它的父节点在树中的位置
    • 若子结点的左子树为空,则直接将子节点的右子树挂到父节点,此处有3种情况
      • 父节点为空(子节点为根节点),则直接将根节点设为子节点的右子树
      • 子节点是父节点的左结点,则将子节点的右子树挂到父节点的左结点
      • 子节点是父节点的右结点,则将子节点的右子树挂到父节点的右结点
    • 若子节点的左子树不为空,先找到左子树的最右结点,并将子节点的右子树挂到最右结点的右结点上,后续同样有三种情况
      • 父节点为空(子节点为根节点),则直接将根节点设为子节点的左子树
      • 子节点是父节点的左结点,则将子节点的左子树挂到父节点的左结点
      • 子节点是父节点的右结点,则将子节点的左子树挂到父节点的右结点

    def delete(btree, key):
        bt = btree
        father, child = None, btree
        while child and child.val != key:
            father = child
            if key < child.val:
                child = child.left
            elif key > child.val:
                child = child.right
        if child is None:
            return 
        
        # 子节点左子树为空
        if child.left is None:
            if father is None:
                btree = child.right
            elif child is father.left:
                father.left = child.right
            else:
                father.right = child.right
            return btree
    
        # 子节点左子树不为空
        most_right = child.left
        while most_right.right:
            most_right = most_right.right
        
        most_right.right = child.right
        if father is None:
            btree = child.left
        elif child is father.left:
            father.left = child.left
        else:
            father.right = child.left
        return btree
    

    2. 平衡二叉排序树

    记结点左子树和右子树的高度差为平衡因子(Balance Factor),平衡因子的取值为-1,0,1.

    • 如果数据插入位置到根节点途径上每一个结点的BF都为0,那么新插入的结点不会影响导致树失衡,此时只需更新途径上结点的BF值即可.
    • 如果途径上结点BF值不全为0,则可以从插入节点位置沿着途径向上查找,找到第一个BF值不为0的结点,以该节点为根节点的树称为最小非平衡子树,后续的调整都在最小非平衡子树上进行. 记最小非平衡子树的根节点为a, 有左右两棵子树,BF都为0,但两棵树高度差1
      • 如果数据插入较低子树,则a的高度不变,且BF变为0.只需调整插入位置到a路径上结点的BF值即可,其他结点的BF值不变
      • 如果数据插入较高子树,则要调整高子树一部分数据到低子树中,以平衡高度.
        • LL型调整,a左子树较高,新节点插入到左子树的左子树
        • LR型调整,a左子树较高,新节点插入到左子树的右子树
        • RR型调整,a右子树较高,新节点插入到右子树的左子树
        • LL型调整,a右子树较高,新节点插入到左子树的左子树

    LL调整

    (1) 插入结点前,中序遍历的序列为 AbBaCA b B a C
    (2) 插入结点后,导致结点a的BF变为2,不满足平衡二叉树的要求
    (3) 要保持中序遍历的顺序不变,AbBaCA^{\prime} b B a C,将b作为最小非平衡子树的根节点,AA^{\prime}为左子树,BaCBaC为右子树,即可达到平衡.

    给树节点增加一个BF属性:

    class TreeNode():
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
            self.bf = 0
    

    LL调整python实现:

    def LL(a, b):
        a.left = b.right
        b.right = a
    
        a.bf = 0
        b.bf = 0
        return b
    

    RR调整
    RR调整与LL调整类似:

    def RR(a, b):
        a.right = b.left
        b.left = a
    
        a.bf = 0
        b.bf = 0
        return b
    

    LR调整

    (1) 记根节点a左子树的右子树的根节点为c.由于a是最小非平衡子树的跟,所以b,c的bf都为0,以a为根的中序遍历序列是AbBcCaDAbBcCaD
    (2) 新节点可能插入c的左子树(B)或右子树©,插入后b结点的BF=-1, a结点的BF为2,失衡!
    (3) 将c提升为最小非平衡子树的根节点,左右结点分别为b,a,如图所示,中序遍历的结果为AbBcCaDAbB^{\prime}cCaDAbBcCaDAbBcC^{\prime}aD,保持不变,且c结点BF变为0,b和a结点的BF为-1,0或者1,取决于新节点位置.

    def LR(a,b):
        c = b.right
        b.right = c.left
        c.left = b
        a.left = c.right
        c.right = a
    
        # 以下情况是失衡后二叉树的情况
        if c.bf == 0:# c本身为插入节点
            a.bf = b.bf = 0
        elif c.bf == 1: # 新节点在左子树
            b.bf = 0
            a.bf = -1
        else:   # 新节点在右子树
            b.bf = -1
            a.bf = 0
        
        c.bf = 0
        return c
    

    c本身为插入结点的情况如下:

    RL调整

    def RL(a,b):
        c = b.left
        b.left = c.right
        c.right = b
        a.right = c.left
        c.left = a
    
        if c.bf == 0:
            a.bf = b.bf = 0
        elif c.bf == 1:
            a.bf = 0
            b.bf = -1
        else:
            a.bf = -1
            b.bf = 0
        c.bf = 0
        return c
    

    平衡二叉排序树的插入操作:

    • 查找新节点的插入位置,并在查找过程中记录最小不平衡子树的根
    • 修改插入位置到最小不平衡子树根路径上各节点的平衡因子
    • 检查以a为根的子树是否失衡,若失衡则依据情况进行调整.
    def insert(btree, key):
        if btree is None:
            return TreeNode(key)
        a = btree   # 最终是最小不平衡树的根
        p = btree   # 指针
        fa = None   # a的父节点
        q = None    # p的父节点
    
        # 1. 查找插入位置并记录最小非平衡树根节点
        while p:
            # 若BF值不为0,则有可能为最小不平衡树的结点
            if p.bf != 0:
                fa, a = q, p
            
            # 查找插入位置:
            if p.val == key:
                return btree
            elif key < p.val:
                q = p
                p = p.left
            else:
                q = p
                p = p.right
        # 2. 插入节点
        # 此时q是待插入结点的父节点
        node = TreeNode(key)
        if key < q.val:
            q.left = node
        else:
            q.right = node
        
        # 3. 更新BF值,只需更新插入位置到a结点路径上结点的BF值.
        # 先判断插入节点在a的左子树还是右子树
        if key < a.val:
            p = a.left  # 指针
            b = a.left  # a深度较大子树的根节点,用于后续调整
            d = 1
        else:
            p = a.right
            b = a.right
            d = -1
    
        while p != node:
            if key < p.val:
                p.bf = 1    # p原来BF为0
                p = p.left
            else:
                p.bf = -1
                p = p.right
            
        # 4. 判断是否需要调整
        if a.bf == 0:   # a本身平衡,无需调整
            a.bf = d
            return btree
        elif a.bf == -d:    # 增加的结点在较低的树上,无需调整
            a.bf = 0
            return btree
        else:   # 增加的结点在较高的树上
            if d == 1:  # 增加在左子树
                if b.bf == 1: # 增加在左子树的左子树
                    b = LL(a, b)
                else:   # 增加在左子树的右子树
                    b = LR(a, b)
            else:
                if b.bf == 1:
                    b = RL(a, b)
                else:
                    b = RR(a, b)
        
        # 5.将调整好的树接回去
        # a为根节点
        if pa is None:
            btree = b
        elif pa.left == a:
            pa.left = b
        else:
            pa.right = b
        
        return btree
    
    展开全文
  • 二叉排序树与平衡二叉排序树的转化

    千次阅读 热门讨论 2015-10-11 21:43:06
    这篇博客会首先介绍二叉排序树,再介绍什么是平衡二叉树,为什么要会有平衡二叉排序树,最后来看转化。 1.什么是二叉排序树?  二叉排序树(Binary Sort Tree)又称查找二叉树,它可以是一个空树,或者要满足

        二叉排序树与平衡二叉树的转化开始单独看视频的时候感觉是明白的,但是看到题就不知所措了,如果单向旋转还可以,碰到LR型和RL型的就有困难了,所以一定要写个博客来把它弄懂。这篇博客会首先介绍二叉排序树,再介绍什么是平衡二叉树,为什么要会有平衡二叉排序树,最后来看转化。


    1.什么是二叉排序树?


        二叉排序树(Binary Sort Tree)又称查找二叉树,它可以是一个空树,或者要满足以下条件:

       (1)左右子树各是一棵查找树。

       (2)如果有左子树,则左子树的各节点值均小于根节点的值。

       (3)如果有右子树,则右子树上的各节点值均大于根节点的值。


        总之就是它的左子树比根节点小,右子树比根节点大。


    2.什么是平衡二叉树?


       平衡二叉树要么是一棵空树,或者是一棵这样的树:树种任一节点的左右子树的深度相差不超过1

       如定义结点的平衡度为其右子树的深度减去其左子树的深度,则对于平衡二叉树,它的每个结点的平衡度-1,0,1三个值之一.


    3.为什么会有平衡二叉树?


       我们知道二叉排序树又称查找二叉树,平衡二叉树是一个排序二叉树,所以算是平衡二叉排序树,是用来查找的,看下面这张图,这张图是软考视频中的:




       如果查找1的话,第一个图要查找6次,第二个图只需要4次就可以了,所以深度相差越少,查找的次数越少.为了提高查找的效率,因此出现了平衡二叉树


    4.二叉排序树与平衡二叉排序树的转化


       先看几种转换的方式:


       (1)LL型平衡旋转(单向右旋平衡处理)




      (2)RR型平衡旋转(单向左旋平衡处理)



      (3)LR型平衡旋转(双向旋转,先左后右)



      (4)RL型平衡旋转(双向旋转,先右后左)



        从上面的例子我们很容易看懂,做题的时候我们找到对应类型进行旋转,每次旋转90度。


        例题:

        下面是一个自考试题,以这个题为例, 进行旋转,先看原图:


      首先判断类型是LR型,先左后右,如果不知道子结点放在哪里可以想一下二叉排序树的特点,就知道数怎么放了。

                                                    


    上面的图就是旋转的过程,不知道大家明白了没有


    小结:


          看理论觉得是懂得,真正做题就模糊了,这里面掌握了一些概念,想着这些树的特点,用理论指导实践,把这些理论用到实处发现其实很简单。本来对它不熟悉,所以写这篇博客来进行总结,总结完之后就会了,哈哈~



    展开全文
  • 二叉排序树与平衡二叉树的转化开始单独看视频的时候感觉是明白的,但是看到题就不知所措了,如果单向...这篇博客会首先介绍二叉排序树,再介绍什么是平衡二叉树,为什么要会有平衡二叉排序树,最后来看转化。...

    此文转载自http://blog.csdn.net/ww130929/article/details/49029895

     

        二叉排序树与平衡二叉树的转化开始单独看视频的时候感觉是明白的,但是看到题就不知所措了,如果单向旋转还可以,碰到LR型和RL型的就有困难了,所以一定要写个博客来把它弄懂。这篇博客会首先介绍二叉排序树,再介绍什么是平衡二叉树,为什么要会有平衡二叉排序树,最后来看转化。

     

    1.什么是二叉排序树?

     

        二叉排序树(Binary Sort Tree)又称查找二叉树,它可以是一个空树,或者要满足以下条件:

       (1)左右子树各是一棵查找树。

       (2)如果有左子树,则左子树的各节点值均小于根节点的值。

       (3)如果有右子树,则右子树上的各节点值均大于根节点的值。

     

        总之就是它的左子树比根节点小,右子树比根节点大。

     

    2.什么是平衡二叉树?

     

       平衡二叉树要么是一棵空树,或者是一棵这样的树:树种任一节点的左右子树的深度相差不超过1

       如定义结点的平衡度为其右子树的深度减去其左子树的深度,则对于平衡二叉树,它的每个结点的平衡度-1,0,1三个值之一.

     

    3.为什么会有平衡二叉树?

     

       我们知道二叉排序树又称查找二叉树,平衡二叉树是一个排序二叉树,所以算是平衡二叉排序树,是用来查找的,看下面这张图,这张图是软考视频中的:


     

       如果查找1的话,第一个图要查找6次,第二个图只需要4次就可以了,所以深度相差越少,查找的次数越少.为了提高查找的效率,因此出现了平衡二叉树

     

    4.二叉排序树与平衡二叉排序树的转化

     

       先看几种转换的方式:


       (1)LL型平衡旋转(单向右旋平衡处理)

     

     

      (2)RR型平衡旋转(单向左旋平衡处理)

     

      (3)LR型平衡旋转(双向旋转,先左后右)

     

      (4)RL型平衡旋转(双向旋转,先右后左)

     

        从上面的例子我们很容易看懂,做题的时候我们找到对应类型进行旋转,每次旋转90度。

     

        例题:

        下面是一个自考试题,以这个题为例, 进行旋转,先看原图:

      首先判断类型是LR型,先左后右,如果不知道子结点放在哪里可以想一下二叉排序树的特点,就知道数怎么放了。

                                                    

     

    上面的图就是旋转的过程,不知道大家明白了没有

     

    小结:

     

          看理论觉得是懂得,真正做题就模糊了,这里面掌握了一些概念,想着这些树的特点,用理论指导实践,把这些理论用到实处发现其实很简单。本来对它不熟悉,所以写这篇博客来进行总结,总结完之后就会了,哈哈~

    转载于:https://www.cnblogs.com/sz-zzm/p/6093550.html

    展开全文
  • 第7章 高级字典结构 第21讲平衡二叉排序树;字典的表示(实现;回顾二叉排序树;回顾二叉排序树;回顾二叉排序树的查找性能;平衡二叉排序树(AVL树;平衡二叉排序树(AVL树;AVL树--存储结构;平衡二叉排序树(AVL树;平衡二叉...
  • 平衡二叉排序树的概念 平衡二叉排序树四种不平衡的类型及解决方法 算法 插入 删除 查找 一.平衡二叉排序树的概念 如果树T既是平衡二叉树(树中每个结点的左右子树的高度差不超过1),又是二叉排序树,...
  • 平衡二叉排序树又称AVL树。 平衡二叉排序树性质: ① 左右子树的高度之差的绝对值小于等于1。 ② 左右子树也是平衡二叉排序树平衡二叉排序树比普通的二叉排序树查询效率要高。 平衡因子:结点的左子树深度...
  • 文章目录一 前言二 平衡二叉排序树阐述1. 二叉排序树的不足2. 平衡二叉排序树的性质3. 平衡二叉排序树效率分析4. 左旋、右旋以及四种失衡类型 一 前言   在了解平衡二叉排序树前,请大家务必掌握 BS二叉排序树的...
  • 二叉排序树又称为二叉查找树,它是一颗特殊的二叉树。(空树)  性质:1、若它的左子树非空,则左子树上的所有结点的值均小于根结点的值。  2、若它的右子树非空,则右子树上的所有结点的值均大于根结点的值。 ...
  • 用二叉链表作存储结构,编写程序实现二叉排序树上的基本操作:以回车('\n')为输入结束标志,输入数列L,生成二叉排序树T......
  • 依次把结点的关键字的值为50,30,20,150,130,40,80,70,85,15的记录插入到初始化为空的平衡二叉排序树中,在插入过程中平衡树条件如被破坏,则进行必要的调整,得到的平衡二叉排序树的深度为() 正确答案: C 你的...
  • 面向21世纪课程教材 普通高等教育十一五国家级规划教材 北京市高等教育精品教材 教育部普通高等教育精品教材 算法与数据结构 第十二讲 最佳和平衡二叉排序树 1 张乃孝等编著 算法与数据结构C语言描述 7 高级字典结构...
  • 平衡二叉排序树又称AVL树。 一棵平衡二叉排序树或者是空树,或者是具有下列性质的二叉排序树: 左子树与右子树的高度之差的绝对值小于等于1; 左子树和右子树也是平衡二叉排序树。 引入平衡二叉排序树的目的,是...
  • 26. 平衡二叉排序树

    万次阅读 多人点赞 2018-03-05 21:21:25
    平衡二叉排序树的生成,查找和删除
  • 二叉排序树的时间复杂度为 O(n),平衡二叉排序树的时间复杂度为 O(logn) 平衡二叉树又称 AVL 树,是一种特殊的二叉排序树,拥有更高的查询效率。平衡二叉树或是一棵空树,或满足下列性质的一棵非空的二叉树T: T的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,934
精华内容 1,573
关键字:

平衡二叉排序树