网站开发团队排行榜,广东省交通建设监理检测协会网站,网站浏览器不兼容怎么办,18款禁用黄在线观看免费一、栈
先进后出
二、队列
先进先出
三、数组
查询快#xff0c;增加修改慢
四、链表
查询慢#xff0c;增加修改慢
五、二叉树
节点#xff1a; 查找二叉树
二叉查找树的特点 二叉查找树,又称二叉排序树或者二叉搜索树 每一个节点上最多有两个子节点 左子树上所…一、栈
先进后出
二、队列
先进先出
三、数组
查询快增加修改慢
四、链表
查询慢增加修改慢
五、二叉树
节点 查找二叉树
二叉查找树的特点 二叉查找树,又称二叉排序树或者二叉搜索树 每一个节点上最多有两个子节点 左子树上所有节点的值都小于根节点的值 右子树上所有节点的值都大于根节点的值 二叉查找树添加节点规则 小的存左边 大的存右边 一样的不存
数据结构(二叉树)遍历方式
前序遍历:当前节点左子节点右子结点中序遍历:左子节点当前节点右子结点后序遍历:左子节点右子结点当前节点层序遍历:一层一层的去遍历
平衡二叉树
特点 二叉树左右两个子树的高度差不超过1 任意节点的左右两个子树都是一颗平衡二叉树
平衡二叉树旋转 旋转触发时机 当添加一个节点之后,该树不再是一颗平衡二叉树 左旋 确定支点:从添加的节点开始不断的往父节点找不平衡的节点 以不平衡的点作为支点 将根节点的右侧往左拉 原先的右子节点变成新的父节点并把多余的左子节点出让给已经降级的根节点当右子节点
右旋 确定支点:从添加的节点开始不断的往父节点找不平衡的节点
以不平衡的点作为支点 就是将根节点的左侧往右拉 原先的左子节点变成新的父节点并把多余的右子节点出让给已经降级的根节点当左子节点
平衡二叉树旋转的四种情况
左左 左左: 当根节点左子树的左子树有节点插入,导致二叉树不平衡 如何旋转: 直接对整体进行右旋即可 左右 左右: 当根节点左子树的右子树有节点插入,导致二叉树不平衡 如何旋转: 先在左子树对应的节点位置进行左旋,再对整体进行右旋 右右 右右: 当根节点右子树的右子树有节点插入,导致二叉树不平衡 如何旋转: 直接对整体进行左旋即可 右左 右左:当根节点右子树的左子树有节点插入,导致二叉树不平衡 如何旋转: 先在右子树对应的节点位置进行右旋,再对整体进行左旋 红黑树
红黑树的特点
红黑树的增删改查性能都很好 平衡二叉B树 每一个节点可以是红或者黑 红黑树不是高度平衡的,它的平衡是通过自己的红黑规则进行实现的
节点 红黑规则 每一个节点是红色的或者是黑色的根节点必须是黑色叶节点是黑色的两个红色节点不能相连任意节点到所有后代叶节点的简单路径上黑色节点数量相同; 红黑树结构图 红黑树添加节点的默认颜色 添加节点时,默认为红色,效率高
红黑树添加节点后如何保持红黑规则 根节点位置 直接变为黑色 非根节点位置 父节点为黑色 不需要任何操作,默认红色即可 父节点为红色 叔叔节点为红色 将父节点设为黑色,将叔叔节点设为黑色 将祖父节点设为红色 如果祖父节点为根节点,则将根节点再次变成黑色 叔叔节点为黑色 将父节点设为黑色 将祖父节点设为红色 以祖父节点为支点进行旋转 实现代码
public class RBTree {class Node {int val, color;Node left, right;}
// 使用NIL节点来充当叶节点Node NIL;Node root;public RBTree() {NIL new Node();NIL.val -1;NIL.color 1;NIL.left NIL.right NIL;root NIL;}// 创建节点private Node getNewNode(int val) {Node p new Node();p.val val;p.color 0;p.left p.right NIL;return p;}//判断有没有红色孩子private boolean has_red_child(Node tree) {return tree.left.color 0 || tree.right.color 0;}//左旋private Node left_rotate(Node tree) {Node temp tree.right;tree.right temp.left;temp.left tree;return temp;}//右旋private Node right_rotate(Node tree) {Node temp tree.left;tree.left temp.right;temp.right tree;return temp;}//寻找前驱private Node preNode(Node tree) {Node p tree.left;while (p.right ! null) {p p.right;}return p;}//删除public void erase(int val) {root erase(root, val);}private Node erase(Node tree, int val) {tree __erase(tree, val);tree.color 1;return tree;}private Node __erase(Node tree, int val) {if (tree NIL) return tree;if (val tree.val) {tree.left __erase(tree.left, val);} else if (val tree.val) {tree.right __erase(tree.right, val);} else {if (tree.left NIL || tree.right NIL) {Node temp tree.left NIL ? tree.right : tree.left;temp.color tree.color;tree temp;return tree;} else {Node temp preNode(tree);tree.val temp.val;tree.left __erase(tree.left, temp.val);}}return erase_maintion(tree);}//删除调整private Node erase_maintion(Node tree) {if (tree.left.color ! 2 tree.right.color ! 2) return tree;
// 兄弟为红旋转树新根节点转为黑原根节点转为红if (has_red_child(tree)) {int flag 0;tree.color 0;if (tree.left.color 0) {tree right_rotate(tree);flag 1;} else {tree left_rotate(tree);}tree.color 1;if (flag 1) tree.right erase_maintion(tree.right);else tree.left erase_maintion(tree.left);return tree;}
// 兄弟为黑色并且没有红色子节点,子节点减黑根节点加黑if (tree.left.color 1 !has_red_child(tree.left)|| tree.right.color 1 !has_red_child(tree.right)) {tree.color 1;tree.left.color - 1;tree.right.color - 1;return tree;}
// 兄弟节点为黑并且有红色子节点
// |-- 左子树为黑色
// |-- 左子树的右子树为红色且左子树节点为黑 LR
// |-- 子树小左旋新节点转黑原节点转红,进入LL形态
// |-- 左子树的左子树为红色 LL
// |-- 整树右旋新节点改为原根节点的颜色原根节点已经新叔叔节点转为黑色
// |-- 右子树为黑色
// |-- 右子树的左子树为红色且右子树节点为黑 RL
// |-- 子树小右旋新节点转黑原节点转红,进入RR形态
// |-- 右子树的右子树为红色 RR
// |-- 整树左旋新节点改为原根节点的颜色原根节点已经新叔叔节点转为黑色if (tree.left.color 1) {tree.right.color 1;if (tree.left.left.color ! 0) {tree.left.color 0;tree.left left_rotate(tree.left);tree.left.color 1;}tree.left.color tree.color;tree right_rotate(tree);} else {tree.left.color 1;if (tree.right.right.color ! 0) {tree.right.color 0;tree.right right_rotate(tree.right);tree.right.color 1;}tree.right.color tree.color;tree left_rotate(tree);}tree.left.color 1;tree.right.color 1;return tree;}//添加public void insert(int val) {root insert(root, val);}private Node insert(Node tree, int val) {tree __insert(tree, val);tree.color 1;return tree;}private Node __insert(Node tree, int val) {if (tree NIL) {return getNewNode(val);}if (val tree.val) {tree.left __insert(tree.left, val);} else if (val tree.val) {tree.right __insert(tree.right, val);}return insert_maintain(tree);}//添加调整private Node insert_maintain(Node tree) {if (!has_red_child(tree)) return tree;//节点双红if (tree.left.color 0 tree.right.color 0) {if (!has_red_child(tree.left) !has_red_child(tree.right)) return tree;tree.color 0;tree.left.color tree.right.color 1;return tree;}if (tree.left.color 0 !has_red_child(tree.left)) return tree;if (tree.right.color 0 !has_red_child(tree.right)) return tree;// 左子树失衡if (tree.left.color 0) {if (tree.left.right.color 0) {tree.left left_rotate(tree.left);}tree right_rotate(tree);} else {if (tree.right.left.color 0) {tree.right right_rotate(tree.right);}tree left_rotate(tree);}tree.color 0;tree.left.color tree.right.color 1;return tree;}//打印输出public void preorder() {preorder(root, root.val, 0);}private void preorder(Node tree, int val, int flag) {if (tree NIL) return;if (flag 0) {System.out.printf(%d is root, color is %s\n, val, tree.color 0 ? red : black);} else {System.out.printf(%d is %ds %s child, color is %s\n, tree.val, val, flag 1 ? right : left, tree.color 0 ? red : black);}preorder(tree.left, tree.val, -1);preorder(tree.right, tree.val, 1);}
}
