網(wǎng)站建設(shè)一般要多少費(fèi)用網(wǎng)絡(luò)營銷的含義
文章目錄
- 概述
- 實(shí)現(xiàn)
- 創(chuàng)建節(jié)點(diǎn)
- 查找節(jié)點(diǎn)
- 增加節(jié)點(diǎn)
- 查找后驅(qū)值
- 根據(jù)關(guān)鍵詞刪除
- 找到樹中所有小于key的節(jié)點(diǎn)的value
概述
二叉搜索樹,它具有以下的特性,樹節(jié)點(diǎn)具有一個(gè)key屬性,不同節(jié)點(diǎn)之間key是不能重復(fù)的,對(duì)于任意一個(gè)節(jié)點(diǎn),它的key都要比左子樹的key大,比右子樹的key小
實(shí)現(xiàn)
創(chuàng)建節(jié)點(diǎn)
static class BSTNode {int key;Object value;BSTNode left;BSTNode right;public BSTNode(int key, Object value) {this.key = key;this.value = value;}public BSTNode(int key, Object value, BSTNode left, BSTNode right) {this.key = key;this.value = value;this.left = left;this.right = right;}}
查找節(jié)點(diǎn)
利用二叉樹的性質(zhì)
public Object get(int key) {BSTNode node = root;while (node != null) {if (node.key < key) {node = node.right;} else if (node.key > key) {node = node.left;} else {return node.value;}}return null;}
增加節(jié)點(diǎn)
同樣利用二叉樹的性質(zhì),但是需要記錄要增加的節(jié)點(diǎn)的父節(jié)點(diǎn)
public void put(int key, Object value) {BSTNode node = root;BSTNode parent = null;while (node != null) {parent = node;if (key < node.key) {node = node.left;} else if (key > node.key) {node = node.right;} else {//直接修改node.value = value;return;}}if (parent == null) {root = new BSTNode(key, value);} else if (key > parent.key) {parent.right = new BSTNode(key, value);} else {parent.left = new BSTNode(key, value);}}
查找后驅(qū)值
在后面的AVL,以及紅黑樹中刪除節(jié)點(diǎn)是,我們經(jīng)常會(huì)需要求一個(gè)節(jié)點(diǎn)的后驅(qū)節(jié)點(diǎn)
分類討論,分成兩種情況
若節(jié)點(diǎn)有右子樹,那么右子樹的最小值就是前驅(qū)
若沒有右子樹,則去尋找是否存在從右而來的祖先節(jié)點(diǎn),最近的這個(gè)祖先節(jié)點(diǎn)就是后驅(qū)
兩種情況都不滿足,則該節(jié)點(diǎn)沒有后驅(qū)
public Object predecessor(int key) {BSTNode ancestorFromRight = null;BSTNode node = root;while (node != null) {if (key < node.key) {ancestorFromRight = node;node = node.left;} else if (key > node.key) {node = node.right;} else {break;}}//沒有該節(jié)點(diǎn)if (node == null) {return null;}if (node.right != null) {return min(node.right);}return ancestorFromRight == null ? null : ancestorFromRight.value;}public Object min(BSTNode node) {if (node == null) {return null;}while (node.left != null) {node = node.left;}return node.value;}
根據(jù)關(guān)鍵詞刪除
根據(jù)關(guān)鍵字刪除
刪除有一下幾種情況
第一種:刪除節(jié)點(diǎn)沒有右孩子,將左孩子掛過去
第二種:刪除節(jié)點(diǎn)沒有左孩子,將右孩子掛過去
第三種:都沒有,掛過去null
第四種:左右孩子都有,可以將后繼節(jié)點(diǎn)掛在parent后面,后繼節(jié)點(diǎn)為s,后繼節(jié)點(diǎn)的父親為sp
??1.將如果sp就是要?jiǎng)h除的節(jié)點(diǎn)
??2.sp不是刪除節(jié)點(diǎn),需要將s的后代給sp
public Object delete(int key) {BSTNode node = root;BSTNode parent = null;while (node != null) {if (key < node.key) {parent = node;node = node.left;} else if (key > node.key) {parent = node;node = node.right;} else {break;}}if (node == null) {return null;}if (node.left == null) {//情況1shift(parent, node, node.right);//情況2} else if (node.right == null) {shift(parent, node, node.left);} else {BSTNode s = node.right;BSTNode sParent = node;while (s.left != null) {sParent = s;s = s.left;}if (sParent != node) {//將后驅(qū)節(jié)點(diǎn)的孩子掛在后驅(qū)節(jié)點(diǎn)父親的后面shift(sParent, s, s.right);s.right = node.right;}//后驅(qū)節(jié)點(diǎn)一定沒有左孩子,所以可以直接的掛靠shift(parent, node, s);s.left = node.left;}return node.value;}/** 托孤方法** */private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {if (parent == null) {root = child;} else if (deleted == parent.left) {parent.left = child;} else {parent.right = child;}}
找到樹中所有小于key的節(jié)點(diǎn)的value
我們可以通過一個(gè)中序遍歷實(shí)現(xiàn),對(duì)于一個(gè)二叉搜索樹來說,中序遍歷的結(jié)果,恰好是從小到大排序的
public List<Object> less(int key) {ArrayList<Object> result = new ArrayList<>();LinkedList<BSTNode> stack = new LinkedList<>();BSTNode node = root;while (node != null || !stack.isEmpty()) {if (node != null) {stack.push(node);node = node.left;} else {BSTNode min = stack.pop();if (min.key < key) {result.add(min.value);} else {break;}node = min.right;}}return result;}